Need an adaptive algorithm for participant subgroups that balances repeated pairings I want to build a utility that helps manage small groups of participants. It is an acting class setting.
For each exercise, the facilitator will usually have some number of participants get up to do a scene. Two is the most common, but sometimes 1 or 3 or 4. More than 4 is not common.
I want the utility to have a list of participants and then the facilitator can just ask it for a specified number of people. E.g. 2.
The utility should do a good job of balancing combinations. For example, let's say there are 5 participants, A, B, C, D, E. If A and B work together, then ideally they should have also worked with C, D, and E before working together again.
I know how to manage this well if it's always just pairs. You can create, in advance an ordered list of all the pairings.
But once you add the possibility of other changeable group sizes, I don't know how to manage it.
My starting point is to keep track of how often each participant has worked with every other participant. So, I could look at A and know how often she has worked with B, C, D, and E, and then if A is due to get up, pair her with the person/people she has worked least often with.
The problem with this, is that it can lead to situations where the last remaining unmatched pair have already worked together.
As a simple counter-example: Say I have 6 participants - A - F. In the first lot of exercises, these are the pairs. AB CD EF. Then next round, I might (if not thinking) do AC, then BD, but now I'm left with E and F again. This is not ideal, and is what I need the algorithm to avoid.
I think part of the solution should be that everyone should get a roughly even number of turns. So, at any given point, we have a group of participants who have had fewer turns that the others, and we need to balance them out so that they don't work with people they've worked with (where possible) or at least with the people they've worked with least, and it needs to anticipate the possible remaining combinations and avoid duplication there too. Part of the complexity is that you don't know in advance what group sizes will be used for the remaining groups.
Does this type of algorithm / problem set have a specific name? Are there known algorithms for solving it?
(As an extra complication, there is the possibility of a participant having to leave unexpectedly, or an extra participant who arrives late, but that might be for later)
This is my first time asking here, so I hope I've posted this appropriately. Thanks for your patience and assistance!

It sounds like the stakes are low, so I would suggest something simple and "good enough", rather than looking for fancy algorithms that will be guaranteed to give the optimal solution.  One approach is to take the approach you're already considering, but break ties randomly.  This seems like it may do well enough in practice: it is possible to get  into a bad situation, but the randomness might make that unlikely; and this might occasionally have one student participate a little more than they otherwise would, but that I'd expect that to average out over time and so maybe it isn't a big deal.


Existence of Efficient Set Difference Algorithm As a foreword, I'm not asking what the algorithm is, just whether one can possibly exist (though, if it does already exist and someone knows what it is, that'd be great).

Basically, given two sets $S$ and $T$, I want to compute the two set differences $I = T \setminus S$ and $R = S \setminus T$. The goal is that if $S$ represents a "before" set, and $T$ an "after" set, I want to know what elements were inserted into (represented by $I$) and removed from (represented by $R$) the original set $S$ to get to $T$.

A naïve approach would be to compare every element of $S$ with every element of $T$, a worst-case runtime of $O(n * m)$, where $n = |S|$ and $m = |T|$.

An improvement would be to treat $S$ as a list and sort it, then do a binary search in the sorted list for every element in $T$. This would be worst-case (I believe) $O(n \log n + m \log n)$.

However, I think I can get it down to $O(n + m)$, and here's my thought process:

If $S$ is a list of $s_i$ and $T$ a list of $t_i$, we can define a "modification" bit for each element in each list.

If we define
$$c_i = \begin{cases} 1, & s_i \in R \\ 0, & \text{else} \end{cases}$$
and
$$d_i = \begin{cases} 1, & t_i \in I \\ 0, & \text{else} \end{cases}$$

and we define a "concatenation" sequence of the two:
$$x_i = \begin{cases} c_i, & 0 \leq i < n \\ d_{i-n}, & n \leq i < n+m \end{cases}$$

we can define a "modification" number:
$$X = \sum_{i=0}^{n+m-1} 2^i x_i$$

We can then compute $R$ and $I$ by breaking down the "modification" number $X$ into $c_i$ and $d_i$, giving
$$I = \{ t_i | d_i = 1 \}$$
and
$$R = \{ s_i | c_i = 1 \}$$.

Now, since $c_i$ and $d_i$ rely on $R$ and $I$, we can redefine them based on how $R$ and $I$ are defined:
$$(s_i \in R) \iff (s_i \in S \land s_i \notin T)$$
$$(t_i \in I) \iff (t_i \in T \land t_i \notin S)$$
So $c_i$ and $d_i$ are now:
$$c_i = \begin{cases} 1, & s_i \in S \land s_i \notin T \\ 0, & \text{else} \end{cases}$$
$$d_i = \begin{cases} 1, & t_i \in T \land t_i \notin S \\ 0, & \text{else} \end{cases}$$

Therefore, the modification number $X$ only depends on the original sets/lists $S$ and $T$. Furthermore, since $X$ is composed of $n + m$ bits, any set difference algorithm should be able to compute these bits in $\Omega(n + m)$ time. It could then compute $S$ and $T$ as described above, which would take $O(n)$ and $O(m)$ time, respectively.

My primary concern is the assumption that computing $n + m$ bits should only take $\Omega(n + m)$ time - my reasoning for that is based on the proof of the lower bound of the general sorting algorithm, and how sorting a list is similar to computing $\log_2 n!$ bits, which (from Sterling's Approximation) is $O(n \log n)$.

Again, I'm mostly interested in the validity of my reasoning, and whether or not this means a linear-time algorithm exists for computing set-differences.

An example application that I'm currently interested in (and what originally inspired this) is when a SCSI host rescans its bus for changes in device topology. Typically, it has a list of custom device objects that represent the corresponding device's current state. Upon rescan, the host gets a list of devices currently on the bus, but only by a small identifier (such as it's bus location or LUN).

The problem, then, is how to efficiently map this new device list to the existing device object list, so that unchanged devices are mapped to their corresponding objects, and any device objects whose corresponding devices have been removed can be cleaned up, and any new devices can have objects allocated for them.

If I let $S$ be the list of current devices (by their ID, with some other simple mapping from the ID to the object data), and $T$ be the results of the rescan, then I can efficiently compute $I$ and $R$, and allocate new objects for devices in $I$ and clean up objects for devices in $R$ in linear ($O(n + m)$) time.

You can compute $S\setminus T$ and $T\setminus S$ from $S$ and $T$ in $O(n+m)$ time using a hash table.  Put all of list $S$ into a hashtable, and then iterate through list $T$ and look it up in the hashtable.  Then do the same, with $T$ in the hashtable and iterating through $S$.

Fine print for complexity purists: this is expected running time, making suitable assumptions about the hash function.  However, the probability that the running time takes longer than $c \cdot (n+m)$ can be made exponentially small in $c$ with a suitable choice of hash function.  For practical purposes, you typically don't need to worry about this.

You can also do it in $O(n \lg n + m \lg m)$ time, using a suitable sorting algorithm plus a standard merge algorithm.  In some special circumstances, sorting might be even faster (look up counting sort and radix sort).

Which of these is faster in practice will depend upon the platform you run it on.  You probably will need to implement and try both, to see which will be faster.  You can't trust the asymptotic complexity in this situation, as caching effects and other implementation considerations have the potential to be more important than the asymptotics.


User recognition through keystroke pattern Hello thank you for taking time looking at this question. Is it possible to determine the keystroke patterns for a certain user?

My idea is that, when the user enters their username & password it must contain a specific keystroke pattern that when analyzed it could probably predict the actual user and able to differentiate other user that might know the exact username and password from hacking or entering the account.

Keystroke dynamics is indeed a form of biometric recognition that has been studied for a long time. It was already known in the telegraph era: skilled operators could recognize each other's “fist”, similar to recognizing someone's handwriting.

As far as I know, this is not precise enough to authenticate someone. A 2005 study by Araújo et al. results in a 96.34% success rate (3.66% false acceptance) in a controlled experiment, for an imposter, for typing the same user-chosen string 10 times (see §IV.B). The false acceptance rate for a hard-to-type password is likely to be worse. It can be used as a second authentication factor, but as an authentication factor, it's pretty weak.

These days, a lot of authentication is performed remotely, with the typing device under control of the unauthenticated user, who may be the attacker. This means that keystroke dynamics is not reliable in this setting.

Keystroke dynamic is sometimes used, not as a primary authentication factor, but to raise alerts when an account might have been compromised. On its own, it has poor signal, since a user with unusual typing patterns may be wounded, tired, using an unfamiliar keyboard, etc. It can be useful in combination with other factors however.


Why are most (or all?) polynomial time algorithms practical? I read an interesting comment in a paper recently about how weirdly useful maths turns out to be. It mentions how polynomial time doesn't have to mean efficient in reality (e.g., $O(n^{999999999999999999999})$ is polynomial time, but not efficient). Yet, isn't it the case that all algorithms in polynomial time also happen to be realistic, like at most $O(n^4)$ or something? I guess my questions are:

Is this surprising?
Are there any examples of algorithms that are polynomial time but not practical?

The comment is wrong. It is very easy to give examples of polynomial time algorithms which aren't practical at all:

The ellipsoid algorithm for solving linear programs runs in polynomial time but is too slow to be practical. The simplex algorithm, whose worst-case running time is exponential, is preferred in practice.
The AKS primality testing algorithm runs in polynomial time but is too slow to be practical. Instead, randomized polynomial time algorithms are used. We sacrifice certainty for performance.
Fast matrix multiplication algorithms run asymptotically faster than high-school matrix multiplication (both are polynomial), but are too slow to be practical. The high-school algorithm is used in practice.
A similar issue occurs in fast integer multiplication algorithms. The algorithm with the best asymptotic complexity, Fürer's algorithm, is too slow to be used in practice. Instead, relatively simple algorithms are used even for quite large integers.
Big data algorithms need to run in linearithmic time (which is $O(n
\log^{O(1)}n)$) to be practical.

These examples show that the identification of polynomial time with practical is not accurate, and might depend on the circumstances. Researchers in theoretical algorithms feel a need to justify their field of research, and so they ideologically believe in the sentiments expressed in the comment you mention. You shouldn't take such comments too literally.

In fact, many algorithms used in practice are heuristic and we don't have any estimates on their running time other than empirical results. Such algorithm don't fit into the theoretical framework at all, yet there are very useful in practice. Several (but not all) machine learning algorithms belong to this class just in terms of running time (not to mention in terms of performance), as do search algorithms such as A* and alpha-beta, and SAT solving algorithms.


Calculating time it takes to download content I have a network line that runs at a speed of 400kbps. How long do I have to download 6GB.

Most likely what you have is a line with a 400kbps bandwidth. That means a maximum throughput of 400kbps.

If you divide by 8 bits you get KiloBytes/s = 50Kbs.

1GB = 100000KB, thus 6GB = 600000KB,

600000KB / 50KB/s = 12000 seconds = 200 minutes = 3 hours 20 minutes

That means it would take at least 3 hours 20 minutes to download.   It could take significantly longer depending on network traffic.


Find a CFG for univocalic words I'm trying to figure out how to create a CFG for univocalic words...

Univocalic words are words that have only one the same vowel letter throughout the word

Example:
September, Anna

Would appreciate any of your help..

Try the following grammar (which can be transformed into a regular grammar):

$S \rightarrow A \mid E \mid I \mid O\mid U$
$A \rightarrow aA \mid bA \mid cA \mid \dots \mid zA \mid \epsilon$ (all consonants and only 'a')
$E \rightarrow eE \mid bE \mid cE \mid \dots \mid zE \mid \epsilon$ (all consonants and only 'e')
$I \rightarrow iI \mid bI \mid cI \mid \dots \mid zI \mid \epsilon$ (all consonants and only 'i')
$O \rightarrow oO \mid bO \mid cO \mid \dots \mid zO \mid \epsilon$ (all consonants and only 'o')
$U \rightarrow uU \mid bU \mid cU \mid \dots \mid zU \mid \epsilon$ (all consonants and only 'u')

Example 1: $S \Rightarrow A \Rightarrow aA \Rightarrow anA \Rightarrow annA \Rightarrow annaA \Rightarrow anna$

Example 2: $S \Rightarrow E \Rightarrow sE \Rightarrow seE \Rightarrow sepE \Rightarrow septE \Rightarrow septeE \Rightarrow septemE \Rightarrow$ $septembE \Rightarrow septembeE \Rightarrow septemberE \Rightarrow september$

Warning: do not expect that this grammar generates only English dictionary words. For example it does generate a nonsense such as 'aagfdadgsa'.


Show that 6n^2 + 12n is O(n^2) I understand how I would do this if the problem were as such

$8n + 5$ is $O(n)$

$c>0$ and an integer constant $n(not 0) \geq 1$ such that $8n + 5 \leq cn$ for every integer $n \geq n(not 0)$

we could let $c= 13$ and $n(not 0) = 1$

or we could let $c = 9$ and $n( not 0) = 5$.

I'm just not sure how to go about $6n^2 +12n$

Let $f(n)=6n^2 + 12n$

The $O$ notation for $f(n)$ can be derived from the following simplification rules:

If $f(n)$ is a sum of several terms, we keep only the one with largest growth rate.
If $f(n)$ is a product of several factors, any constant is omitted.

From rule 1, $f(n)$ is a sum of two terms, the one with largest growth rate is the one with the largest exponent as a function of $n$, that is: $6n^2$

From rule 2, $6$ is a constant in $6n^2$ because it does not depend on $n$, so it is omitted.

Then: $f(n)$ is $O(n^2)$


Is it possible to repeat a wildcard in regex? .{5} would match any string of 5 symbols (excluding newline). Suppose I wanted to define "a 5-character repetition of a single character."

The immediate way that comes to mind is (.)\1{4}, but this relies on a back reference.

Using a subset of regex which is dependent only on |,(),*,concat any regex expression of pattern size M and search string size N can be solved with a  means an M-size NFA in O(NM) time.

Backreferences, unlike +, {n}, etc. are not derivable from the restricted regex tools above, and result in exponential times.

Is it possible to replicate the desired pattern in the non-exponential-time subset of regex (without using exponential* size)? If not, then why (how can we prove so)?

*one could go factorial in size by brute-forcing in this case.

Using backreferences you can accept non-regular languages such as the language of squares $ww$, which is accepted by (.*)\1. This language cannot be represented as a non-extended regular expression at all.


Prove that a stable algorithm cannot solve an ill-conditioned problem with a precision greater than that of input values How can I prove that a stable algorithm cannot solve an ill-conditioned problem with a precision greater than that of input values ?

It seems obvious to me, since an ill-conditioned problem is that in which exact input values(D) are totally different from error valuesI(D') (judging by something), thus the exact solution(G) differ much from one with error in some sense. This can be applied in case of algorithms: because if D and D' are far from each other somehow, than no one can expect for G(D*) to get closer to G*(D), where G* is the algorithm for implementing the G problem . Can you please show some more precise approach, less "in words" and more in logic ?

Thank you.

Let's try to define those terms in math language:

Denote $x$ as the input, and $f(x)$ is the solution to the problem with input $x$.
Ill-condition problem: $x'=x + \delta \Rightarrow f(x') \gg f(x) + \delta$
Stable algorithm $F(x) \simeq f(x')$ (stable algorithm give you result close to result of a nearby input)

So apply stable algorithm on ill-condition problem we get: $F(x) \simeq f(x') \gg f(x) + \delta$

Which says the best you can get can't be smaller than error in the input.

I think you can also prove by contradiction, saying if the stable algorithm can do that, then the changes in input will make only small change in the output which makes the problem well-condition.


For every imperative function, is there a functional counterpart with identical performance or even instructions? Currently, I haven't learned about a functional language that can achieve the same performance as C/C++. And I have learned that some languages that favor functional programming to imperative programming, such as Scala and Rust, use imperative ways to implement their library functions for better efficiency.
So here comes my question, on today's comptuters that execute imperative instructions, is this a limitation of the compiler or functional programming itself? For every imperative function with no side effects, either in a language without GC such as C/C++/Rust/assembly or one with GC such as Java, is there a pure functional counterpart in Haskell, Scala, etc. that can be compiled to run with identical performance in time and space (not just asymptotic but exactly the same) or even to the same instructions, with an optimal functional compiler that utilizes all modern and even undiscovered optimization techniques such as tail recursion, laziness, static analysis, formal verification, and so on which I don't know about?
I am aware of the equivalence between λ-computable and Turing computable, but but I couldn't find an answer to this question online. If there is, please share a compiler example or a proof. If not, please explain why and show a counter-example. Or is this a non-trivial open question?

Supplementary edits as suggested by Andrej Bauer:
To be more specific, here are 2 examples that led into thinking about this question.
For example, tail recursion and accumulators can improve the performance of some recursive functions to be identical to an imperative implementation using for. In some cases they might even have the same instructions.
Another example is about laziness in Haskell. Laziness can help avoid unnecessary copying of data structures and make performance better. However, laziness leaves wrappings, closures, etc. in the runtime and still can't make the program as fast as an imperative implementation where there are no such things. So I am wondering whether such things can be statically removed before runtime during compilation.
Supplementary edits as suggested by Nearoo:
The question can also be stated in this way: is there a language that supports both pure functional programming and imperative programming, paired with an optimized compiler, in which every function with no side effects implemented imperatively can be replaced with one implemented purely functionally, at no cost of performance or even compiled to the same instructions?

Performance is not a property of language, it is a property of specific programs within a language. Some languages might be very fast at some things and slow at others.
For example, Chez-Scheme can sometimes find performance comparable to C, not because the language is more efficient, but because defensive practices that programmers often use in C are less necessary in scheme.
Likewise, there are times when Haskell can do very efficient parallelism or concurrency, not because it is faster than C, but because the immutability guarantees of the language allow the programmer to avoid things like locks and other synchronization techniques.
And, performance varies from implementation to implementation. I can hand-roll a C interpreter, but it will certainly not be fast. C is not fast, GCC and Clang are.

What is considered a "functional" language? Every practical functional language has some facilities for mutable state: OCaml, Haskell, Scala, Lisp, Scheme, etc. Tail recursion gives something roughly equivalent to mutation inside of a for-loop. But when this is not enough, functional languages give the programmer access to mutable state. In the case of Haskell, this is controlled by the type system, so there is never implicit mutable state, but mutation is very much allowed and even encouraged in Haskell. Look at any Haskell code, and you will see the IO monad everywhere. Likewise, ML languages distinguish between types T and ref T, so you can tell by the types whether a variable is mutable or not.

There is no "optimal" compiler, thanks to Rice's theorem. All compilers, imperative or functional, are "best effort:" the use conservative approximations to optimize code.
If we had an optimal compiler, the answer would be that every program always ran using the most efficient instructions possible, and it wouldn't matter what language you coded your problem in. The optimal sequence of instructions computing a problem does not depend on the source language. But if we had this, then this compiler would compile every non-halting program into while(0), which means we could detect non-halting programs, which is impossible.

For Turing Machines and the lambda calculus, I think it is fairly trivial to implement a lambda calculus interpreter for Turing Machines that is asymptotically equivalent to a universal Turing-machine. Big-O complexity isn't what people mean when they say "Functional languages are slow". Usually they are talking about constant overhead, which is very different. We don't have as good of ways to mathematically model this, so we usually just end up using experiments to measure precise performance.


Reduction from Clique to something else Given $G(V,E)$ and $k$.
Is there a clique with size $k$?

Given set $X = \{x_1,x_2,\dots,x_n \}$, and collection $A = \{A_1,A_2,...,A_n\}$ of sub-sets of $X$ and $k$.
Are there are $k$ different elements in $A$, that every two of them has intersection that isn't empty? For example $A_1 = \{ x_1,x_2,x_3 \}$, $A_2 = \{x_4,x_5,x_1 \}$ so their intersection is $x_1$ and its valid, but it should be applied for every two $A_i,A_j$ in $A$.

Prove: That unnamed problem (which surely has a name) is NP-Hard.

The reduction is..

$X=E$, and every $A_i$ in $A$ is composed of edges that are connected to vertex $v_i$.

I can't understand the reduction, can someone explain why it works please?

$X = E$, so it remains to define the collection $A$. For each vertex $v_i$ in $V$ create $A_i$ as following: for each edge $x_t$ incident to the vertex $v_i$, add $x_t$ to $A_i$. Thus the edge $x_t=(v_i, v_j) \in E \Leftrightarrow A_i \cap A_j = \{x_t\}$, and every pair $A_i, A_j$ has at most one common element. So, if there are $k$ different elements in $A$ such that every two $A_i, A_j$ of them has non-empty intersection which is exactly the edge between vertices $v_i$ and $v_j$, then these $k$ vertices are pairwise connected meaning that they form a clique.


Is proof of totality of a semantic function for binary numbers cicular? I think the following proof found in a textbook is circular, since the proof for case n=n'0 assumes the case n=n'1 and vice versa. Am I missing something?

Proof that the semantic function N is a total function from binary strings into the integers:

  Let N be defined thusly:

  N(0) = 0;
  N(1) = 1;
  N(n0) = 2*N(n);
  N(n1) = 2*N(n) + 1;

  For any n, there is one and only on integer mapped to by N(n), that is to say, N is a total function from binary strings into the integers. (A)

  In the case n = 0, there is only one way to evaluate N(n) and that is with N(n) = N(0) = 0; hence (A) clearly holds. The proof for the case n = 1 is similar.

  In the case n = n'0, we have only one way to evaluate N(n) and that is with N(n) = N(n'0) = 2*N(n'). Assuming by induction that (A) holds for N(n'), (A) clearly holds for N(n). The proof for n = n'1 is similar.

  QED

In the second part of the proof, for the case n = n'0 you have to assume for induction that * holds for n = n'1, and vice versa. Does this not lead to a circular dependency in the proof?

The proof is by induction on the length of the string. You're proving the inductive claim for all strings of length $n$, both those terminating in $0$ and those terminating in $1$. The proof goes by considering these two cases, but you're assuming and proving the inductive hypothesis for all strings of a particular length at once.


Point rank in 2D plane time complexity? I'm reading about the algorithm of finding the ranks of all points in a 2D plane, I don't understand the time complexity formula for it. It has four steps:

Compute the median of x-coordinates of all point, and divide the plane into two half Left, and Right.
Recursively do 1. then when there is only 1 point, rank(that point)=0.
Sort points by y-coordinate in Left, and Right separately.
Update Right.

I understand the idea of these steps, and 3. has complexity $O(n\log n)$, but the time complexity formula in my book is

$$T(n)=2T(n/2)+\Theta(n),$$

why the last term is not $\Theta(n\lg n)$? That is my current idea is that the $T(n)=\Theta(n\lg^2n)$, by applying master's theorem.

I think I may solve it but I'm not sure: In short the sorting can be done in $\Theta(n)$, so the book statement, hence my assumption, is not correct. The "Sort points by y-coordinate in Left, and Right" actually only need to merge it, and this step is $\Theta(n)$.


How is this equation (involving a recurrence and $\phi(N)$) derived? As in another question, let

$$T(N) = \begin{cases}1 & \text{if } N = 1\\
T(\phi(N)) + \lg(\phi(N))^3 & \text{otherwise}
\end{cases}$$

where $\phi(N)$ is Euler's totient function.

Tasse kindly reasoned that we can write

$$T(N) = T(\phi(N))+\log(\phi(N))^3 = T(\phi(\phi(N)))+\log(\phi(\phi(N)))^3 + \log(\phi(N))^3$$

I can't at all see why this is true.  How is this equation derived?  I do understand his proof that $\phi(\phi(N)) < N/2$.

Here's the relevant part of the proof, quoting verbatim:

  First, show that $\phi(\phi(n)) < n/2$. This can be done as such:

  Let $n = \prod_{i=1}^rp_i^{k_i}$ be the prime factorisation of $n$
  ($p_i$ prime, $k_i>0$)

  Suppose $n$ is even. Then $\phi(n) = n\prod_{i=1}^r(1-\frac{1}{p_i}) \leq n(1-\frac{1}{2}) \leq n/2.$ Thus $\phi(\phi(n)) < n/2$.
  Suppose $n$ is odd and $n > 1$. Then $\phi(n) = \prod_{i=1}^r (p_i-1)p_i^{k_i-1}$ is even and smaller than $n$. By the previous
  result $\phi(\phi(n)) < n/2$.

  So we get the desired result.

This lemma is slightly mis-stated, because when $n=2$, $\phi(\phi(n)) = n/2$. But it doesn't invalidate the main result. We will state the lemma as:

Lemma For all $n \ge 2$, $\phi(\phi(n)) \le \frac{n}{2}$.

Tasse's proof sketch is a proof by induction in disguise, but this may not have been obvious to you. I'm going to simplify the proof sketch a little bit and lay it out more like a proper proof by induction.

Proof By induction on $n$.

Base case: If $n=2$, see above.

Inductive step: Suppose that for all $2 \le m < n$, $\phi(\phi(m)) \le \frac{m}{2}$. We want to prove that $\phi(\phi(n)) \le \frac{n}{2}$.

Case 1: Suppose $n$ is even, that is, $n = 2q$ for some $q$. In this case, the multiplicative property of the totient function says that $\phi(2q) = \phi(2) \phi(q) = \phi(q)$.

That is, $\phi(n) = \phi(\frac{n}{2})$. However, another useful property of the totient function is that for all $m \ge 2$, $\phi(m) \le m-1$. Therefore $\phi(\phi(n)) \le \frac{n}{2} - 1$.

This proves what we wanted for this case, but we have also incidentally proven another useful thing: If $n$ is even, then $\phi(n) \le \frac{n}{2}$. This will be important in the next step.

Case 2: Suppose $n$ is odd. That is, $n = p^k q$ for some odd prime $p$, and some positive integer $k$, and some $q$ which doesn't have $p$ as a divisor. Then:

$\phi(n) = \phi(p^k) \phi(q) = \left(p^k - p^{k-1}\right) \phi(q)$.

Now there are two things you need to notice about the right-hand side.

First off, it's less than $n$. Why? Because clearly $p^k - p^{k-1} < p^k$, and it's a standard property of the totient function that $\phi(q) \le q$. (Note that this is also true if $q = 1$.)

Secondly, it's even. Why? Because if $p$ is odd, $p^k - p^{k-1}$ is even.

So by that incidental result we discovered in case 1:

$\phi(\phi(n)) = \phi(\left(p^k - p^{k-1}\right) \phi(q)) \le \frac{\left(p^k - p^{k-1}\right) \phi(q)}{2} < \frac{n}{2}$.

QED


Find $f\colon \Bbb{N}\to\Bbb{N}$ such that $f = n^{o(1)}$ and for every $c\in\Bbb{N}$, $f(n)=\omega(\log^c n)$ Find $f\colon \Bbb{N}\to\Bbb{N}$ such that $f = n^{o(1)}$ and for every $c\in\Bbb{N}$, $f(n)=\omega(\log^c n)$.

It looks like I need to find a very small growing function $g$ that will satisfy
$$\lim_{n\to{\infty}} \frac{1}{g} = 0 $$
and also
$$\lim_{n\to{\infty}} \frac{\log^cn}{n^{\frac{1}{g}}} = 0 $$

My first attempt was $g(n) = \log n$
but according to wolfram alpha, the second limit was not satisfied,
I then tried $g(n) = \log\log n$ which according to wolfram does the trick.

But I'm not sure how to prove that
$$\lim_{n\to{\infty}} \frac{\log^cn}{n^{\frac{1}{\log\log n}}} = 0 $$

Im looking for a way to prove this, or find a simpler solution than $f=n^{1/\log\log n}$.

Take the log of your ratio to get
$$
c\log\log n - \frac{\log n}{\log\log n} = \frac{c\log^2 m - m}{\log m}, \quad \text{where } m = \log n.
$$
It is not hard to show that this tends to $-\infty$ as $m\to\infty$, and so as $n\to\infty$, which means that your ratio tends to zero as $n\to\infty$.

Indeed, since $c\log^2 m = o(m)$, for large enough $m$ we have $c \log^2 m - m \leq -m/2$. Since $2\log m = o(m)$, it follows that $\frac{m}{2\log m} \to \infty$ and so $\frac{-m}{2\log m} \to -\infty$.


Calculate the number of iterations in unusual nested loop I am trying to calculate the number of iterations of a sequence of nested loops of the form:

\begin{equation}
N = \sum_{j=0}^{j_T} \sum_{k=0}^{j} \sum_{l=0}^{k} \sum_{n=n_0}^{n_T} 1
\end{equation}

where $j_T\ge 0$ and $n_T\ge 0$ are known constants.

For $n_0 = 0$ the case is trivial and can be calculated using the standard procedure (Sum number of times statement is executed in triple nested loop)

The problem is that in my case $n_0$ is given by a more complex expression:

$$ n_0 = \begin{cases}
0    &\text{ if } k-2l\lt0,\\
n_T  &\text{ if }k-2l\gt n_T,\\
k-2l &\text{ otherwise.}
\end{cases} $$

Basically, the initial value of $n$ in the last sum is $k-2l$, except when its value is lower/greater than the lower/greater limits of the sum, in which case it gets replaced by the corresponding extreme value of the interval (either $0$ or $n_T$).

Any ideas?

If you want to compute an upper bound of the asymptotic complexity, you can consider the maximum value for the most inside sum. Hence,$\sum_{n=n_0}^{n_T}1 \leqslant n_T + 1$. Therefore, we will have:

$$
N \leqslant \sum_{j=0}^{j_T}\sum_{k=0}^j\sum_{l=0}^k (n_T+1) = \sum_{j=0}^{j_T}\sum_{k=0}^j (n_T+1) (k+1) = (n_T+1) \sum_{j=0}^{j_T}\sum_{k=0}^j (k+1)  =
$$
$$
(n_T+1)\sum_{j=0}^{j_T}\frac{(j+1)(j+2)}{2} = \Theta(n_T (j_T)^3)
$$

Therefore, $N = O(n_T (j_T)^3)$.


Are computers infallible? (Not sure if this is the right place to ask this question.)

Let's say I get a computer to calculate 1+1. It should give 2, obviously. Will it always give 2? Is there any possible combination of circumstances that could cause a computer to, after finishing its calculations, give a number other than 2?

To illustrate what I'm thinking of, for humans the answer is "no" because if they're (e.g.) sufficiently drunk, they might get it wrong.

An algorithm may be infallible. Any physical computer can make an error e.g. if it is hit by a stray cosmic ray, a bolt of lightning or a large axe.


Load and Store Data hazard problem in 5-stages pipeline Hi everyone and first of all thank you for been reading.
I'm a little confused about data hazard dependences when a "Store" instruction is followed by a "Load" instruction.
(Assume that we're working with a 5 stages pipeline processor withouth data forwading paths)

So if I have the following code now:

Store R3,R8,off-1
Load R3, off-2

If we've had ADD and Subsract instructions instead of "store" and "load" we'll have data hazard dependences, so we would have to "wait" for the result using No-Op, but in this case; can I start "fetchig" the second instruction while the first one is on "Decode" stage?

I think I'm missing some concepts here, as to where the operand is fetched from and where it gets stored to.

Thank you.

Assuming the stages are IF, ID, EX, MEM and WB, I believe the Load instruction cannot be carried out until the value has been written back in the first instruction i.e the WB stage.

This is what happens in the ID stage (from Hennessey-Patterson, Computer Architecture - A Quantitative Approach 4 ed.):

  Decode the instruction and read the registers corresponding to register source specifiers from the register file.

Since we have to read the registers in the ID stage, this cannot be done until the WB stage of the previous instruction has been completed as otherwise, it would lead to reading an incorrect value.

EDIT: On further notice, I've realised this might be incorrect. I wrote this answer under the assumption that the Store instruction passes through all the five pipeline stages. However, here, it is mentioned that:

  The store instruction stores to memory, so the "write" is performed inside MA.

So it won't have to wait till the WB stage, it can read the value after the MEM stage of the previous instruction.

That being said, more details about the instruction set would be helpful and how exactly are Load and Store defined would be helpful.


Null Hypothesis in Analysis and Testing I have my end of year exams next Thursday. I'm generally doing fine but I am having some major issues with this strand of my course, this has to be the biggest issue I have. So, here is the question in the past paper:

  You have been tasked with determining the validity of a
    manufacturer’s claim that their widget is more reliable than their main
    competitors’ widgets.

  In order to verify this assertion you test a sample of 25 widgets from
    the manufacturer’s range and find a mean pass rate of 992 per 1000
    with a standard deviation of 15 per 1000.

  Previous studies have shown that the mean pass rate of all other
    widgets on the market is 979.4 per1000.

  In order to increase the confidence in the making a decision about
    the null hypothesis you choose a 99.5% confidence level and find the
    corresponding t-table value to be 2.947.

  State the null hypothesis.

I have revision notes in front of me, but I just don't understand what this question is actually asking. Am I just writing down my own hypothesis, or do I need to use this equation?

  H0; μ
    H1; μ

If anyone could go through step by step for what I need to do, then that would be fantastic. My notes are just confusing!

For your particular problem, the null hypothesis is

$H_0: \mu_{manifacturer} = \mu_{competitors}$

and the alternative hypothesis is

$H_1: \mu_{manifacturer} > \mu_{competitors}$.

Basically, the null hypothesis states that there is no difference between the widget under test and the widgets made by other competitors. The alternative hypothesis states that, instead, there is a difference and the widget under test is better than the widgets made by the competitors.

Now, in your statistical significance test, you are trying to determine if you can reject the null hypothesis, i.e, if the data can be used to demonstrate for a specific confidence level that the widget made by this manufacturer may be better than the ones made by the competitors on the market. Note that I wrote "may be". If you can not reject the null hypothesis on the basis of the available data, this is interpreted by saying that statistically the data do not provide enough evidence to support your assumption that the widget under test is better.

See this Wikipedia article and this one on Statistical hypothesis testing for additional information.


Why is data in computer science considered to be discrete? I understand that "structure" of data is totally dependent on Boolean Algebra, but:

  Why is data considered to be a discrete mathematical entity rather than a continuous one?

Related to this:

  What are the drawbacks, or invariants, that are violated in structuring data as a continuous entity in $r$ dimensions?

I am not an expert in the field as I am an undergrad math student, so I'd really appreciate it if someone would explain this to me like I'm five.

Answer

  why was the data considered to be a discrete mathematical entity rather than a continuous one

This was not a choice; it is theoretically and practically impossible to represent continuous, concrete values in a digital computer, or actually in any kind of calculation.

Note that "discrete" does not mean "integer" or something like that. "discrete" is the opposite of "continuous". This means, to have a computer that is truly able to store non-discrete things, you would need to be able to store two numbers a and b where abs(a-b) < ε for any arbitrarily small value of ε. Sure, you can go as deep as you want (by using more and more storage space), but every (physical) computer always has an upper bound. No matter what you do, you can never make a (physical) computer that stores arbitrarily finely resolved numbers.

Even if you are able to represent numbers by mathematical constructs (for example π), this does not change anything. If you store a graph or whatever that represents a mathematical formula, then this is just as discrete as anything else.

Addendum

The rest is just a little perspective beyond the field of computer science. As the comments have shown, the physical topic is not undisputed, and as you can see I have formulated my next paragraph in a way that is rather uncommitted to whether it's true or not. Take it more as a motivation that the concept of "continuum" is not a trivial one. The answer given above does not depend on whether space is discrete or not.

Note that all of this is not so much a problem of computers, but a problem with the meaning of "continuous". For example, not everyone even agrees, or did agree in the past, that the Universe is continuous (e.g., Does the Planck scale imply that spacetime is discrete?). For some things (e.g., energy states of electrons and many other features in Quantum (sic) Mechanics) we even know that the Universe is not continuous; for others (e.g., position...) the jury is still out (at least regarding the interpretation of research results...). (Notwithstanding the problem that even if it is continuous, we could not measure to arbitrary precision => Heisenberg etc.).

In mathematics, studying the continuum (i.e., the reals) opens up a lot of fascinating aspects, like measure theory, which makes it utterly impossible to actually store a "continuous" kind of number/data.


Any ideas on implementation of a certain image process? I recently found this music video. While the music is mislabeled, the video part caught my eye. It seems to be transitioning between two images based on shape? I think its a fade-in/fade-out with the images being streched and transformed, but it seems to be specific on the shape in the image. This may be manual, but anybody have ideas on how one might go about something like this automatically? I was thinking it could be possible if you find the "flow" of an image by assigning pixels vectors based on their color compared to their neighbor's colors.

The first effect that appears at the video is a hue change. Later this is morphing, which is a feature based operation.

It seems like some similarity between images is used to set the morphing points (looking at the consecutive changes the points that do not move are chosen separately per transition).

The part of comparing two images (your last sentence) is used to make transition smoother, otherwise it would resemble warp. This is known as the Temporal Coherence, another technique includes Structural Similarity. Techniques yielding the best results are semi-automatic or manual due to a big complexity involved in finding smooth, minimal transition well perceived by people and also lack of good formula evaluating "how natural" transition looks like. The optimal transition calculated as minimal sum of changes does not yield nice looking morphing.

Sometimes a motion blur is added on top of the morphing (between patches) to make transition look better.


Piecewise linear approximation for set of points If we have a set of points $A$ and a known algorithm $Bestfit(A)$ to find
the best-fit straight line-segment through $A$, what would be a good algorithm to construct piece-wise linear segments (with at most $k$ segments) to give a better approximate of the set of points and reduce the error $E$?

This can be solved with a straightforward dynamic programming algorithm.  If you have $n$ data points, it can be solved in $O(n^2)$ calls to BestFit plus $O(n^2 k)$ time.  See https://cs.stackexchange.com/tags/dynamic-programming/info for our resources on how to construct dynamic programming algorithms.


Given three languages L1 L2 L3 that do not intirsect could one be TR and the other TD and the third neither where $L_{1} \cup L_{2} \cup L_{3} = \sum^{*}$ and

$L_{1} \cap L_{2} = \emptyset$ and $L_{2} \cap L_{3} = \emptyset$ and $L_{1} \cap L_{3} = \emptyset$

is it possible that $L_{1}$ is decidable, $L_{2}$ is recognizable but not decidable

and $L_{3}$ is not recognizable?

If so please give an example, if not why?

By recognizable I mean Turing Recognizable.

To make things a little easier (I think!) I have reached a conclusion that it is very much possible, I only can't think of an example of such 3 languages.

Is is indeed possible.

Consider the halting problem set $$H = \big\{ \big(\langle M \rangle, w\big): M \big( w \big) \space halts \big\}$$

and its complement $$\overline{H} = \big\{  \big(\langle M \rangle, w\big): M \big( w \big) \space doesn't \space halt \big\}$$

We know that H is recognizable and not decidable. That means that $$\overline{H}$$ is not recognizable because, otherwise, H would be decidable.

Now take $$L_1 = \emptyset \space \big( decidable \big) $$ $$L_2 = H \space \big( recognizable \space and \space not \space decidable \big) $$ $$L_3 = \overline{H} \space \big( not \space recognizable \big)$$

We have that $$L_1 \cup L_2 \cup L_3 = \Sigma^*$$ and
$$L_1 \cap L_2 = L_2 \cap L_3 = L_1 \cap L_3 = \emptyset$$


Why the Call instruction in the x86 architecture saves the return address as EIP+5 instead of 4? In 'The Computer Organization and design book' it illustrates the call instruction as

Decrementing the stack pointer by 4.
saving the EIP+5 into the stack.
Jumps to the new address specified.

What I know already is the instructions in this architecture are not typically all 4 byte in length, Hence.

How do we standardize the EIP to be added by 5 to the next instruction ?

normally in the MIPS architecture throughout the rest of the book the EIP is incremented by 4 which is intuitive as all the instructions are 32 bits.

Not sure which book you are referring to (isn't that book talks only about MIPS and not on x86?)

In any case, I think that the answer is the following:
EIP+5 is the address of the next instruction.
That is, in x86 the next instruction after a (near32) call is 5 bytes away. This is because the call takes 5 bytes:
1byte = the call opcode (E8, for a (near)rel32 call)
4bytes = the 32bit offset to the call target from current EIP.

That is, the new EIP (after the call) is computed by taking the current EIP and adding to it the 4bytes relative offset.

So, if the call instruction itself takes 5 bytes, then the next instruction (the return address) is at EIP+5.

See also https://c9x.me/x86/html/file_module_x86_id_26.html for all possible calls (I described the rel32 one).


Is every subset of a RE language also RE, in general? I'm trying to understand the question in my title in an intuitive way:
If I have an RE language A, then some TM, say TM(A) accepts on it. If I take a subset of A, say A2, then all elements of A2 will cause TM(A) to halt in the accept state.

However, is it in general possible to then create a TM for A2, say TM(A2), such that A2 is the max possible set that halts TM(A2) in the accept state. Thus making A2 its language - and would this language be RE?

Thanks

No, it is not true that every subset of a recursively enumerable (RE) language is also RE. In fact, it make sense to say that a subset of a RE language is not RE more often than not.

For an example, let us consider the RE language, $\Sigma^*$ that contains all words. It is the language of the Turing machine which always halts and accepts in its first step. Note that every language is a subset of $\Sigma^*$. Every language that is not RE is an example.

Here are a few exercises for you to check.

Exercise 1. Is every subset of a regular language regular?

Exercise 2. Is every subset of a context-free language context-free?

Exercise 3. Is every subset of a recursive language recursive?


Perfect Matching in Bipartite Graph with mutually exclusive edges Problem

I would to solve Perfect Matching in Bipartite Graph Problem where some edges are mutually exclusive.

Example

Left vertices: $a,b,c$

Right vertices: $x,y,z$

Edges: $(a,x),(a,y),(b,z),(c,y)$

Exlusive pairs: $(b,z)$ and $(c,y)$

Answer: no perfect matching

Question

Is the problem in P or NP?

Solution Attempts

I know that Perfect Matching in Bipartite Graph Problem is in P. But I cannot find a polynomial-time algorithms for the above version of this problem. I have also tried proving that it is NP, but without any luck.

It is $NP$ as $SAT$ can be polynomially reduced to this problem.

Let clauses be the left part vertexes, and literals be the right part vertexes. Draw an edge $(x,y)$ iff clause $x$ contains literal $y$. Finally, a pair of edges $(x_1, y_1)$ and $(x_2, y_2)$ will be exclusive iff $y_1$ corresponds to literal $a$ and $y_2$ corresponds to literal $\overline{a}$.


Is there some mathematical properties of the distribution which is the output of a probabilistic polynomial-time Turing machine? Let $S_{n}$ be an input set whose elements are length $n$, namely $S_{n} = \Sigma^{n}$. For every probabilistic polynomial-time algorithm $A$ and any $u \in \Sigma^{*}$, there exists a function $f^{A}$ such that $f^A(u) = \mathrm{Pr}[A(u) = 1]$. And let $f^{A}_{n} = \left.f^{A}\right\vert_{S_{n}}$ be a function from $S_{n}$ to $[0,1]$.

Is there some properties about what $f^A_n$ looks like? Or is there some references that introduce about this?

Indeed, let $F_{n} = \{ f^{A}_n \mid A \text{ is a PPT algorithm} \}$. And if we define
$$\mathrm{Dist}_{n}(f^{A},f^{B}) = \sum_{u \in S_{n}} \left\vert f^{A}(u) -
 f^{B}(u)\right\vert$$
and
$$d_{1}(n) = \inf \{ \mathrm{Dist}_{n}(f^{A},f^{B}) \mid f^{A} \neq f^{B} \}$$
how does $d(n)$ grow?

How about
$$d_{2}(n) = \sup_{g} \inf_{A} \mathrm{Dist}_{n}(f^{A},g)$$
where $g$ is a function from $\Sigma^{*}$ to $[0,1]$.

Given a probabilistic algorithm $A$, define $f^A(x)=\Pr[A(x)=1]$. To make the question interesting, you have to ask whether $f^A$ (with polynomial $A$) can be close to $g$, for infinitely many values of $n$. Otherwise, as Raphael mentioned, you can pretty much obtain any $g:\Sigma^n\rightarrow [0,1]$, while keeping $A$ polynomial (there is no asymptotics). Consider the problem of how $dist_n(f^A,g)=\sum\limits_{x\in S^n}\left|g(x)-f^A(x)\right|$ grows as a function of $n$. Obviously $dist_n(f,g)\le 2^n$, and a random guessing $A$ achieves $dist_n(f^A,g)\le 2^{n-1}$, can we find a probabilistic polynomial algorithm $A$ such that $dist_n$ grows polynomialy?

Let $L\subseteq\Sigma^*$ be some language, and $f^L:\Sigma^*\rightarrow \{0,1\}$ be its indicator function, i.e. $f^L(x)=1\iff x\in L$.
If for large enough $n$ it holds that $\sup\limits_{x\in\Sigma^n}\left|f^L(x)-f^A(x)\right|\le\frac{1}{2}-\epsilon$, then $\mathsf{L\in BPP}$ (simulate $A$ several times and take the majority vote, this works for $\epsilon=n^{-d}$). If for large enough $n$ you have $\sum\limits_{x\in\Sigma^n}\left|f^L(x)-f^A(x)\right|\le poly(n)$, then $\mathsf{L\in P/Poly}$, since your advice can contain information about all strings $x\in\Sigma^n$ on which $f^L,f^A$ differ by more than (say) $\frac{1}{3}$, and on the rest of the strings you can take the majority vote as above.

Thus, to answer your question, if $g$ is an indicator function for a hard language, you can expect (under some hardness assumptions) that there is no probabilistic polynomial time algorithm $A$ for which $Dist_n(f^A,g)$ is polynomial in $n$.


Clock page replacement algorithm - Already existing pages When simulating the clock page replacement algorithm, when a reference comes in which is already in memory, does the clock hand still increment?

Here is an example:

With 4 slots, using the clock page replacement algorithm

Reference list: 1 2 3 4 1 2 5 1 3 2 4 5

Initial list would look like this:

-> [1][1]
   [2][1]
   [3][1]
   [4][1]

The next reference to insert would be 1, then 2. Would the hand still point at 1 after 1, and after 2 ? In other words, after inserting the 5, would the clock look like this :

-> [5][1]
   [2][0]
   [3][0]
   [4][0]

?


Clock synchronization in a network with asymmetric delays Assume a computer has a precise clock which is not initialized. That is, the time on the computer's clock is the real time plus some constant offset. The computer has a network connection and we want to use that connection to determine the constant offset $B$.

The simple method is that the computer sends a query to a time server, noting the local time $B + C_1$. The time server receives the query at a time $T$ and sends a reply containing $T$ back to the client, which receives it at a time $B + C_2$. Then $B + C_1 \le T \le B + C_2$, i.e. $T - C_2 \le B \le T - C_1$.

If the network transmission time and the server processing time are symmetric, then $B = T - \dfrac{C_1 + C_2}{2}$. As far as I know, NTP, the time synchronization protocol used in the wild, operates on this assumption.

How can the precision be improved if the delays are not symmetric? Is there a way to measure this asymmetry in a typical Internet infrastructure?

Inability to measure asymmetry

No, you can't measure the asymmetry. Consider these two communication diagrams, the first with a negative clock offset and equal delays and the second with no clock offset and entirely asymmetric delays (but the same round trip time).

The important thing to notice is that, from the perspective of both the PC and the server, the two interactions are exactly identical. They receive messages at the same time. They send messages at the same time.

You can create more cases by 'grabbing' the PC timeline and 'sliding' it, holding the message send/receive points fixed relative to their respective timelines. The asymmetries you cause are exactly negated by the clock offset. In fact, you can even make messages go BACKWARDS IN TIME one way (as long as the round trip time is still the same) and the server/client STILL can't tell!

Therefore it is impossible to measure latency asymmetries. In the worst case, where you have no information other than that one way latencies are positive and sum to the round trip time, the accuracy of clock synchronization is limited to the round trip time.

Can intermediate infrastructure help?

Whether or not the intermediate infrastructure can help will be heavily dependent upon your theoretical model of the situation.

If the asymmetry is constant and the intermediate infrastructure is the routers on the communication path between you and the server, then no. Even if each router synchronized their clock with the adjacent router, the errors would compound in the same way as if you had synchronized with the server via communication across the routers.

In the real world you can rely on delays being somewhat symmetric for architectural reasons, repeated synchronizations to reduce asymmetry due to queuing delays (etc), and multiple communication paths to reduce other sorts of asymmetry.

If you put your model's assumptions somewhere in between (because it's interesting to explore model space, of course) I expect the result should also be somewhere in between.


Determine whether two collections of items can be paired Given collections I (items) and S (slots), where I >= S.
And a pairing function that determines whether a slot can accept an item.

Is there an efficient way to find whether a "complete" pairing of items to slots exist, where "complete" means every slot is filled?

(More importantly for my use case... is there a way, other than trying every combination, to determine if no such pairing exists?)

Yes. You're just looking for a maximum matching in the bipartite graph where one side is the items, the other side is the slots and there's an edge between an item and each slot it's compatible with.

There are a number of efficient algorithms for this. The standard method taught to CS undergraduates is the augmenting paths algorithm of Hopcroft and Karp.


Is a 2 address machine more likely to follow a RISC or CISC design? The Problem: If I have a 3 address machine, is my machine more likely to follow RISC or CISC design?  2 addresses?  1 address?  0 address.

To solve this problem I first looked up the different terms.

RISC is a microprocessor architecture that has smaller/simpler set of instructions
CISC is a microprocessor architecture that has larger/more complex set of instructions
3, 2, 1 address machines just mean how many addresses are in an instruction

When first investigating the relationship between RISC vs CISC and n-address machines, with the help of the slide below, I was able to quickly associate 3 address with CISC and 0 address with RISC.

I saw that 3 address instructions were much more complicated than 0 address and therefore would make sense for CISC design. Similar reasoning for 0 address machine and RISC design. How would you make the distinguish for CISC and RISC with the address sizes in the middle - 1 and 2?

The problem is that the terms RISC and CISC are marketing terms, not science or engineering terms.  The terms are supposedly acronyms for "Reduced Instruction Set Computing" and "Complex Instruction Set Computing."  Your assumption that 3 addresses is much more complicated than 0 addresses is logical, but there is no logic here, and typically 3-address instructions are associated with RISC and 2-address instructions are associated with CISC (and 1-address and 0-address instructions aren't very common any more, so aren't associated with either RISC or CISC).

The term RISC is generally associated with instruction sets that have the following characteristics:

Fixed width instructions.  Usually 32-bits or 16-bits.  This makes it easier for the instruction decoder to find the boundaries between instructions.  In CISC machines, by contrast, the different instructions can range in length from 8-bits to as much 64-bits.  This makes the job of the instruction decoder somewhat harder in CISC machines, but can result in programs consuming less memory.
Fewer operand addressing modes.  In a RISC machine typically each operator (add, sub, jmp, load) has only one available addressing mode for its operands (the a, b, c, d, and e in your picture.)  Typically for arithmetic type instructions (add, sub, xor, ...) the only available addressing mode is register direct.  The source operands are found in registers, and the result of the computation can only be placed in a register. Load and store type instructions typically have one operand that is register direct and the other operand is register indirect plus offset.  Jump and branch type instructions will typically have a target operand that is pc relative.   There will typically also be a few jump and branch type instructions with a register indirect target, and sometimes a jump instruction with an absolute target operand.  The smaller number of operand addressing modes is typically the only way in which "RISC" instruction sets are actually reduced (compared to "CISC" instruction sets).  The reasoning, again, has to do with trying to keep the instruction decoder as simple as possible in RISC machines.  The simple operand addressing modes are easier to implement in a simple pipeline, and so the decoder in modern CISC machines often has to do extra work to crack instructions with complex operand modes into sequences of micro-operations that are more like RISC instructions.
There is a tendency for RISC architectures to have more register names available.  Many RISC architectures have 32 registers, while many CISC architectures have only 8 or 16.  This again has to do with making it somewhat simpler to exploit instruction-level parallelism with a simple pipeline.  Having more available register names makes it possible for the compiler to use different register names for unrelated computations, without requiring the hardware to do register renaming.
RISC architectures tend to have "3-address" instructions, while CISC architectures tend to have mostly "2-address" instructions.  The notion of "3-address" vs. "2-address" is also somewhat fuzzy (and somewhat mis-named).  Every add instruction has 3 operands, 2 source operands and 1 destination operand.  The real distinction is whether those operands are explicit or implicit.  In a so-called "3-address" instruction you make all 3 operands explicit.  In a so-called "2-address" instruction you make the destination operand explicit and one of the source operands explicit.  The third source operand is implicit: it is always the same address as the destination operand.  In a so-called "1-address" instruction only one of the source operands is explicit.  The other source operand is implicitly either an accumulator register or the top of the stack, as is the destination operand.  Finally in a "0-address" instruction all the operands are implicit (usually the two source operands are the top two values on the stack and the destination goes back on the top of the stack.)

To sum up: these are all marketing terms, and don't really mean much.  The important concepts have to do with the relationship between different instruction-set design choices and how those choices make it easier or harder to implement hardware pipelines.


Quick Sort Equal to or Less Than For my course I have to memorise a number of algorithms and to know how to perform them by hand. The steps of the quick sort are given as the following in the text book I am using:

Choose the item at the midpoint of the list to be the first pivot
Write down all the items that are less than the pivot, keeping them in order, in a sub-list
Write down the pivot
Write down the remaining items (those greater than the pivot) in a sub-list
Apply steps 1 to 4 to each sub-list
When all items have been chosen as pivots, stop

The problem is that these instructions are ambiguous as to what to do if there is an item which is equal to the pivot. Does it fall into the first sub-list (written before the pivot) or the second (written after the pivot)? I assume that there is some sort of agreed upon standard for this.

It doesn't really matter which way you decide to break the tightness. You could put all the elements less than or equal to the pivot in the first list and the ones larger than the pivot in the second list, or you could put only the elements smaller than the pivot in the fist list and the ones larger than or equal to the pivot in the second list.

You could even arbitrarily pick the list that will contain an element equal to the pivot (except the pivot itself), on an element-to-element basis. No matter how you will assign these elements to the lists, the algorithm will still work.

Another solution that slightly breaks the algorithm's description you gave is to put all elements smaller than the pivot in the first list $L_1$, all those larger than the pivot in the second list $L_2$, and insert as many copies of the pivot $x$ as there are elements equal to $x$ (including the pivot itself) between the sorted versions of $L_1$ and $L_2$.

As a final note: the pseudocode reported in your textbook seems wrong. You are supposed to recursively repeat the whole procedure on $L_1$ and $L_2$, not just steps $1$ to $4$ (otherwise you will never reach a recursion depth larger than $1$).


P vs NP: Assuming P = NP Lets assume $P = NP$. Can we say if every language $L \in P$, then $L \in NPC$?

I read $P \subseteq NP$, which means that $L\in NP$. So I know for example, that a language can be $NP \text{ hard}$, but it doesn't have to be in $NP$, e.g. $HALT$.

But what about the case above. Is the language also $NPC$?

Yes.  Every* problem in $P$ can be reduced to any other problem in $P$ using polynomial-time reductions (since the reduction is allowed to do polynomial work, it can just solve the problem itself).

If $P=NP$, then it follows that every* problem in $NP$ can be reduced to any* other problem in $NP$ -- in other words, every* problem in $NP$ is $NP$-complete.  This implies that if $L \in P$ and if $P=NP$ then* $L$ is $NP$-complete.

Footnote *: There is an exception for the empty language ($\emptyset$) and the universal language ($\Sigma^*$).  For purposes of gaining a rough conceptual understanding, this technical detail can probably be safely ignored.


Determining if $G$ contains $K_4$ as a minor in polynomial time I am trying to devise an algorithm for determining if an undirected graph $G$ contains $K_4$ as a minor. I was able to show in a previous problem how to test for $K_{2,3}$ by looking at all pairs of vertices and applying Menger's problem as a black-box on that pair of vertices (i.e checking for at least 3 vertex-disjoint paths). This gave an, although naive, $O(n^3)$ algorithm. However, the same trick doesn't seem to work for $K_4$, since the same type of structure cannot be exploited. How can one test for $K_4$?

I am also wondering what the best possible algorithm for $K_{2,3}$ and $K_4$ testing might be.... I seriously doubt that the brute-force approach highlighted above is optimal. Is there a known lower-bound?

I think your best bet would be to implement a treewidth 2 algorithm.  We implemented one for an android app and you can find the source code of this specific implementation here: Treewidth.  You can probably modify it to run in $O(n^4)$ time.


Compression of Memoryless Sources Are there any compression algorithms outside of entropy encodings that yield a significant compression ratio for memoryless sources (not the Markov kind, but this kind)?

More concretely, if a million ASCII characters, each generated from the same probability distribution that is not necessarily even but where the probability of each ASCII character being chosen is non-zero, what compression algorithms outside of entropy encoders (such as arithmetic, huffman) would yield decent compression ratios?

You've eliminated entropy encoders, which is the type of data you described.

A Memory-less Markov is a contradiction of terms.

The best Compression possible for the specifically generated list of characters, might just be the program that is used to generate the deterministic data in the first place.


Is this statistical group summation unambiguously reversible? Let $X$ be a finite multisubset of $\mathbb{N}^2$. Let's introduce the following notation:
$A$ is a set of all first elements of pairs from $X$ and $B$ is a set of all second elements of pairs from $X$.
$cnt_1(n) = |\{(n,  b)|(n, b) \in X\}|$ (that is a number of elements in a corresponding set).
$cnt_2(n) = |\{(a,  n)|(a, n) \in X\}|$
$sum_1(n) = \sum_{(n,b) \in X}b$
$sum_2(n) = \sum_{(a,n) \in X}a$
$Y=\{(a, cnt_1(a), sum_1(a))|a \in A\}$
$Z=\{(b, cnt_2(b), sum_2(b))|b \in B\}$
The question: Given only $Y$ and $Z$ is it always possible to unambiguously reconstruct $X$?

Equivalently, phrased in terms of SQL: Given an (unordered) set of 2-tuples (X) of natural numbers:
CREATE TABLE X (
    a int,
    b int
);

the following statistical summaries and are derived:
Y:
SELECT a, COUNT(1) AS ca, SUM(b) AS bs FROM X GROUP BY a ORDER BY a;

Z:
SELECT b, COUNT(1) AS cb, SUM(a) AS as FROM X GROUP BY b ORDER BY b;

Is it possible to unambiguously re-construct X when knowing only Y and Z?

The answer is no . I found it helpful to think of the information in the form of a picture: mark each pair $(a, b)$ as a point on a grid, then in each column and row write both the count of the entries in that row, and the "sum" of the entries (the sum of the 'other' coordinate). Your example may be pictured as follows:

I'm writing the count of the dots in each row/column as the number closest the the column, and the "sum" as the number further away. The original data is the set of dots, the new data are Y and Z (understood to not just be sets of points, but to be positional: for example we remember that in the $Y$ data we have $(2, 3)$ in column $1$, $(1, 3)$ in column 2, and so on).
Here are two configurations of points with equal $Y$ and $Z$ data:

Hence the operation is not reversible. Per-column ambiguity arises when there are multiple integer partitions with the prescribed number of parts: eg if a column counts to 2 and sums to 5, its possible entries are 1 + 4 or 2 + 3.


How to determine if a database schema violates one of the less known normal forms? In database normalization, 1NF (no multivalued attributes), 2NF (all non-PK attributes depending only on PK attributes) and 3NF (all non-PK attributes depending on all of the PK attributes) are widely known. The 4NF (no part of the PK depending on other part of the PK) is less known, but still reasonably known.

Much less known are the 5NF, 6NF and the intermediates EKNF (Elementary Key normal form), BCNF (Boyce-Codd normal form - 3.5) and DKNF (Domain/Key normal form - 5.5). What exactly are that? Given a database schema, how do I determine if any table violates one of these much less knows normal forms?

From Wikipedia:

  1NF: The table faithfully represents a relation and has no repeating
  groups.

  2NF: Non-prime attributes are non functionally dependent on a proper
  subset of a candidate key.

  3NF: Non-prime attributes are non-transitively dependent on every
  candidate key in the table.

  BCNF: Every non-trivial functional dependency is a dependency on a
  superkey.

  4NF: Every non-trivial multivalued dependency in the table is a
  dependency on a superkey.

  5NF: Every non-trivial join dependency in the table is implied by the
  superkeys of the table.

  DKNF: Every constraint in the table is a logical consequence of the
  table's domain and key constraints.

Please let me know which, if any, of these requires further explanation. Each provides a means of checking whether a table is in the normal form.

EDIT: Again from Wikipedia:

  A join dependency is a constraint on the set of legal relations over a
  database scheme. A table $T$ is subject to a join dependency if $T$
  can always be recreated by joining multiple tables each having a
  subset of the attributes of $T$. If one of the tables in the join has
  all the attributes of the table $T$, the join dependency is called
  trivial.

  The join dependency plays an important role in the Fifth normal form,
  also known as project-join normal form, because it can be proven that
  if you decompose a scheme $R$ in tables $R_1$ to $R_n$, the
  decomposition will be a lossless-join decomposition if you restrict
  the legal relations on $R$ to a join dependency on $R$ called
  $*(R_1,R_2,...R_n)$.

In other words, if a constraint on your table $T$ is that T = R JOIN S for some tables $R$ and $S$, then $T$ has a join dependency $*(R, S)$.


Primality testing: Why is dividing a number $n$ by every integer between 2 and $\sqrt{n}$ an inefficient test? In the paper "PRIMES is in P" the following is said (page 1):

  Let PRIMES denote the set of all prime numbers. The definition of prime numbers already gives a way of determining if a number $n$ is in PRIMES: try dividing $n$ by every number $m \leq \sqrt{n}$ — if any m divides $n$ then it is composite, otherwise it is prime. This test was known since the time of the ancient Greeks — it is a specialization of the Sieve of Eratosthenes (ca. 240 BC) that generates all primes less then $n$. The test, however, is inefficient: it takes $\Omega (\sqrt{n})$ steps to determine if $n$ is prime. An efficient test should need only a polynomial (in the size of the input = $\lceil \log n \rceil$) number of steps.

Firstly, isn't complexity $\sqrt{n}$ already polynomial?

Secondly, why would complexity $\lceil \log n \rceil$ represent an efficient algorithm? This seems somewhat arbitrary to me.

The complexity is measured as a function of the size of the input.
You don't have here an array of $n$ numbers but a number $n$.
 The size of the input is $O(\log n)$ (to store a number $n$ you need $\lfloor log_2(n) + 1 )\rfloor$ bits).
Hence, $O(\sqrt n)$ is not polynomial in the size of the input.

The answer to the second question is a direct consequence. Since the size of the input is logarithmic in $n$, an algorithm with logarithmic time complexity with respect to $n$ (and therefore, polynomial wrt the size of the input) would be efficient.

As an example, consider a number $M$ of size $n$, an algorithm with time complexity $O(log^k M)$ for a constant $k$, corresponds to a polynomial time algorithm (in the size of the input) of time complexity $O(n^k)$.


Minimization of idle time with two kinds of actors Let's say I have 2 different types of machines responsible for 2 different duties.

I have the PRODUCTION_MACHINES that EACH are able to produce a single unit of goods within 2 hours.

Then I have TRANSPORTER_MACHINES which are EACH able to collect and package away a single unit of goods from the production line at 95 seconds per TRANSPORTER_MACHINE.

QUESTION:

Assuming there are 5 PRODUCTION_MACHINES working, and they are operated at different starting times, how many TRANSPORTER_MACHINES do you need in order to MINIMIZE the IDLE_TIME incurred in the production process ?

(Whereby "IDLE_TIME" is defined as the time expended by EITHER the PRODUCTION_MACHINE or a TRANSPORTER_MACHINE waiting to have its good collected or produced.

HINT: Too many TRANSPORTER_MACHINES will add to the idle time as there are prone to be extra TRANSPORTER_MACHINES idly waiting for struggling PRODUCTION_UNITS to produce quickly enough to keep up with DEMAND.

... and vice-versa, too few TRANSPORTER_UNITS will also increase the idle time, this time for the PRODUCTION_MACHINES as some of them will have to wait for the struggling TRANSPORTER_MACHINES to keep up with their SUPPLY.)

Thank you very much !

Observe that it takes a PM about 75 times as long to produce a widget as it takes a TM to clear that widget and let it start producing the next widget. And we have only 5 PMs.

Intuitively, it seems like we should have only one TM. It will be idle almost all the time, waiting for one of the PMs to finish. The PMs will be busy almost all the time, except right after they finish a widget and have to wait for the output to be cleared away.

Adding more TMs would simply add more idle time for them, while reducing the PM idle time by very little at best. Removing the sole TM would leave all of the PMs idle as soon as each of them finishes the first widget.

If the times were more similar, or the number of PMs were closer to 75, finding the answer would be more complex. This problem seems to be designed for a simple, intuitive answer.


Interleaving algorithm for 2 stacks Suppose I have two stacks $<a_1,a_2,...a_m>$ and $<b_1, b_2,...b_n>$ and a third stack of size $m+n$.
I want to have the third stack in the following manner, $$<a_1,b_1,a_2,b_2,...a_n,b_n...a_m-1,a_m>$$ for $$m>n$$
This was easy to do if the two initial stacks were not size constrained. But if the two stacks are size constrained, I am in a fix.

Is it even possible to interleave the elements of the two stacks into a third stack in constant space? Also what would be the minimum number of moves to do this? I know using recursion this can be reduced to Tower of Hanoi variant, but what about a non-recursive algorithm?

Note: I found a better technique which I give in a separate answer, which is more general, faster and simpler, though the complexity results remain somewhat similar. I chose to leave this answer rather than replace it, as it may be interesting to compare, and both solutions were too long for a single answer.

Let A, B and C be the three stacks.
I assume that the top of A and B are on the small index side.

I note (X,Y,p) the transfer of p elements from the top of X to the top
of Y. This has of course the effect of inverting the order of these p
elements, and has a cost p.

Let q and r the quotient and remainder of the integer division of m by
n. Thus m=q*n+r.

Pseudocode for the interleaving

% transfer of the m-n unmatched tail by chunk of n elements
For i from 1 by 1 to q-1 do
  % transfer the bottom n elements remaining in A
  (B,C,n)
  (A,C,m-i*n)
  (A,B,n)      % bottom n
  (C,A,m-i*n)
  (B,C,n)      % bottom n
  (C,A,n)      % bottom n
  (C,B,n)
  (A,C,n)      % bottom n
  end loop
if r≠0 then
  % transfer the remaining r elements of the umatched tail
  (B,C,n)
  (A,C,n)
  (A,B,r)      % bottom r
  (C,A,n)
  (B,C,r)      % bottom r
  (C,A,r)      % bottom r
  (C,B,n)
  (A,C,r)      % bottom r
  end if

% Now we have transferred the extra elements of A at the bottom of C.
% We have only 2n slots available in C, for intertwining A and B.
% But we have m-n free slots in A.

(A,C,n)   % rest of A inverted in C
(B,A,n)   % B inverted in A
k=n       % number of remaining elements of each stack still to be transferred
t=m-k     % available space in A to do the transfer
while k>0 do
  t=min(k,t)
  (C,A,t)   % last t of A in direct order in A
  (C,B,k-t) % top rest of A in B in direct order
  (A,B,t)   % last t of A inverted in B
  For i from 1 by 1 to t do    % intertwin in C last t elements of remainder
    (A,C,1)
    (B,C,1)
    end loop
  (B,C,k-t) % top rest of A inverted in C
  k=k-t
  t=2t
  end  loop

Complexity

I am only counting the number of moves. It actually gives the
complexity since the control statements introduce only a constant
factor on the moves and the number of moves is polynomial.

For one iteration of the first loop : $6n+2(m-i\times n)$

Hence the cost of the loop is $\sum_{i=1}^{q-1}6n+2(m-i\times n)$
= $(q-1)(6n+2m)-2nq(q-1)/2$ = $(q-1)(6n+2m-nq)$ = $(q-1)(6n+2m-(m-r))$
= $(q-1)(6n+m+r)$

The cost of the following conditional is at worst $4(n+r)$

So the total cost for the last $m-n$ elements of stack A is majored by
$q(6n+m+r) \leq q(7n+mn/n) \leq 7m+m^2/n$

The cost of transferring the tail of A is quadratic in $m$ when $n$ is
constant, as B becomes too small with increasing values of $m$ to do
the tranfer in a fixed number of passes over the whole stack. The
linear decrease of the remaining part to be transferred does not help
enough.

Things are however better with the parts of the two stacks that must
be intertwined.

There is a first cost of $2n$.

The cost of one iteration of the loop is $2t+2(k-t)+2t$, the cost of
the inner loop being $2t$. So this makes a total of $2(k+t)$.

If $m\geq 2n$ then the loop is executed only once, with $k=t=n$, hence
the cost is $4n$. Note that $4n\leq 2m$ in this case.

Otherwise we start the loop with $k=n$ and $t=m-n$, so that we
have $k+t=m$. But the update k=k-t; t=2t at the end of the loop
preserve this property as an invariant. So each iteration actually
costs $2(k+t)=2m$, except possibly the last one, since $t$ may be
reduced by the statement t=min(k,t), thus lowering the cost of that
last iteration. Note that, in this case, $2m\leq 4n$.

Since $t$ doubles at each iteration, but will not be greater than $n$,
the number of iterations is at worse $1+\log_2 n$, when $t$ starts with
value 1. Note that there must be at least one iteration when $n=1$
(though it could be simplified), in which case $\log_2 n=0$.

But the initial value of $t$ is actually $min(n,
m-n)$. Since it would take $\log_2 min(n, m-n)$ iterations to reach that value,
starting from 1, the actual number of iterations is $1+\log_2 n - \log_2
min(n, m-n) = $1+log_2 \frac{n}{min(n, m-n)}$

Hence the total cost for this part is less than $2n+4n(1+\log_2 \frac{n}{min(n, m-n)})$

So, the overall complexity in stack moves is $O(m^2/n+n(1+\log
\frac{n}{min(n, m-n))})$

In particular the complexity is linear in $n$ or $m$ when the ratio
$h=m/n$ remains constant.

This is obvious for the first term $m^2/n=h^2n$.

For the second term,  we have
$min(n,m-n)=min(n,n(h-1))=n min(1, h-1)$. Hence $n(1+\log
\frac{n}{min(n, m-n))})= n(1+\log\frac{1}{min(1, h-1))})$


Closure of regular languages under permutation Given a regular language $L$ over the alphabet $\Sigma = \{a,b,c,d\}$, is the language $\mathrm{Perm}(L)$ consisting of all permutations of words in $L$ also regular?
My intuition says it is, since each word in $L$ only has finitely many permutations, but I don't know how to prove it.
Any help would be great.

You can consider the regular language $(ab)^*$. We have
$$ \mathrm{Perm}((ab)^*) \cap a^*b^* = \{ a^n b^n : n \geq 0 \}, $$
which isn't regular. If you take instead $(abc)^*$ and intersect with $a^*b^*c^*$, you get the language $\{ a^nb^nc^n : n \geq 0 \}$, which isn't even context-free.
In contrast, the class of context-sensitive languages is closed under permutation. To see this, it suffices to observe that you can nondeterministically permute the input without any additional space (for example, by applying an arbitrary number of transpositions).


How to improve the accuracy of automatic conflict resolution? A little background information from my previous question:https://english.stackexchange.com/questions/318528/conflict-resolution-how-to-decide-if-two-words-are-generally-unmistakable

When a court reporter strokes 2 different words with the same keys, this creates a conflict. Normally, the reporter will fix the error later, but sometimes there is a way for the court reporting software to fix the error for you. This can be referred to as automatic conflict resolution.

My court reporting software's system for accomplishing this is by recording the parts-of-speech before and after the conflicting words.

So for example, if my two conflicting words are Tallahassee and shake and I type the following sentences it will look something like this:

I eat at Tallahassee / shake all the time. (Prep - Determiner)

I eat a Tallahassee / shake all the time. (Article - Determiner)

At first it will make me choose between the two, but after I chose it will then automatically add its defined part of speech in a database, so that if I type something like this...

I eat in Tallahassee every afternoon. (Prep - Determiner)

my computer should correctly pick "Tallahassee" since I already told it that "Tallahassee" occurs after a Prep and before a Determiner. The rule for this is simply pos word pos

I tested the practicality of this conflict-resolution system with 79 random conflicts using parts of ANC's pos-tagged corpus and Excel VBA.

As the data shows, only 10 out of the 79 conflicts showed up with 0 collisions total. This means that in the entirety of the corpus, none of these conflicts had conflicting parts-of-speech which had caused an error.
36/79 conflicts showed up with 5 or less collisions.
32/79 had 10 or more collisions
Each collision represents 1 guaranteed error of real-time translation given the pos word pos rule (per the parsed text from ANC, which was about 4.5 million words long)

These results aren't very good for the kind of real-time accuracy I hope to achieve.  It would be much better if I could get at least 30/79 (as opposed to only 10) to have 0 "guaranteed errors."

How can I improve this system so that I will have fewer real-time translation errors?

My best thought is to change the rule from pos word pos to pos pos word pos in the case of a collision, but that's all I've got. I'm not very experienced on this subject, so I'm not necessarily opposed to the idea of starting over with something fresh.

There are many candidate approaches you could consider.  I would suggest you be creative about what features you could use, to make predictions about which candidate is more likely to be the intended one.

One approach is to use a language model for the prevalence of different phrases.  For instance, if $w, x$ are two words, define

$$r(x | w) = {P(w \; x) \over P(w) \times P(x)}.$$

(Here $P(w \; x)$ represents the prevalence of the 2-gram $w \; x$ in some large corpus, and $P(w)$ represents the prevalence of the 1-gram $w$ in the corpus.)

Now if the previous word is $w$ and the next word is either $x$ or $y$, compare $r(x | w)$ to $r(y | w)$ to see which is larger, and use that to resolve the conflict.

For example, comparing $r(\text{Tallahassee} | \text{at})$ to $r(\text{shake} | \text{at})$ using the Google n-gram viewer, we find that the former is much larger.  In particular, the former is $1.2 \times 10^{-6}/(0.3 \times 8.5 \times 10^{-5}) \approx 0.05$, while the latter is $4.8 \times 10^{-8}/(0.3 \times 9.7 \times 10^{-4}) \approx 10^{-4}$, which is much smaller.  We conclude that "Tallahassee" is much more likely to follow "at" than "shake", so the conflict should be resolved by the former.

You can generalize this to use any number of tokens of previous history (e.g., the previous 2 words instead of the previous 1 word).

Another approach would be to use something similar, but replace words with their parts of speech.

For instance, Google's n-gram viewer supports part-of-speech queries.  You can quickly see that "ADP Tallahassee" (basically, a preposition followed by Tallahassee) is more common than "ADP shake", so "I eat at" is more likely to be followed by "Tallahassee" than "shake".  In contrast, you can see that "DET shake" is more common than "DET Tallahassee"; so "a" (an article) is more likely be to be followed by "shake".


Minimize edges of a directed unweighted graph I need to find an algorithm to find a sub-graph $G'=(V, E')$ of a directed unweighted graph $G = (V, E)$ where for all $(u, v)\in E$ there exists a path in $G'$ from $u$ to $v$ and the size of $E'$ is minimal.

As an example, $(1, 2) (2, 3) (1, 3)$ reduces to $(1, 2) (2, 3)$. Additionally, $(1, 2) (2, 3) (1, 3) (3, 1)$ reduces to $(1, 2) (2, 3) (3, 1)$.

This is not an MST (or arborescence) problem since we care every vertex as a root hence Edmond's algorithm does not work.

I am clueless at this point. At least a hint is highly appreciated.

There is no polynomial-time algorithm for your problem, unless $\mathsf{P}=\mathsf{NP}$.

Let $H$ be a connected undirected graph with at least $2$ vertices and consider the directed graph $G$ obtained by replacing each undirected edge {u,v} of $H$ with the pair of directed edges $(u,v)$ and $(v,u)$.

If there is a Hamiltonian path traversing the vertices $\langle u_0, \dots, u_{n-1}, u_n = u_0 \rangle$ of $H$, in order, then the set of $n$ edges $\{ (u_i, u_{(i+1) \bmod n}) \mid i=0,\dots,n-1\}$ of $G$ induces a subgraph $G'$ with your property.

If there is a subgraph $G'$ of $G$ with at most $n$ edges that satisfies your property, then it must have exactly $n$ edges. Moreover the in-degree and the out-degree of each vertex must be exactly $1$, and the undirected version $H'$ of $G'$ must be connected. In other words $G'$ is a cycle that that traverses each vertex of $G$ exactly once, showing that $H'$ is a Hamiltonian path of $H$.


Why is the following language not context-free? $L = \{a^n b^m | m \not= n^2 \}$
I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck.

Assuming that $ a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ and $b$ symbols in them. Otherwise pumping would generate strings not of the form $a^i b^j$.

Hence both $v$ and $y$ must consist only of one kind of symbol each.
Beyond this I wonder what string in $L$ has to be chosen in order to pump and obtain something of the form $a^n b^{n^2}$.

Alternative idea : Assuming that $L$ is context-free, then I must have a PDA accepting it by final state. Can I say that this PDA can be adjusted* to accept $L'$ i.e., all $a^n b^{n^2}$ ? However I know that $L'$ is not a CFL. Hence, contradiction ?

*Adjusted = Make the non-final state on reading $a^n b^{n^2}$ as final and the rest as all non-final.

Your first approach is not very clear. What are $n$ and $m$? You have to fix a word in order to use the Pumping lemma; please see our reference question for how it's done.

Your second approach is fundamentally flawed as CFL is not closed against complement, i.e. your PDA construction does not work. Also, note that $L^c$ does not only contain words of the form $a^nb^{n^2}$, but also all that do not match $a^*b^*$.

Towards showing that $L$ is not context-free, note that $\mathrm{CFL} \cap \mathcal{L}(a^* b^*)$ is closed against complement (see here). Therefore, if $L$ was context-free so would be

$\qquad L' = \{a^n b^m \mid m = n^2\}$.

It is easy to show that $L'$ is not context-free by using the Pumping lemma.


What is the theoretical minimum number of "switches" requried to implement a Turing-complete CPU? Where "switches" are the basic abstract building blocks for logic gates: vacuum tubes, transistors, magnetic relays, or whatever. We're not counting any switches in the RAM or tape drive because that's a separate component.
I'm not sure if the exact number is known or provable, but an upper bound could be proven by implementing one or pointing to a known implementation.
I am assuming a binary computer with empty memory. You can, of course, load a program to make it work, but said program must be finite in length. Something like Wolfram's (2, 3) UTM, which requires the whole unbounded tape to be initialized, is out.
The first commercial microprocessor was the Intel 4004, with a transistor count of 2,250 (not sure if that's exact), so that's an upper bound.
But that already had a 4-bit data width and multiple opcodes, probably much more than is required for the theoretical minimum CPU. I have heard of 1- and 2-bit CPUs and one-instruction set architectures like Subleq, so I think we can do a lot better than the 4004. I suspect the true answer is < 1000 switches, but I'm not sure.

The Rule 110 cellular automaton is apparently Turing-complete.  If you're not counting the cost of memory, I imagine a circuit that applies the Rule 110 evolution rules could be implemented with very few switches.
See also https://softwareengineering.stackexchange.com/q/230538/34181.


Approximate subset sum with two-dimensional vectors Consider the following optimization problem:

  Given $n\leq 10^3$ vectors $v_i\in\mathbb{R}^2$, all of which are small, i.e., $\|v_i\| \leq 1$, find a subset $S$ of them that minimizes
  $ \| w + \sum_{i\in S} v_i \|^2$, where $w$ is a fixed known vector.

I know that this can be reduced to an unconstrained 0-1 quadratic program (with unknowns $x_i\in\{0,1\}$, $x_i=1$ whenever $i\in S$), but that is a hard problem in general.

However, since the constraints are so specific, is there a way to get a reasonably simple efficient approximation algorithm for it? One that doesn't involve integer programming? It's not even clear to me how to efficiently implement a greedy algorithm for it.

Are there special cases of this problem that are easier? For example, would it help if all the vectors were unit length, $\|v_i\|=1$?

Let $\rm V$ be the $2 \times n$ matrix whose $i$-th column is vector $\rm v_i$. We have the Boolean optimization problem in $\mathrm z \in \{0,1\}^n$
$$\min_{\mathrm z \in \{0,1\}^n} \| \mathrm V \mathrm z + \mathrm w \|_2^2$$
Let
$$\rm z = \frac 12 (x + 1_n)$$
where $\mathrm x \in \{\pm 1\}^n$. Hence, we have an instance of the Boolean least-squares (BLS) problem
$$\min_{\mathrm x \in \{\pm 1\}^n} \| \mathrm A \mathrm x - \mathrm b \|_2^2$$
where
$$\rm A = \frac 12 V \qquad \qquad \qquad b = - \left( \frac 12 V 1_n + w \right)$$
Since $\{\pm 1\}$ is the solution set of the quadratic equation $x_i^2 = 1$, we have the following (non-convex) quadratically constrained quadratic program (QCQP) in $\mathrm x \in \mathbb R^n$
$$\begin{array}{ll} \text{minimize} & \| \mathrm A \mathrm x - \mathrm b \|_2^2\\ \text{subject to} & x_i^2 = 1 \quad \forall i \in \{1,2,\dots,n\}\end{array}$$
Exhaustive evaluation of the objective function at all $2^n$ points is only feasible for small $n$.

SDP relaxation
Note that
$$\begin{array}{rl} \| \mathrm A \mathrm x - \mathrm b \|_2^2 &= (\mathrm A \mathrm x - \mathrm b)^{\top} (\mathrm A \mathrm x - \mathrm b)\\ &= \mbox{tr} \left( (\mathrm A \mathrm x - \mathrm b)  (\mathrm A \mathrm x - \mathrm b)^{\top} \right)\\ &= \mbox{tr} \left( \begin{bmatrix} \mathrm A & -\mathrm b\end{bmatrix} \begin{bmatrix} \mathrm x\\ 1\end{bmatrix} \begin{bmatrix} \mathrm x\\ 1\end{bmatrix}^{\top} \begin{bmatrix} \mathrm A & -\mathrm b\end{bmatrix}^{\top} \right)\\ &= \mbox{tr} \left( \begin{bmatrix} \mathrm A^{\top}\\ -\mathrm b^{\top}\end{bmatrix} \begin{bmatrix} \mathrm A & -\mathrm b\end{bmatrix} \begin{bmatrix} \mathrm x\\ 1\end{bmatrix} \begin{bmatrix} \mathrm x^{\top} & 1\end{bmatrix} \right)\\ &= \mbox{tr} \left( \begin{bmatrix} \,\,\,\, \mathrm A^{\top} \mathrm A & -\mathrm A^{\top}\mathrm b\\ -\mathrm b^{\top}\mathrm A & \,\,\,\, \mathrm b^{\top}\mathrm b\end{bmatrix} \begin{bmatrix} \mathrm x \mathrm x^{\top} & \mathrm x\\ \mathrm x^{\top} & 1\end{bmatrix} \right)\end{array}$$
Since $\mathrm x \in \{\pm 1\}^n$, all $n$ entries on the main diagonal of $\mathrm x \mathrm x^{\top}$ are equal to $1$. Thus,
$$\begin{bmatrix} \mathrm x \mathrm x^{\top} & \mathrm x\\ \mathrm x^{\top} & 1\end{bmatrix}$$
is symmetric, positive semidefinite and has only ones on its main diagonal, i.e., it is a correlation matrix. Its rank is $1$. Let
$$\mathrm C := \begin{bmatrix} \,\,\,\, \mathrm A^{\top} \mathrm A & -\mathrm A^{\top}\mathrm b\\ -\mathrm b^{\top}\mathrm A & \,\,\,\, \mathrm b^{\top}\mathrm b\end{bmatrix}$$
Hence, the BLS problem can be written as the following rank-constrained optimization problem in $(n+1) \times (n+1)$ symmetric matrix $\rm Y$
$$\begin{array}{ll} \text{minimize} & \langle \mathrm C , \mathrm Y \rangle\\ \text{subject to} & y_{ii} = 1, \quad \forall i \in \{1,2,\dots,n+1\}\\ & \mathrm Y \succeq \mathrm O_{n+1}\\ & \mbox{rank} (\mathrm Y) = 1\end{array}$$
which is a hard problem due to the rank constraint. Relaxing the optimization problem above by discarding the rank constraint, we then obtain the following semidefinite program (SDP) in $\rm Y$
$$\boxed{\begin{array}{ll} \text{minimize} & \langle \mathrm C , \mathrm Y \rangle\\ \text{subject to} & y_{ii} = 1, \quad \forall i \in \{1,2,\dots,n+1\}\\ & \mathrm Y \succeq \mathrm O_{n+1}\end{array}}$$
which is convex and computationally tractable. This SDP relaxation provides a lower bound on the minimum of the original BLS problem. In the very, very fortunate case where the optimal solution of the SDP happens to be rank-$1$, we have solved the BLS problem.

References

Alexandre d'Aspremont, Stephen Boyd, Relaxations and Randomized Methods for Nonconvex QCQPs, EE392o, Stanford University, Autumn 2003.

Stephen Boyd, Convex Optimization, IAM-PIMS, Vancouver, 3/15/04.

Laurent El Ghaoui, Homework Assignment #1, EE227A, January 2012.

Semidefinite relaxation for Boolean least squares, Mathematics Stack Exchange.


Linear programs with strict inequalities and supremum objectives Linear programming can solve only problems with weak inequalities, such as "maximize $c x$ such that $A x \leq b$". This makes sense, since problems with strict inequality often do not have a solution. For example "maximize $x$ such that $x<5$" does not have a solution.

But suppose we are interested in finding supremum instead of maximum. In this case, the above program does have a solution - the supremum is $5$.

Given a linear program with strict inequalities and a supremum or infimum objective, is it possible to solve it by reduction to a standard linear program?

Suppose that the supremum of a continuous function $f(x)$ subject to $Ax < b$ is $c$, and assume furthermore that the constraints imply a bound on $\|x\|_\infty$. Thus there is a sequence of feasible points $x_n$ such that $f(x_n) \to c$. Since all points in the sequence have bounded norm, it follows that some subsequence of $x_n$ converges to a limit point $y$ satisfying $f(y) = c$ and $Ay \leq b$. This implies that in the bounded case, your problem is equivalent to classical linear programming.

In the unbounded case this argument doesn't work. For example, the infimum of $x-y$ subject to $x-y > 0$ is $0$, but the sequence $(n+1/n,n)$ has no limit points. Nevertheless, the answer should be the same.


Finding at least two paths of same length in a directed graph Suppose we have a directed graph $G=(V,E)$ and two nodes $A$ and $B$.
I would like to know if there are already algorithms for calculating the following decision problem:

  Are there at least two paths between $A$ and $B$ of the same length?

How about the complexity? Can I solve it in polynomial time?

I would like to add a new constrain on the graph, maybe the problem is more solvable.
On adjacency matrix, every column is not empty. So, every node has at least one arrow on input and there is also at least one node connected to itself. So if the node is the $i$-th node, then $(i,i)$ is an edge in the graph.

Consider a graph $G$, we want to know if there are two different paths from $A$ to $B$ of the same length. What to do? Simple: code two paths in one. Define graph $G'$ with vertices $V \times V \times \{0,1\}$. You make a step in $G'$ by making two independent steps in $G$. The additional bit tells you whether the two paths have already split from each other.

Formally, there is an edge $(i,j,e) \to (i',j',e')$ in $G'$ iff $i \to i'$, $j \to j'$ in $G$ and $e'=e ∨ (i,i')≠(j,j')$.

The algorithm checks if there is a path $(A,A,0)$ to $(B,B,1)$ in $G'$, which is $O(V^4)$, or something like $O((V+E)^2)$.

If you agree this algorithm is correct then, as a consequence, the path in $G'$ is of length at most $2n^2$, therefore potential "path collisions" must occur latest at that length. You can get a $O(V^{\omega} \log V)$ algorithm from this observation, where $\omega$ is matrix multiplication complexity (ask if you need a spoiler...).

I strongly feel there is a $O(V+E)$ algorithm, which uses more of the structure of the problem.


Adleman's theorem to $\mathsf{P=BPP}$ Adleman's theorem gives $$\mathsf{BPP\subseteq P/Poly}.$$
Why is this theorem considered progenitor to derandomization conjecture that $\mathsf{P=BPP}$?

Does it mean Adleman's result could be considered as evidence $$\mathsf{BPP\subseteq P/Log}$$ is a realistic possibility?
Anaalogously, does it mean $$\mathsf{NP\subseteq P/Poly}$$ could be considered as evidence $$\mathsf{NP\subseteq P/Log}$$ is a realistic possibility?

Is there a satifactory answer without considering Impagliazzo-Wigderson's conditional $\mathsf{P=BPP}$ result?

First of all, $\mathrm{NP}\subset\mathrm{P}/log$ would imply that $\mathrm{NP}=\mathrm{P}$ (try all possible log-long advice to search for a satisfying assignment in SAT problem).

Second, the situation for $\mathrm{BPP}$ is more complicated. Since $\mathrm{BPP}$ languages do not have short certificate, one cannot hope to deduce that $\mathrm{BPP}=\mathrm{P}$ from $\mathsf{BPP\subset P/}log$.

What we can deduce from $\mathsf{BPP\subset P/}log$ is that $\mathsf{BPP\cap NP=BPP\cap co}$-$\mathsf{NP=RP=co}$-$\mathsf{RP=P}$. That is, the part of $\mathsf{BPP}$ inside $\mathsf{NP\cup co}$-$\mathrm{NP}$ is just $\mathrm{P}$.


Attribute grammars: How are attributes implemented? I've read about attribute grammars, but I haven't found out, how are the attributes often implemented?

To me they scream objects (of classes), but they could be also variables.

But are there any general rules as to how the attributes should be implemented in a practical implementation? Or is it free form?

Attribute grammars are a conceptual tool. You are mixing this up with implementation details.

There are many parser generators around (check for example the Wikipedia pages on compiler compilers and comparison of parser generators). They all implement some flavor of attribute grammar, in actual use you aren't interested in a parse tree or a derivation. The most used ones are (direct descendants of) old designs, which predate the current object oriented craze, and write parsers  implemented in languages like C, with no objects.


Decidable Program Equivalence Determining whether two programs always return same output for same input is undecidable (easily reduced to the halting problem). My question is, is there a complexity class in which this problem is decidable for machines on that class?

Seems like it must be below PTIME, as Datalog is P-Complete and equivalence of Datalog programs is undecidable.

Given a Turing machine $M$, we can construct another Turing machine $T$, which on input $1^n$ simulates $M$ for $\log n$ steps, and returns whether $M$ halted within these steps. The new Turing machine runs in linear time, and is equivalent to the constant time Turing machine which always returns "No" iff $M$ doesn't halt. Therefore program equivalence is undecidable even for linear time Turing machines.