Ordering elements so that some elements don't come between others Given an integer $n$ and set of triplets of distinct integers
$$S \subseteq \{(i, j, k) \mid 1\le i,j,k \le n, i \neq j, j \neq k, i \neq k\},$$
find an algorithm which either finds a permutation $\pi$ of the set $\{1, 2, \dots, n\}$ such that
$$(i,j,k) \in S \implies (\pi(j)<\pi(i)<\pi(k)) ~\lor~ (\pi(i)<\pi(k)<\pi(j))$$
or correctly determines that no such permutation exists.  Less formally, we want to reorder the numbers 1 through $n$; each triple $(i,j,k)$ in $S$ indicates that $i$ must appear before $k$ in the new order, but $j$ must not appear between $i$ and $k$.

Example 1

Suppose $n=5$ and $S = \{(1,2,3), (2,3,4)\}$.  Then

$\pi = (5, 4, 3, 2, 1)$ is not a valid permutation, because $(1, 2, 3)\in S$, but $\pi(1) > \pi(3)$.
$\pi = (1, 2, 4, 5, 3)$ is not a valid permutation, because $(1, 2, 3) \in S$ but $\pi(1) < \pi(3) < \pi(5)$.
$(2, 4, 1, 3, 5)$ is a valid permutation.

Example 2

If $n=5$ and $S = \{(1, 2, 3), (2, 1, 3)\}$, there is no valid permutation.  Similarly, there is no valid permutation if $n=5$ and $S = \{(1,2,3), (3,4,5), (2,5,3), (2,1,4)\}$  (I think; may have made a mistake here).

Bonus: What properties of $S$ determine whether a feasible solution exists?

Here's a naive algorithm. It relies ultimately on brute force, but may perform okay sometimes.

Each constraint
$(\sigma_{m_i}, \sigma_{m_j}, \sigma_{m_k}) \in S \implies i < k \wedge \neg(i < j < k)$ consists of two conjuncts; let's call them type-$A$, $i < k$, and type-$B$, $\neg(i < j < k)$. Each type-$B$ constraint can be equivalently written as a disjunction $i>j \vee j>k$, relying on the fact that $i\neq j,j\neq k$.

Collect all type-$A$ constraints. Call this $\Theta$. Check whether they are consistent, namely that this is a linearization of the ordering.  This takes $O(|S|)$-time in the number of constraints using topological sorting.
For each of the disjuncts in the type-$B$ constraint, check whether it is consistent with partial order $\Theta$. If it is not consistent, remove the disjunct. If both disjuncts are inconsistent with $\Theta$, then fail. Whenever just one type-$B$ constraint is removed, add the remaining one to $\Theta$. This step is $O(|S|^2)$.
Now there's an obvious algorithm for finding a solution, namely to consider all combinations of the type-$B$ disjunction pairs and test their consistency with $\Theta$, but this is clearly exponential in $|S|$.
One heuristic to improve performance  would be to treat the type-$B$ disjunction pairs as the branches of a tree---one pair forms the root, it's children are given by the second pair, their children by the third and so forth. Using this data structure, a solution is found by traversing the tree in a depth-first fashion. Each time a new constraint is added (using the label on a branch), consistency can be checked. Inconsistent subtrees can be pruned.
If a leaf of the tree is reached, then we have a consistent set of constraints consisting of all of the type-$A$ constraints and one disjunct of the type-$B$ constraints. Linearise the result to obtain the desired ordering.

My preferred approach would actually be to encode it into a set of constraints and use a constraint solver such as Choco. I would introduce $n$ integer variables $x_i$ in the range $[0,n-1]$ and require that they were all distinct. Then I would encode each of the constraints above directly as constraints and then let Choco do it's business.


Which process states exist a multi-processor machine? In a single-processor architecture, A process might be New, Ready, Running, Blocked and Terminated.

Are there any additional states in a multi-processor architecture?

More states aren't technically needed, depending on an operating system's implementation.

A kernel can have a task scheduler running on each processor. This allows for the use of the same process states, since each scheduler is running independent of each other. The kernel can have "load balancing" between the processors so that not too many processes are queued-up on one processor

xv6 (UNIX V6 port for x86 architecture) is a bare-bones kernel that does just this, and so, it has the same process states like in a single-processor environment.


Efficient n-choose-k random sampling Is there an efficient method of sampling an n-choose-k combination at random (with uniform probability, for example)?

I have read this question but it asks for generations of all combinations, not combinations at random.

I general I'm aware of rejection sampling, however it's very inefficient.

I also came across reservoir sampling, but that appears to be primarily geared towards very large or unknown n. I'm more interested in large but finite n (definitely not large enough to not be able to fit in memory. Well. An n-sized array itself will fit in memory, but the state space of all n-choose-k combinations might not).

Is there any survey/review on this topic? Does Knuth cover random n-choose-k sampling in his TAOCP texts?

Thanks in advance.

Edit: To be a bit more specific, a 5-choose-3 space over the string 'ABCDE' would look like this:

['ABC', 'ABD', 'ABE', 'ACD', 'ACE', 'ADE', 'BCD', 'BCE', 'BDE', 'CDE']

(Note: this is combination without replacement). And I want to be able to sample from this space with uniform distribution, using a general algorithm (one that works with arbitrary n and k).

Here is the simplest algorithm, which is efficient when $k$ is much smaller than $n$ relatively.

Input: two positive integers $n$ and $k$ with $k\le n$
Output: a random permutation of $k$ integers from $1,2,\cdots,n$
Algorithm:

Let arr be an array of size $n$ and a default value that is not True.
Let out be an empty array.
Let i be a random integer in $[0,n)$. If arr[i] is not True, append i+1 to out and set arr[i] to True.
Go back to 3 unless we have selected $k$ elements.
return out.

If $k\le n/2$, then the algorithm above runs in $O(k)$ average time. For example, if $n=1000$ and $k=50$, it will use the random number generator less than 55 times in average. This is much better the reservoir sampling that will use the random number generator about 1000 times.

How to speed up the algorithm if $k$ is not much smaller than $n$?

We will let each element in arr be a pair (i, False). After we have selected $n/4$ elemented, we will compactify arr by removing the elements whose second entries have been changed to True. We will set $n$ to $n-n/4$ and $k$ to $k-n/4$. Repeat the algorithm.


Merge a set of strings based on overlaps I have a set of strings that are slices of a single, longer string. It is not guaranteed, however, that any two strings from this set must overlap: only that all of them together overlap. I want to reconstruct the original longer string.

For example, suppose the longer string is LGHFDJGHSJGHDFKSJBSFSHJKADGHS. The slices might be FKSJBSFS, JKADGHS, LGHFDJGHS, SFSHJKA and GHSJGHDFK. I need an algorithm to reconstruct the original LGHFDJGHSJGHDFKSJBSFSHJKADGHS.

I understand that this algorithm may be somewhat probabilistic: given any two strings, the probability that they overlap by pure chance is $\frac{2}{n}$ where $n$ is the size of the alphabet used. I want to find the "best" overlapping longer string.

So far I've asked around and I've been told to look into suffix trees and de Bruijn graphs. I have done so but I can't see how I can apply them to solve this problem. Any help would be appreciated.

This is the DNA sequence assembly problem, an algorithms problem that has been well studied in the literature.  You can apparently find entire courses on the subject.  In general, the problem is NP-hard.  However, there are many algorithms that seem to work well in practice; greedy assembly is one very simple approach, but there are many others.


Most efficient known priority queue for inserts In terms of asymptotic space and time complexity, what is the most efficient priority-queue?
Specifically I am looking for priority queues which minimize the complexity of inserts, it's ok if deletes are a little slower.

 If you're looking for a survey of priority-queues which minimises complexity of deletes over inserts, see: Does there exist a priority queue with $O(1)$ extracts?.

Worst-case complexity
Insert: $\mathcal{O}(1)$
Find-min: $\mathcal{O}(1)$
Decrease-key: $\mathcal{O}(1)$
Delete: $\mathcal{O}(\log \log n)$
Space: $\mathcal{O}(n)$
Proof

THEOREM 1. We can implement a priority queue that with n integer keys in the range $[0 , N )$ in linear space supporting ﬁnd-min, insert, and dec-key in constant time, and delete in $\mathrm{\mathcal{O}(log\ log\ min \{n, N\})}$ time.

Which is established with a combination of:

LEMMA 3. Let $\tau(n, N)$ be the delete time for a priority queue for up to $n$ integers in the range $[0 , N)$ supporting insert and dec-key in constant time. Then $\tau ( n, N ) \le τ ( N, N)$. This holds whether $\tau$ is amortized or worst-case.

and:

THEOREM 6. Theorem 6. We can implement a priority queue that with $n$ integer keys in the range $[0 , N)$ in linear space supporting ﬁnd-min, insert, and dec-key in constant time, and delete in $\mathrm{\mathcal{O}(1 + log\ log\ n − log\ log\ q)}$ time for a key of rank $q$.

Reference
Thorup, Mikkel. “Integer Priority Queues with Decrease Key in Constant Time and the Single Source Shortest Paths Problem.” In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, 149–158. STOC  ’03. New York, NY, USA: ACM, 2003.


Why Miller–Rabin instead of Fermat primality test? From the proof of Miller-Rabin, if a number passes the Fermat primality test, it must also pass the Miller-Rabin test with the same base $a$ (a variable in the proof). And the computation complexity is the same.

The following is from the Fermat primality test:

  While Carmichael numbers are substantially rarer than prime
  numbers,1 there are enough of them that Fermat's primality test is
  often not used in the above form. Instead, other more powerful
  extensions of the Fermat test, such as Baillie-PSW, Miller-Rabin, and
  Solovay-Strassen are more commonly used.

What is the benefit of Miller-Rabin and why it is said to be more powerful than the Fermat primality test?

The Rabin-Miller algorithm also tests, given a number $n$, whether $Z_n$ has a nontrivial root of Unity.

Carmichael numbers pass the Fermat test (for every basis $a$), but for every Carmichael number $n$, there exist many numbers $a$ such that the test for unity roots fails on $a$ (that is, the sequence $a,2a,...,2^ra$ eventually displays a nontrivial root of unity).

Thus, we have the following:

For Fermat's test, if a composite number $n$ is not Carmichael, then the probability that the test will detect compositeness is at least $1/2$. However, the test will fail all Carmichael numbers.

For the Rabin-Miller test, every composite number will be detected with probability at least $1/2$. This means that the correctness probability is independent of the input (there are no "hard" inputs). This is what makes this algorithm stronger.


Is lazy evaluation required for do-notation? Do-notation is most famous by Haskell, which is also famous for having lazy evaluation.

But is lazy evaluation a requirement for implementing do-notation?

In principle, could do-notation be added to imperative languages, such as Java and C++?

It is not required that the language is lazy. The do notation exists in SML family of languages (for instance OCaml), which are eager. In these languages the do-notation is written as the let-notation, that is, instead of writing

do x1 <- e1
   x2 <- e2
   ...
   return e

we write

let x1 = e1 in
let x2 = e2 in
...
e

Note however that let in OCaml has a fixed monad (what in Haskell would be the IO monad), whereas the do notation in Haskell works for any monad. There are extensions of OCaml which allow you to use any monad.


Convert a decimal floating-point number into a binary floating-point number Let's say I have a decimal floating-point number, i.e. a mantissa and precision (negative exponent), both represented as integers. How do I convert this into a binary floating point number (of the sort you find in most programming languages, with only the standard operations available). This should be done with maximum precision, ideally. The naive method of simply calculating $m \cdot 10^e$, where $m$ is the mantissa and $e$ the exponent, turns out to be very imprecise when $e$ is large, unfortunately.

I was also wondering how to do the reverse. I suspect the algorithm can't simply be reversed, due to the different representations.

I am not an expert in this area, but the following is what I know about this problem. This problem was solved in the following paper:

William D. Clinger. How to read floating point numbers accurately, ACM SIGPLAN Notices, 25(6) [Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation], pages 92–101, June 1990 (A PDF, you'll find other versions online)

This is also the reference cited by Knuth in TAOCP Volume 2, Exercise 17 in 4.4 (Radix Conversion).

In a retrospective published in 2004, the author looks back and cites the following additional references:

David Gay. Correctly rounded binary-decimal and decimal-binary conversions. Technical Report 90-10, AT&T Bell Laboratories, November 1990. At http://www.ampl.com/REFS/ (Direct link)

In particular, see function strtod in David Gay's dtoa.c available at http://www.netlib.org/fp/

The reverse problem (printing floating point numbers) is harder. It should probably be a separate question, but here are some references:

Steele and White, How to Print Floating-Point Numbers Accurately (also 1990, at the same conference)
Their retrospective
Burger and Dybvig, Printing Floating-Point Numbers Quickly and Accurately (1996)
Florian Loitsch, Printing Floating-Point Numbers Quickly and Accurately with
Integers
Printing Floating-Point Numbers: A Faster, Always Correct Method from POPL’16. Revised to Printing Floating-Point Numbers: An Always Correct Method (see github) (2016)

Popular expositions and other implementations:

Bryan Sullivan, Here be dragons: advances in problems you didn’t even know you had (2011)
Russ Cox, Floating Point to Decimal Conversion is Easy (2011)
Ryan Juckett(?), Printing Floating-Point Numbers (2014)
python-nicefloat
Aubrey Jaffer, Easy Accurate Reading and Writing of Floating-Point Numbers (2013)

Aside/Example: Even though this is a problem solved since 1990 (albeit with developments even last year), even Python until 2.6 had suboptimal printing of floating-point numbers, e.g. it would print float('2.2') as '2.2000000000000002'. It was fixed only in Python 2.7. See https://docs.python.org/2/whatsnew/2.7.html#python-3-1-features and https://docs.python.org/3/whatsnew/2.7.html#other-language-changes (specifically https://bugs.python.org/issue7117 and discussion at https://mail.python.org/pipermail/python-dev/2009-October/092958.html).


Confusion with the Running Time of an algorithm that finds duplicate character I have the following simple algorithm to find duplicate characters in a string:

for i = 1 -> n
    for j = i + 1 -> n
        if A[i] == A[j] return true
return false

Why is the running time of this algorithm $\mathcal{O}(n^2)$?
If the first iteration is $n$ steps then, $n-1, n-2,n-3,..,1$ it seems to me that
adding all these would never be $n^2$ or am I wrong?

When we sum all numbers we get $n(n-1)/2$, which is in the class of functions $O(n^2)$. Make sure that you understand what big O notation is about.

Another way of seeing that this sum is $O(n^2)$ since each summand is at most $n$ and there are at most $n$ summands, so the sum is at most $n^2$.


Updating the MST of a graph G = (V,E) when decreasing the weight of one of the edges that is not part of the MST You are given a weighted undirected graph  G = (V,E). You have run Prim's algorithm and found the MST of this graph. Now you pick one edge that is not part of the MST and reduce its weight  by some value. You now want to come up with a smart way to find the new MST of the graph.

My approach would be the following. Take this edge (u,v) that you changed and add it to your MST. Start from u and travel around in your MST until you end up back in u, since it is guaranteed that after inserting (u,v) you will create a cycle (MST is a tree). Then from the cycle that you found, remove the edge with the maximum weight.

I feel like this is correct but I don't know how to prove it. Can someone guide me?

Here's what I've tried:

My intuition about the problem is the following. Let's call T, the MST that we found before updating an edge (u,v). Now after updating this edge (u,v), let's just add it to our MST. What is the resulting structure? Since we connect two nodes that are part of the MST with an edge that was previously not in the MST, we create a cycle. Of course this indicates that some edge/edges need to go, since what we just created is not a valid MST. We can not remove any edges that are not part of the cycle that we just created, since this action would give us two components that are not connected. If we look at the cycle that we created, we can only remove exactly one edge and no more than that. Since we want to minimize the weight of all the edges part of the MST, we simply remove the edge with the largest weight. So in the end we get something that is definitely a spaning tree, and it is also minimal. Proving that it's spanning tree is trivial. To prove the latter, the edges that are not part of the cycle, should definitely be part of some MST (they are light edges of some cut), so it's ok to leave them there, as for the cycle removing the max weight will give a min total weight.

You are definitely on the right track. As D.W. notes, you have to prove two things:

The new tree is a spanning tree.
There is no spanning tree of lower total weight (i.e. minimality).

For (1), consider what it means to be a spanning tree:

Every vertex must be a part of it (this is the spanning part).
It must be a tree (i.e. a connected acyclic graph).

So with your construction, you have a starting MST $T$ for the graph $G$, and you create a new potential MST $T'$ for $G'$, which is $G$ with a single modified edge weight (which may or may not be the added edge).

Is every vertex of $G$ (and hence $G'$) in $T'$?
Is $T'$ connected?

For (2), you want to show that there's no other tree that is better. Proofs of this kind are normally done by contradiction. So start by assume there is a tree $R$ that is a spanning tree of $G'$ and has lower weight than $T'$, what would this imply?

In thinking about this consider what it means for $R$ to be different, and what this would imply for $T$, the original MST.


Finding an algorithm to return the $\log n$ largest element in an array I have just proved that for every $\alpha, \beta>0 : (\log n)^\alpha=O(n^\beta)$.
Now, given an array of $n$ elements, I want to find an efficient comparison based algorithm for finding the $\log n$ largest elements in the array, and returning them in sorted order.
I will appreciate your help on what is the best way to solve this question, and how should I think when countering such a question.

A possibility (don't think it's the simplest way, though) is:

Transform the array into a max-heap;
find (without extracting) the $\log n$ largests elements in the heap.

The first step can be done in $O(n)$. For the second step, let's give a little bit details:

The largest element is found among one element (it's the root);
the second largest must be found among two elements (the two children of the root);
in general, the $k$-th largest element must be found among $k$ elements, because each time you select an element to be the largest, you remove it from the candidates and add its two children.

That means that after having found the $k$ largest elements, finding the $k+1$-th is done by searching the maximum value among $k+1$, so it is done in $O(k)$. Since we want to find at most $\log n$ elements, the total search takes $O((\log n)^2)$ time, and with the property you proved, it is $O(n)$.
That means that the total complexity of the algorithm is $O(n)$ which is obviously optimal since you need to browse all elements of the array.
Edit: Actually, I realize (that confirms what I initially said) that there is a simpler way to do it:
Use a quickselect algorithm to find the $\log n$-th largest element (no plural here) of the array (this is done in $O(n)$). By doing so in place, the $\log n$ largest elements will be placed in consecutive positions at the end of the array. You can then sort those $\log n$ elements in time complexity $O(\log n \log \log n) \subset O((\log n)^2) \subset O(n)$.


Using hash tables instead of lists for buckets in hash tables Say instead of using a linked list as buckets for a hash table of size $m$, we use another hash table of size $p$ as buckets this time. What would be the average case for this problem?

I looked up perfect hashing and I got a very close algorithm, and it is $O(1)$. Can someone please clarify?

Using a hash table with $n$ buckets and a hash function $h_n : S \rightarrow \{0, 1, ..., n - 1\}$ , where each bucket is a hash table with $m$ buckets and a hash function $h_m : S \rightarrow \{0, 1, ..., m - 1\}$, is equivalent to a hash table wit $nm$ buckets and a hash function $h_{nm} : S \rightarrow \{0, 1, 2, ..., nm - 1\}$ where $h_{nm}(x) = mh_n(x) + h_m(x)$. In other words, using more than one level has no effect whatsoever on the complexity: it's the same as a for a garden-variety hash table.

Perfect hashing is a completely separate issue.


Are tamper attacks considered side-channel? Wikipedia defines side-channel attacks as:

  any attack based on information gained from the physical implementation of a cryptosystem

Usually in side channel attacks the implementations leak information (e.g., timing attack: the implementation leaks the time it takes to complete a task, etc.)

Are tampering-attacks also considered as side-channel attacks?

On one hand, tampering-attacks are (usually) attacks on the implementation itself.
On the other hand, the attack might be such that information only enters the device, and no information comes out of the device, so there is no "side-channel" that leaks the information.
(example: If we heat some access-control device, until it grants us the access. Or if we perform SQL injection that causes the device to grant the access (but leaks no secret other than that))

A tampering attack can be considered as an active side-channel attack, which is one that involves (physically) interacting with the device under attack. In contrast, passive attacks involve only measurement and observation.

Generally, however, I think tampering attacks are considered as a separate class as the countermeasures against them are quite different than for other side-channel attacks.


D has polynomial verifyer, the certificate for any word $w \in D$ is at most O(|log w|) space. Prove $D \in P$ Given that a language D has a polynomial verifier,

and given that for every word $w \in D$, the length of the certificate $c$ is $O(\log|w|)$ space.

How can I prove that $D\in P$ ?

My idea was to create a TM that takes a word w and runs the verifier on all the strings that are potentially a certificate but I don't know how to claim that such a machine will stop? How can I limit the number of certificates my machine will generate?

Suppose language $D \in NP$ and for every input $w \in D$, the certificate $y_w$ is of logarithmic length; $|y_w| = O(\log|w|)$, and a polynomial verifier $V(w,y)$ exists for $D$.

We can also say: a constant $c$ exists s.t for any $w \in D$ whose certificate is $y_w$, $|y_w| \leq c \log |w|$

Consider the following algorithm $A$:

Given input $x$, for every possible certificate $y_i$ of length at most $c \log |x|$, run $V(x,y_i)$

$\bullet$ If $V(x,y_i) = 1$, then $x$ has a provable witness and $x \in D$

$\bullet$ If $V(x,y_i) = 0$, continue to the next certificate. If all certificates are exhausted, then no $y_x$ exists, and $x \notin D$.

$A$ checks at most $2^{c \log |x|}$ certificates, and $2^{c \log |x|} = |x|^c$. $V$ verifies each certificate at polynomial time (say $|x|^k$), so in total $A$ runs in $O(|x|^{k+c})$ which is polynomial in $|x|$

We get that $D$ can be decided in polynomial time $\Rightarrow D \in P$


LP Relaxation of Maximum Coverage Problem So I know from some research I've done that the OPT-IP <= OPT-LP for the maximum coverage problem, however I'm having some difficulty following the explanations I find. Does an example exist where it can be shown OPT-IP < OPT-LP easily?

Does an example exist where it can be shown OPT-IP < OPT-LP easily?

Here is an example of "LP Relaxation of Maximum Coverage Problem".

Let $G$ be the complete graph with four vertices, $\{v_1,v_2,v_3,v_4\}$. That is, $G$ has six edges. Let $S_i$ be the set of edges that is not incident to $v_i$. More specifically,
$S_1=\{\{v_1, v_2\},\{v_1, v_3\},\{v_1, v_4\}\}$.
$S_2=\{\{v_1, v_2\},\{v_2, v_3\},\{v_2, v_4\}\}$.
$S_3=\{\{v_1, v_3\},\{v_2, v_3\},\{v_3, v_4\}\}$.
$S_4=\{\{v_1, v_4\},\{v_2, v_4\},\{v_3, v_4\}\}$.

The maximum coverage problem is given the above 4 sets, select at most 2 of these sets such that the maximum number of elements are covered. The answer is to select any two sets, which will cover 5 elements. For example, if we select $S_1$ and $S_2$, then all edges are covered except edge $\{v_1,v_2\}$.

If we relax this integer linear programming problem to its corresponding general linear programming problem as done here, we can select "half" of each set. Then each element is "covered" exactly once in total! For example, $\{v_1,v_2\}$ is covered by "half" of $S_3$ and "half" of $S_4$. So we are able to "cover" 6 elements, which are more than 5 elements.

As you should be able to see by now, the idea of this example is quite easy to understand and to generalize.

Problem to ponder (This is not an exercise.)
Is 5/6 the worst ratio we can get given any 4 sets?


What does "finite state transduction" mean? Wikipedia says, the regular languages are closed under

  arbitrary finite state transductions, like quotient K / L with a
  regular language.

I wonder what kinds of operations "finite state transductions" are? Btw,
It links to finite state transducer, an automaton.
Thanks.

A finite state transducer is a machine model, much like a finite state automaton, but equipped with two tapes, one for input and one for output. Each specific finite state automaton defines a binary relation between input and output strings.

Your assumption is right: for each input string we look at computations that match that string and output the corresponding strings on the second tape. This process can be highly nondeterministic, as symbols can be deleted and inserted at will (when the automaton is programmed to do so).
This definition is extended to languages: each transducers defines a binary relation on languages too.

Transducers can be found for a very broad class of tasks: homomorphisms, inverse homomorphisms, intersection or quotient with (a fixed) regular language.
Finite state transducers are nice devices, e.g., they can be programmed to deleted every second $a$ in a string, but only for strings ending in a $b$.

The wikipedia article on FST ignores a very important basic fact on transductions. They happen to be equal to the class of operations built from homomorphisms, inverse homomorphisms and intersection with regular languages. Each family closed under these operations is called a trio, and such a class is then closed under all FST's. Examples are the family of regular languages and the family of context-free languages. So as a consequence, given a CFL, the language we obtain by erasing every second $a$ (for strings that end in a $b$) is again context-free.


Trouble with Big-O notation proof by definition Let $a,b>0$. Prove
$\left(\log\left(n\right)\right)^{a}=O\left(n^{b}\right)$.

I'm supposed to find an algorithm to find the log(n) largest elements in an array and return them sorted and explain why it's bounded by $O(n^{b})$, but the thing is I'm having trouble proving the above and I'm kind of stuck.. Any tips?

As $a$ is fixed, then you can omit it from requirements because for $a \gt 0$ inequality $(\log n)^a \leqslant C n^b$ is equivalent $\log n \leqslant C^{\frac{1}{a}}n^{\frac{b}{a}}$. Denoting $0 \lt \frac{b}{a}=\alpha $ we obtain, that it's enough to proof $\log n \in O(n^\alpha)$ for $\alpha \gt 0$.
To simplify, we can consider $\log n$ with base $e$, because  the difference with the other base will be constant factor.
So, last step will be
$$\lim\limits_{n \to \infty}\frac{\ln n}{n^\alpha} = \lim\limits_{n \to \infty}\frac{1}{\alpha n^\alpha}=0$$
We see, that a more strong result with $o$-little is fair: $\forall \alpha \gt 0$  we have $\log n \in o(n^\alpha) \subset O(n^\alpha)$.


"Natural" reductions vs "Polynomial-time many-one" reductions (Karp Reductions) For two problems $A$ and $B$ and a Karp Reduction $R$ from $A$ to $B$, we call the reduction $R$ natural if, for any instance $I$ of problem $A$, the size of $R(I)$ (as well as the possible numerical parameters of $R(I)$ depends only on the size of $I$ and the sizes of $I$ and $R(I)$ are polynomially related.

We know that all the text-book reductions (from SAT to 3-SAT, 3-SAT to Vertex Cover, Hamiltonian Cycle etc.) are natural in the above sense. In fact, all the natural known "NP-complete" problems are complete under "Natural" reductions.

I have following two questions:

Is it possible for a Karp-reduction to be "non-natural" in the above sense?
Are "natural" reductions only a special case of "Karp" reductions or Can we generalize them for other reductions (like logspace or linear time reductions)?

To understand the context better: Kabanets-Cai[1999] in his seminal paper proved that Minimum Circuit Size Problem (popularly known as MCSP) being NP-hard under so-called "natural" reductions leads to class $E$ having superpolynomial circuit size. Then, recently Murray-Williams[2015] proved that MCSP being NP-hard under "Polynomial-Time" reductions leads to $EXP \neq NP \cap P/poly$ (This is weaker than Kabanets-Cai result). So, surely "natural" reductions are more strict than "polynomial-time" reductions. (or Am I missing something here?)

Natural reductions are a special case of Karp reductions, with an extra condition stating that the output's length depends only on the input's length (and not structure). This concept can be applied to many forms of many to one reductions, so I guess you could talk about natural logspace reductions.

Obviously a karp reduction can be non-natural (otherwise the definition would be of no use). Think about a reduction from clique to SAT, I can make it non natural by first checking whether the graph is planar, and in case the answer is yes output some fixed non satisfiable formula (suppose the parameter $k$ is greater than $4$). This breaks naturality, since now the output formula's length depends on the planarity of the input graph.

Finding an example of a "natural" non-natural reduction (even if a natural one is known) is harder, but I guess that if you go over enough reductions you will find one.


Connection between probabilistic algorithm and distributional algorithm A basic question about the connection between two notions. I am sure these are known notions in CS but I struggle with the basics:
First Definition:
A probabilistic algorithm $A(n)$ decides $L$ if for every $x \in L$, it holds that $\Pr(A(x) = 1) \geq 1 - \epsilon$, and for every $x \notin L, \Pr (A(x) = 0) \leq \delta$.
Second definition:
Given a language $L$ and a distribution $D$ on the instances of $L$, the algorithm $A$ decides $L$ with respect to $D$, if it holds that for every $x$ which is drawn from $D$, the above requirements hold ($\Pr(A(x) = 1)\geq ...$).
Clearly, the first notion is "stronger" in some sense: in the second definition, I may force the algorithm make as many mistakes as I want, by creating a different distribution on which he cannot handle.
My main question is the following:
If for a problem there exists an algorithm $A$ such that $A$ decides $L$ with respect to the uniform distribution, does it mean that $A$ decides $L$ for every input (with high probability)? I somewhat "feel" that uniform solving for a uniform distribution is harder, does this feeling correct?

The first notion (probabilistic algorithms who are correct with high probability for all inputs) is indeed stronger. Distributional complexity relates to randomized (worst case) complexity via Yao's principle, which states that the worst case expected running time of any randomized algorithm, is no better than the expected running time of the best deterministic algorithm for any input distribution.

You can find an exact formulation in this cstheory question, where both the Las Vegas (the randomized algorithm should always output the correct answer) and the Monte Carlo case (similar to your formulation) are mentioned.

As for your question, it is not true that an algorithm which outputs the correct answer with high probability when the input is drawn according to the uniform distribution, returns the correct answer with high probability for all inputs. Consider an algorithm which answers correctly for all inputs not of the form $0^n$. For an input drawn from the uniform distribution, the probability of getting a correct answer is $1-2^{-n}$, however for inputs of the form $0^n$ you never get the correct answer.


If Data-Flow Analysis is able to approximate, what does that mean? I have been learning about data-flow analysis and have come across the idea of approximations and that the data-flow analysis should be able to under and over approximate a situation. For example, when using available expressions, we under under-approximate if we aren't sure if we can do something by not doing it. I just don't really understand; surely if analysis wasn't sure if it could do something or not, the algorithm would just not report this as a possible available expression?

What does approximation and decidability (which I think is also related) mean in terms of data-flow analysis?

All of the problems we want to solve with static analysis are undecidable.  We have a yes-or-no question ("will this expression be available?", "is this variable live?", etc.).  Ideally we'd like an algorithm that takes as input the program, terminates in a finite amount of time, and outputs the correct answer to the question.  Unfortunately, the problem is undecidable, so there is no such algorithm.

But we're not willing to give up.  So, we accept algorithms that always terminate but sometimes output "I'm not sure".  There are basically two kinds of such algorithm.  One can will either output "Definitely yes" or "I'm not sure (might be yes, might be no)".  The other kind will either output "Definitely no" or "I'm not sure (might be yes, might be no)".

Underapproximation vs overapproximation just refers to the difference between those two kinds of algorithms.

How do you pick one or the other?  That depends on what you're ultimately trying to achieve.  In some situations, it's more useful to know that the answer is "definitely yes".  In others, it's more useful to know that the answer is "definitely no".

Of course, these two notions can be combined, so you can get an algorithm that will output either "Definitely yes", "Definitely no", or "I'm not sure (might be yes, might be no)".  But you can't avoid the possibility of an "I'm not sure" answer; that's an unavoidable consequence of undecidability.


Difference between multi-tape Turing machine and single tape machine A beginner's question about "fine-grained" computational power.
Let $M_k$ be a $k$-tapes turing machine, and let $M$ be a single tape turing machine. We know that $M_k$ and $M$ both have the same "computable power". In addition, one can simulate $M_k$ on $M$ in a way that every computation which takes $O(t(n))$ on $M_k$ will take $O(t(n) \log(t(n))$ on $M$.
Here is my question:
Is there a language $L$ such that $L$ can be decided in $O(n)$ time in $k$-tape Turing machine (for fixed $k$, say 2), but can't be decided in $O(n)$ time in a single tape machine? (every single tape machine which decides $L$ needs $\Omega(n \log n)$ time).
In addition, are there any examples of two computational models (classical, not the quantum model) with the same computable power, but with fine-grained differences in their running time? (I guess that major changes in running time would contradict the extended Church-Turing thesis, which is less likely).

The language of all palindromes needs quadratic time on a single-tape Turing machine. See for example lecture notes of Eric Ruppert. The proof uses crossing sequences. In contrast, on a two-tape Turing machine, the language can be decided in linear time.


Kleene star and Kleene plus Let $\Sigma$ be an alphabet. Have a look at following definitions frequently used in literature containing Kleene star and Kleene plus.

$\Sigma^* := \Sigma^+ \cup \{\varepsilon\}$
$\Sigma^+ := \Sigma^* \setminus \{\varepsilon\}$

These definitions lead to different sets iff $\varepsilon \in \Sigma_i$ for some $i$. What's the proper one in general context?
Is it similar to mathematical issues like multiplicative identity in rings or including zero in the set of natural numbers?

$\Sigma$ is a finite set of elements called letters. A word is a sequence of 0 or more letters. For every alphabet, there is a unique 0-letter word called the empty word, denoted $\epsilon$. By definition, $\epsilon\notin \Sigma$, for eny $\Sigma$.

Thus, $\Sigma^*$ and $\Sigma^+$ are both well defined, and are used for different purposes.

Mathematically, $\Sigma^*$ with the concatenation operation is a monoid, with $\epsilon$ being the identity element. $\Sigma^+$ is thus a semi-group, with the concatenation operation, as it doesn't have an identity element.


Understanding reductions for NP-completeness Let's I have to make the following reduction:

$$\text{CLIQUE}\le_p \text{VERTEX-COVER}$$

The technique of building the reduction is -

Assume you can find a $\text{VERTEX-COVER}$ of size $k$, in polynomial time.
Building a new graph, in which I say that if a $\text{VERTEX-COVER}$ exists of size $k$, then in the original graph, a $\text{CLIQUE}$ of size $k$ exists?

I just want to understand the technique of these proofs.

Assume you can find a $vertex-cover$ of size $k$, in polynomial time.

Actually, this step is not correct. When we show that $A \le_p B$, where $A$ and $B$ are languages (also known as decision problems), we do not assume that either $A$ or $B$ can be solved in polynomial time. What we do is "reduce" problem $A$ to problem $B$: that means that we take an instance of problem A, and return an instance of problem $B$. The part that has to be polynomial time is this "reduce" function.

In other words, it's possible that $A$ and $B$ are both really "hard" -- they can't be done in polynomial time, or maybe they aren't even decidable. But what we show is that the reduction is polynomial time.

So what is this "reduction" that we have to show is polynomial time? You mentioned part of it:

  Building a new graph, in which I say that if a $vertex-cover$ exists of size $k$, then in the original graph, a $clique$ of size $k$ exists?

That's half. You also have to show that if a vertex-cover doesn't exist of size $k$, then in the original graph, a clique of size $k$ doesn't exist.

To summarize: when doing a reduction from $A$ to $B$ ($A \le_p B$), here are the three things you should show:

If the output of the reduction is in $B$, then the input is in $A$. (For example, if a vertex-cover exists in the output, then in the original graph, a clique exists.)
If the output of the reduction is not in $B$, then the input is not in $A$. (For example, if a vertex-cover does not exist in the output, then in the original graph, a clique does not exist).
The whole reduction -- which takes instances of problem $A$ to instances of problem $B$ -- runs in polynomial time.


Maximum amount of memory that can be allocated to a process DISCLAIMER: The following scenario was taken from an assignment I got in a OS course I'm taking, and it arose a lot of question marks in my head. However non of the questions asked by myself here reflects a question that I'm supposed to answer (alone) as part of the assignment. What I mean is: I'm not asking you to do my HW I'm just asking for help to better understand the concepts.

Given the following scenario:
A system using paging for memory management.
Physical memory size is 128MB
There are 4K frames in physical memory and each frame has 8K words.
Page table of a single process has at most 1024 entries
Virtual memory is not used.

I know from the above that a WORD in such a system must be 4 Bytes long.

Since virtual memory is not being used, I think it is possible that a process can get all the 4K frames if it requests them (assuming obviously that they're available for it when it's loaded) thus it can be allocated all of the available physical memory (128MB). However if Virtual Memory is used then the maximum amount it can get is 32MB because of the structure of the page table (1K entries, each entry has 8K words and each word = 4 Bytes). Is my conclusion correct or not? I reached it while reading Silberschatz, Galvin & Gane book (Operating System Concepts).

The main point I think is here the usage of paging without implementation of virtual memory(VM) techniques.

Nowadays it's rare, but once upon a time when the concept of VM was a dream paging was used for a different purpose. At that time the memory allocated to a process needed to be contiguous which usually lead to fragmentation (external) and hence bad utilization of memory. Then the concept of paging brought a revolution. Memory can be allocated to a process non-contiguously. The process memory space is divided into pages of same size. The Main Memory is also divided into same size frames and page size is equal to frame size. Page table of a process keeps track of the addresses of the frames. To be precise if the page table has $k$ entries it can have at most $k$ frames. For each frame, page table stores the starting memory address of that frame. Unlike the concept of VM all the frames need to be stored in main memory. Note that this might lead to another type of fragmentation (internal) as a process memory space size might not be multiplicative of page size. But, this is not that severe like the external one.

So, here in your question I think they try to mean this kind of scenario, paging without VM. Thus here also it is possible to limit the size of a process by using the page table in the similar manner you mentioned in your question for the case where we use VM.

But, my main concern is to convey the idea that we can indeed use paging without VM.


Name of this rearranging/sorting problem? You are given an array of length $n$. Each element of the array belongs to one of $K$ classes. You are supposed to rearrange the array using minimum number of swap operations so that all elements from the same class are always grouped together, that is they form a contiguous subarray.
For example:
$$
\begin{align*}
&[2, 1, 3, 3, 2, 2] \longrightarrow [2, 2, 2, 1, 3, 3], \text{ or} \\
&[2, 1, 3, 3, 2, 2] \longrightarrow [1, 2, 2, 2, 3, 3], \text{ or} \\
&[2, 1, 3, 3, 2, 2] \longrightarrow [3, 3, 2, 2, 2, 1].
\end{align*}
$$
Three other valid arrangements remain.

What is this problem called in literature?  Is there an efficient algorithm for it?

Note: It is a hardness proof, and I think there are practical algorithms like integer programming, etc.

Given a BIN_PACKING instance where you want to pack $K$ numbers $n_1,\ldots,n_K$ into $L$ bins of size $m_1,\ldots,m_L$, and it is ensured that $\sum n_i=\sum m_j=N$, then we could design a instance of your problem as follows:

There are $K+(N+1)(L-1)$ classes;
The first $K$ classes have size $n_1,\ldots,n_K$ respectively, and each of the rest classes have size $N+1$;;
The array is partitioned into slots of size:
$$m_1,(N+1)^2,m_2,(N+1)^2,m_3,\ldots,(N+1)^2,m_L$$
where each slot of size $(N+1)^2$ is packed with $N+1$ classes, arranged contiguously, and the rest are arbitrarily arranged.

Now a key observation is that it is meaningless to keep at least one class in a $(N+1)^2$ slot unmoved and move other ones (because it won't change the size of a 'bin'). So the original bin packing is available if and only if the minimum number of swaps is no larger than $N$. Since BIN-PACKING is known to be strongly NP-complete, your problem is NP-hard.


Check if adding an edge to a DAG results in a cycle On the begining: It is a programming contest problem, but not from on-going one. Unfortunatelly, I can't provide any link to this task, because it is not publically available. It was from one of the Polish local programming contest in 2011 organised by Warsaw School of Computer Science.

I have a graph with $V$ $(1 \le V \le 5 \cdot 10^5)$ vertices without edges and a list of $E$ $(1 \le E \le 5 \cdot 10^5)$ directed edges. On the $i$-th second $i$-th edge is being added to a graph. I want to know after which second there will be a cycle in a graph.

The most obvious solution would be to perform DFS after adding each edge, but it would take $O((V + E)^2)$ time. Another solution would be to keep the graph topologically sorted and when adding an edge, I could place it in such a way so that it will not disturb topological ordering. This would take at most $O(V^2)$ time. I did some research on Google and it seems that this is the fastest online algorithm.

As I know all the edges beforehand I can use offline algorithm. The fastest offline algorithm I can think of is binary search. If after $k$-th second graph contains a cycle then obviously it will have a cycle at any other second $l \ge k$. So I can do binary search to find smallest $k$ by performing DFS $O(\log E)$ times, each of them taking $O(V + E)$ time, so the total complexity of this solution would be $O((V + E) \log E)$.

It is quite fast, but I wonder if there exist any faster offline algorithm. One thing I can think of is giving for each edge weight equal to the time when this edge was added to a graph. Then the task would be equivalent to finding a cycle with minimal maximum edge weight. I don't know if it leads to anywhere.

Kahn's algorithm is known for topological sorting, but it can be used to find strongly connected components as well.  I use it for cycle checking, where an actual topological sort is not needed.  In this variant, nodes are discarded as they are visited, instead of being added to the output, and the error termination indicates at least one cycle.

It works by pruning off root or leaf nodes (having in-degree or out-degree 0 resp.) from the graph one at a time, until no more nodes of that type can be found.  Since this process cannot cut a cycle (all nodes on a cycle have indegree and outdegree > 0), it terminates with a nonempty graph if at least one cycle exists.

If we cut the maximum remaining edge e at each such termination point, we can continue the process to see if E\e still contains a cycle, and so on iteratively until we've cut enough edges to make E acyclic.  The last such edge cut k is the first k that makes E[1...k] cyclic.

Kahn's algorithm does this leaf-cutting process linearly by using a work queue of nodes to be deleted; it is initialized with the leaves of the entire graph (at least one of which must exist, if it's acyclic), and, as each is deleted, its parent node(s) are checked to see they in turn become leaves, and if so they are added to the work queue.  By checking the neighborhood of each deletion, it works linearly through the graph, without the need for indexing structures beyond the FIFO queue.

We can do the same neighbor-leafness check as we cut the maximum edge, and add any leaves created to the work queue, or, if none are created, continue cutting.

In order to make the max-cutting process linear, we have to find the maximum non-deleted edge via a descending scan of the edges array, but each scan starts where the previous left off, and the algorithm only does a single pass through the whole array, so that part is O(E) in total.  Overall I believe this method is O(V+E), the same as Kahn's alone.


Why is the following grammar not LL(1) Consider the following grammar:
S → bAb
  | bBa
A → aS
  | CB
B → b
  | Bc
C → c
  | cC

I have to provide the reasons as to why this grammar is not LL(1). So far all I can think of is that the grammar is not left factored given the productions:
S → bAb
  | bBa

But I am also wondering if the grammar is left recursive due to the productions:
B → b
  | Bc

Options provided are:

This grammar has left recursion. (Unsure)
This grammar has right recursion. (Would not make grammar not LL(1))
This grammar is ambiguous. (Unsure)
This grammar is not left factored. (Correct)
This grammar can produce infinitely many distinct strings. (This shouldn't affect a grammar right?)

As far as I can tell, the grammar is not ambiguous, I have tried 3 different inputs and all have resulted in a single parse tree.
So is this grammar not LL(1) just because of the lack of left factoring? or also because the grammar is left recursive?

LL(1) grammars must be unambiguous, have no left recursion, and no conflicts.
The grammar you provide is unambiguous in terms of the syntax tree, however there are conflicts when parsing (which stops it from being an LL(1) grammar). The conflicts reside in the first set of S and C. That is to say, FIRST(S) = { b }, but its ambiguous in which production rule to apply: S -> bAb or S -> bBa. This can be eliminated by factoring out the b as such:
S  -> b S'
S' -> A b | B a

Similarly for C:
C  -> c C'
C' -> c C' | eps

The grammar also has left recursion in the rule B -> Bc; this is the definition of left recursion. This can be removed as such:
B   -> b B'
B'  -> c B' | B''
B'' -> c

Check the following for more information:

LL parser: https://en.wikipedia.org/wiki/LL_parser
Left recursion: https://en.wikipedia.org/wiki/Left_recursion
CFG checker (including LL(1)): http://smlweb.cpsc.ucalgary.ca/


How to calculate the efficiency of an algorithm? So I was given this algorithm to compute the efficieny in which I found sorts an array into ascending order.

solvethis(T[1..n])
    for i = 1 to n-1 do   //n
       minJ = i           //n-1
       minX = T[i]        //n-1
       for j = i+1 to n do  //sum_{i=1}^{n} t
          if T[j] < minX then ** //sum_{i=1}^{n} t-1
             minJ = j             //sum_{i=1}^{n} t-1
             minX = T[j]         ////sum_{i=1}^{n} t-1
      T[minJ] = T[i]      //n-1
      T[i] = minX         //n-1

I also listed the number of times the line of code is run. I need to find the efficiency and how many time the line at ** is calculated. Any help is appreciated thank you.

The best way (The way I was taught at least) is to look for a basic operation. That's the operation that most significantly impacts the performance of an algorithm. In your case it looks like if T[j] < minX then would be your basic operation as it's performed the most times, where the statements inside of the if check are only performed if the condition is true. The fact you have two for loops going from 1 to n-1 tell me that you're working with quadratic time. You're going to be doing your basic operation at minimum n^2 or n operations n times. This should tell you that your algorithm performs in O(n^2) timing.


In a bloom filter, why does the optimal number of hashes *increase* with the number of bits in the filter? Multiple resources, such as Wikipedia, state that if you have an $m$-bit Bloom filter with $n$ elements inserted, then the optimal number $k$ of hash functions to use is

$k = \frac{m}{n} \ln 2$

This is very counterintuitive. If $m$ is the number of bits in the filter, then as you increase $m$, why would the optimal number of hashes have to increase to reduce the rate of false positives?

Intuitively, as you increase $m$, the number of collisions goes down. So, as $m \to \infty$, using only one hash function would yield a 0% false positive rate. But this equation would say that as $m \to \infty$, you would need $k \to \infty$ as well. Why?

Is there some way to understand this?

This balances two considerations:

The more hash functions you have, the more bits will be set in the Bloom filter when you create the filter (because each element you insert causes up to $k$ bits to be set in the filter).  The more bits that are set, the higher the risk of false positives.
The more hash functions you have, the less likely that one of them triggers a false positive (because a false positive will be triggered only if all of the bit positions you inspect are set, and the number of bit positions you inspect is equal to the number of hash functions).

So, increasing the number of hash functions ($k$) has two effects, one of which increases the likelihood of false positives, and the other of which decreases the likelihood of false positives.  To figure out how to balance those two, you need to work through the math.

I suspect your intuition was missing the second factor, and once you take that into account the result will feel less absurd.

I agree that if you hold $k,n$ fixed and increase $m$, then the false positive probability will decrease.  But it would decrease even more if you held $n$ fixed and increased both $m$ and $k$ (due to the way the math works out, and due to the second consideration above).


Determining equivalence classes of $\{w \in \{0,1\}^*\mid$ the $k$-bit of $w$ from the right is 1$\}$ I want to formally write the equivalence classes of the following language:
$$L_k = \{w \in \{0,1\}^*\mid\text{ the } k\text{-th bit of }w\text{ from the right is } 1\}$$

I understand the definition of equivalence classes, yet struggle to come up with a clear intuitive answer.

The language is regular, therefore i'd expect finite equivalence classes.

It seems like the essence of the information I am looking for is only "what is the $k$-th bit from the right", which means i want to focus my attention on suffixes in the form of $\sigma y \in \{0,1\}^*$ where $|y|=k-1$, $\sigma\in \Sigma$.

I would highly appreciate some guidance that would build my intuition for finding equivalence classes in general, and in this specific case.

http://users.utu.fi/jkari/automata/fullnotes.pdf explains equivalence classes well (under section 2.8 "Myhill-Nerode theorem") whence the following notation and definition is borrowed.

Define $\text{Ext}(w,L) =\{x\mid wx\in L\}$ where $w$ is in $\Sigma^*$ and $L$ is the language, ie. the set contains of all suffixes that, when added to $w$, yields a word in $L$.

Two words $a$ and $b$ are in the same equivalence class if $\text{Ext}(a,L)=\text{Ext}(b,L)$.

For the language $L_k$ described, only the last $k$ letters of $w$ matter when figuring out $\text{Ext}(w,L_k)$ for any word $w$ because the other letters do not matter as they do not contribute to the condition "the $k$-th bit of $w$ from the right is $1$". Since there are only finitely many combinations for the last $k$ letters, specifically $2^k$, there are a finite number of equivalence classes in $L_k$.

As per your edit about suffixes of length less than $k$, sure, $\text{Ext}$ can contain such suffixes, but they do not matter in showing that there exist finitely many equivalence classes.


Why is the Shannon entropy 0.94 in this example? Suppose I have a decision tree in which there is a label $L$ under which is the attribute $A$ as shown below. I am given that the Shannon entropy of label $L$ is $H(L) = 0.95$.

I must find the Shannon entropy of $L$ given $A$ ($H(L \mid A)$). Here's what I have tried.

\begin{eqnarray}
H(L \mid A) &=& -(\frac{6}{8} \log_2 \frac{4}{6} + \frac{2}{8} \log_2 \frac{1}{2}) \\
 &\approx& 0.69
\end{eqnarray}

However, $H(L \mid A) \approx 0.94$. Where did I err? Is my formula for Shannon entropy accurate?

Back to the definitions:
$$H(L\mid A) = \sum_a p(A=a) H(L \mid A=a).$$

As you compute, $P(A=true)=6/8$ and $P(A=false)=2/8$.

However, you don't compute $H(L\mid A=true)$ but instead compute $P(L=positive\mid A=true)$.  [and the same for $A=false$.].

With standard definition of $H()$ we get,

$$H(L\mid A=true) = - 4/6\log_2(4/6) - 2/6\log_2(2/6) = 0.9182958$$
$$H(L\mid A=false) = H(1/2) = 1$$

And thus, $H(L\mid A) = 6/8 \times 0.918 + 2/8\times 1 = 0.938 \approx 0.94$.


Is {: L(M) ∈ NP} ∈ NP? Intuitively I think the answer is no since I don't think every certificate can be checked in polynomial time but I don't know how to give a formal proof. Is the statement true? Why or why not?

Your language is not even decidable.
Given a Turing machine $T$, define $M_T$ as a Turing machine that simulates $T$ on an empty input, and then decides any $\mathsf{EXPSPACE}$-complete language $L_C$ of your choice (notice that the function $f(T) = M_T$ is computable).
Notice that the language $L(M_T)$ is $L_C \not\in \mathsf{NP}$ if $T$ halts and $\emptyset$ otherwise.
Suppose now that there exists a Turing machine $M^*$ that decides $L$.
Then, you could design a Turing machine that solves the halting problem. When given input $T$, this Turing machine behaves as follows: it computes $M_T$; it simulates $M^*$ with input $M_T$; it rejects if $M^*$ accepts, otherwise it accepts.
Notice that if $M^*$ accepts then you must have $L(M_T) = \emptyset$, showing that $T$ does not halt.
On the contrary, if $M^*$ rejects, then $L(M_T) \not\in \mathsf{NP}$ implying that $L(MT)=L_C$ and hence $T$ halts.


How many range are completely inside a given range I have a list of ranges ai , bi. And I have many queries in the form of a range c, d, which asks how many ranges ( ai, bi ) are completely inside c, d.

c <= ai & bi  <= d

There are so many of these queries. So I want to know if there is an algorithm that answer each query in a time complexity that is better than O(n).

My first attempt was to use two sorted list. One with respect to the end point of ranges and the other with respect to the start point of ranges. This way I can find how many ranges start after c, and how many ranges end before d. But I couldn't find a way to calculate their union. So this attempt was unsuccessful.

My second idea was to use Interval Tree. Interval Tree can help you find whether any ranges overlap with a certain range. I couldn't come up with a modification so that it gives me what I want instead of just overlaps. My best attempt had time complexity of O(n) for each query. For example if the ranges were are all equal my query would take O(n) but this wasn't the only example and there were a lot of other cases that the result of each query would take O(n).

So now I am wondering whether there is a data structure or an algorithm that helps me do these queries in sub-linear time?

I've given an answer to the question with the similar idea here. I'll recall the most important parts of the data structure in this answer. It looks similar to the solution with wavelet trees by Jouni but, I think, is easier to code (arguable).

Here is the data structure which is sometimes called Merge Sort Tree. It is basically a segment tree where each node stores a sorted subarray. This structure requires $O(n \log n)$ memory (because there are $\log n$ layers and each of them requires storing $n$ numbers). It is built in $O(n \log n)$ as well: you just go bottom-up and for each inner vertex merge sorted lists of its children.

Here is an example. Say 1 5 2 6 8 4 7 1 be an original array.

|1 1 2 4 5 6 7 8|
|1 2 5 6|1 4 7 8|
|1 5|2 6|4 8|1 7|
|1|5|2|6|8|4|7|1|

This structure can answer queries of form "how many numbers $\leq x$ are there in range $[l, r]$" in $O(\log^2 n)$ time: just make a reqular query to a segment tree (traversing $O(\log n)$ nodes) and make a binary search to know how many numbers $\leq x$ are there in that node (additional $O(\log n)$ from here).

This can be speed up to $O(\log n)$ using Fractional Cascading technique, which basically allows you to do the binary search not in each node but only in the root. However it is complex enough to be described in the post.

The original problem is reduced to this one exactly the way Jouni explained: having your segments sorted by left endpoint, you create the array of left endpoints $A$ and a Merge Sort Tree of right endpoints $B$. Use the binary search on $A$ to find the range, $[l, r]$, of indexes of left endpoints lying in $[c, d]$ and make a query "how many numbers $\leq d$ are there in range $[l, r]$ in array $B$".


Algorithms for 2-colouring a 2 x N matrix Our task is to color a given $2 \times N$ matrix with two colours red (R) and blue (B) such that no two adjacent cells are blue. For red, there are no restrictions.

An example of all possible solutions for $N = 2$ is as follows:

(R)---(R)   (B)---(R)   (R)---(B)   (B)---(R)   (R)---(B)   (R)---(R)  (R)---(R)
 |     |     |     |     |     |     |     |     |     |     |     |    |     |
 |     |     |     |     |     |     |     |     |     |     |     |    |     |
(R)---(R)   (R)---(B)   (B)---(R)   (R)---(R)   (R)---(R)   (B)---(R)  (R)---(B)

I don't need to list all solutions, but what's a good algorithm for counting all solutions? For example, can we do it in $O(n)$ time or better?

One can view this problem as a dynamic programming problem with $3N$ subproblems.
Let $RR(N)$ be the number of solutions for a $2\times N$ matrix where the first row is colored with red-red, $RB(N)$ the number of solutions where the top cell is red and the bottom one blue, and $BR(N)$ the number of solutions where the top cell is blue and the bottom one red. By symmetry $RB(N)=BR(N)$.
We thus get the recurrences:
$$RR(N)=RR(N-1)+2BR(N-1)$$
$$BR(N)=RR(N-1)+BR(N-1)$$
Note that the total number of solutions for a $2\times N$ matrix is equal to $RR(N+1)$.
If one enters the first few terms (1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363,...) of this recurrence in OEIS one finds that it is A078057:

Expansion of $(1+x)/(1-2*x-x^2)$.
[...]
Number of length-$n$ strings of 3 letters $\{0,1,2\}$ with no two adjacent nonzero letters identical. The general case (strings of $L$ letters) is the sequence with g.f. $(1+x)/(1-(L-1)*x-x^2)$. - Joerg Arndt, Oct 11 2012

An algorithm which computes $RR(N)$ by evaluating the recurrence above can do so with $O(N)$ additions. The numbers can get as large as $\Omega(N)$-bit, so the complexity is $O(N^2)$.


Proof Review: Integer Factorization is in NP I want to prove that integer factorization is in NP
I have a general idea of how to prove this, and was wondering if I could get a sanity check:
I'll show it's in NP by using a non-deterministic TM whose longest computational branch runs in polynomial time.
The TM will do the following:
Given an input (binary) word w of length n on the tape:
Non deterministically guess i factors,  1<=i<=n, such that each of the factors is a binary string no longer than n.
Multiply all of the factors together (I think this should take O(n^3)) and accept if the final number on the tape is equal to w.
Otherwise, reject.

Am I missing anything?

You are missing something.

If you are given what is supposed to be a factorisation of a number x, it's not enough to show that the product of those numbers is x. You also have to prove that all the numbers in the purported factorisation are primes.

Fortunately there is theorem that for every prime number, there is a polynomial time proof that it is a prime.


How do I replace a D Flip Flop with a JK Flip Flop Hello I have this circuit with this I want to learn about Mealey and Moore.

Is this a Mealy Automata? I would say yes because of the upper LED depends on the variables I got.

Otherwise isn't the line of J the next State? So it is a Moore because it only depends on its states?

Now I want to replace the D Flip Flop with a JK how could I do this?

I would just implement a JK to change it but I guess there are things that have to be done so the automata has the same outputs.
Any suggestions on how to do this?

Thanks

Just as a hint, the general way to solve a problem like this is to write a truth table. The "inputs" to the truth table are the inputs to the machine plus the states of the flip-flops (one bit per FF), and the "outputs" are the outputs of the machine and the outputs of the flip-flops.

From that truth table, you can see if it's a Mealy machine. And given the desired "state on this time" and "state next time", and you can work out what the inputs to a J-K flip-flop should be:

 Q Q' | J K
------+-----
 0 0  | 0 X
 0 1  | 1 X
 1 0  | X 1
 1 1  | X 0

Where X is "don't care".

I only mentioned the truth table because you wanted to show that it was a Mealy machine, and finding the mapping of inputs and outputs is a definite way to get there.

As for the main question you're asking, you can't replace a D flip flop with a JK flip flop in the general case due to timing. D flip flops "read" their input on (say) the leading edge of the clock, and "output" their result effectively straight away, after a short propagation delay. JK flip flops, on the other hand, "read" on the leading clock edge and "output" on the trailing edge.

This property of JK flip flops can be useful; they are extremely resistant to combinational hazards, for example. But it does mean that they respond half a clock cycle later than a D flip flop.

Assuming that this isn't an issue (and I doubt it is in your circuit), you can just feed D into J and not-D into K.


Is there a formalization of the computational model for quantum computers? There are several equivalent computation models, each capable of simulating each other. For example, the lambda calculus or the SKI calculus which are based on rewriting, Cardelli's object calculus, Hoare's communicating sequential processes, and of course the universal Turing machine, all of them formally defined.

I do understand that though there are possibly different ways of building quantum computers, the ways we build them today are Turing-complete and equivalent to the other models of computation. My question is: have anyone formalized a mathematical computation model for a quantum computer (such as the D-Wave)? (As the other models, I assume this could be used as a programming language.)

(I do understand that a possible answer would be "the quantum mechanics", but that's not exactly what I'm looking for...)

Yes.  The quantum Turing machine is a mathematical formalization of a computation model for a quantum computer.

See also https://en.wikipedia.org/wiki/Quantum_computing#Developments and https://en.wikipedia.org/wiki/Quantum_complexity_theory and https://en.wikipedia.org/wiki/BQP.


How are the number of bytes less than the number of pixels in an image? Lets take, for example this jpeg image here

The image there is 400 x 300, or 120000 pixels and The file size of the image (on my computer) is shown to be 65171 bytes.

This means the computer stores about 2 pixels in every byte. How does it do this? Is it due to the same color pixels repeating in the image, so it only has to save the RGB data once, or is there some other trickery going on here?

A colour image is typically digitalized using 256 levels for each of the 3 RGB channels. That gives 3 bytes per pixel. The trick to attain smaller file size is to apply some compression, to take advantage of the redundacy (neighbouring pixels tend to have similar colours). That depends on the image format. For example, PNG format applies a "lossless" compression (no information lost). JPEG format applies a more aggresive lossy compression (some information lost). BMP format is a format that does not (by default) compress; you can try to open your image and save it in BMP format and check that the size is approximately the expected (3 bytes per pixel). Other thing you can try is to generate a big "pure noise" image, and check that the size is also about 3 bytes per pixel (compression does not work here).


Compute height of AVL tree as efficiently as possible Given an AVL tree, I want to compute its height as efficiently as possible. $\newcommand{\bf}{\text{bf}}\newcommand{\height}{\text{height}}$

Each node of an AVL tree stores its balance factor ($\bf$), defined as

$$\bf(v)=\height(v.\text{left}) - \height(v.\text{right}).$$

We can recursively compute the height of an AVL tree in $O(\log n)$ time, using the following recursive procedure:

Height($v$):
1. If $v$ is a leaf node, return 0.
2. If $\bf(v)=+1$, return Height($v.\text{left}$).
3. If $\bf(v)=-1$, return Height($v.\text{right}$).
4. If $\bf(v)=0$, return Height($v.\text{left}$). (returning Height($v.\text{right}$) would work too)

This recursive algorithm works, because the balance factor tells us which is taller, the left subtree or the right subtree, and the algorithm always recurses into the taller subtree.

My question is: Is there a faster algorithm?  Can we do better than $O(\log n)$ time?  Assume we can't augment the tree to store extra information in it; we are restricted to only the information that is already normally stored in an AVL tree.

No.  There's a $\Omega(\lg n)$ lower bound.  You can't do better than $O(\lg n)$ time.  In fact, any algorithm has to visit at least $H-1$ nodes, where $H$ is the height of the tree.

Let $T_1$ be a tree of height $H$, where the balance factor at every node at all but the bottom two levels is 0.  In other words, it is a perfect binary tree of height $H$, except that some subset of the leaves are missing; at the level above the leaves, all nodes have balance factor $+1$, $0$, or $-1$; and at all levels above that, the balance factor is $0$.

Let $T_2$ be an analogous tree of height $H+1$, i.e., it has height $H+1$ and the balance factor at all but the bottom two levels is 0.

Both $T_1$ and $T_2$ are AVL trees.

Now note that any algorithm has to visit at least $H-1$ nodes to distinguish $T_1$ from $T_2$.  Their first $H-2$ levels look identical (every node has two children and has balance factor 0), so you can't tell them apart until you have visited at least $H-1$ nodes.  To count as a correct algorithm for this problem, the algorithm has to produce the right answer on both $T_1$ and on $T_2$.

Consequently, any algorithm has to have worst-case running time at least $H-1$, i.e., $\Omega(H)$.


Proving that the language of TMs with finite left head moves is undecidable I'm trying to prove that the following language is undecidable:$$
   \{ \langle M, w \rangle ~|~ M \text{ is a TM where its head moves left a finite number of times on } w \}
$$

But I'm having a bit of trouble. I know I have to do some type of reduction, but I'm not really sure what. Can a Turing Machine be simulated by one which only moves left? if so, then I think I could show $A_{TM}$ reduces to it. Any hints would be appreciated.

Hint: Reduce from the halting problem. Given a Turing machine $M$ and an input $w$, you want to come up with a new pair $\langle M',w \rangle$ such that $M$ halts on $w$ iff $M'$ makes a finite number of left moves on $w'$. Now if $M$ halts on $w$ then in particular it makes a finite number of left moves, but the other direction is not true. Think of a way of ensuring that if $M$ makes an infinite number of moves in any direction, then $M'$ makes an infinite number of left moves. (You might want to add some spurious moves.)


f(n) and g(n) are monotonically increasing functions. h(n) = max(f,g) => h = O(f) or h = O(g)? All functions are from naturals to naturals.

Let f(n) and g(n) be monotonically increasing functions. prove or disprove
h(n) = max(f(n),g(n))  =>  h = O(f) or h = O(g)

I've found close questions regarding max(f,g) being O(f+g) but I couldn't derive anything from them regarding my specific problem. Needless to say, I'm new to algorithms and data structures.

any explanations, solutions would be great :)

That's not true. Let's define $f$ and $g$:

$$
f(x) = \left\{\begin{aligned}
&1 && x = 0\\
&2f(x-1) && x \equiv 1 \mod 2\\
&4^xf(x-1) && \text{otherwise}
\end{aligned}
\right.$$
$$
g(x) = \left\{\begin{aligned}
&1 && x = 0\\
&4^xg(x-1) && x \equiv 1 \mod 2\\
&2g(x-1) && \text{otherwise}
\end{aligned}
\right.$$

They look odd, but you can easily proof (by induction), that:
$$
max\{f, g\}(x) = \left\{\begin{aligned}
&2^{x}g(x) && x \equiv 0 \mod 2\\
&2^{x}f(x) && x \equiv 1 \mod 2
\end{aligned}
\right.$$

Intuition behind this is that for each number $x$ we 'increase' value of one function by $2$ and one by $4^x$. Increasing first function is straight forward, just for keeping function strictly increasing. Multiplication of second function is more interesting. Since $4^x = 2 \cdot2^{x-1}\cdot2^x$, we can split this operation into 3 steps:

multiply by $2$ since, another function is multiplied by $2$,
multiply by $2^{x-1}$, because another function was already greater by that factor,
multiply by $2^{x}$, because we want our function to be greater by this factor

Now you can easily see, that there is no constant $c$ for which $$max\{f, g\}(x) < cf(x)$$ nor $$max\{f, g\}(x) < cg(x)$$.


Characterize the Equivalence Classes of a Language Given a language $A = \{a^nb^n : n >= 0\}$, how would one go about characterizing the equivalence classes of this language, in order to apply Myhill-Nerode to show it is not regular? The idea and meaning of "characterizing equivalence classes" is what I am struggling with.

The notion of equivalence is that of indistinguishability. Given a language $L \subseteq \Sigma^{\ast}$, we say that strings $x$ and $y$ are indistinguishable wrt. $L$, written $x \, I_L \, y$, if we have that for every $z \in \Sigma^{\ast}$ that $xz \in L \iff yz \in L$.

The Myhill-Nerode theorem tells us that a language $L$ is a regular language iff the set of equivalence classes of $I_L$ is finite.

To show that $L = \{ w \in \{ a,b\}^{\ast} \mid \exists n \geq 0. w = a^n b^n \}$ is not regular, we simply have to show that the set of equivalence classes of $I_L$ is infinite.

So consider a string $w \in \{ a,b\}^{\ast}$. The set of all strings $w$ not of the form $a^i b^j$ where $i \geq j$ forms an equivalence class, since for no $z$ we have that $w_1 z \in L$ if $w$ is not of the form $a^i b^j$.

Moreover, every string of the form $a^i b^j$ where $i \geq j$ can only be indistinguishable from itself. So every such string forms an equivalence class containing only this single string.

Consequently, $I_L$ has infinitely many equivalence classes.


Why cannot Operand forwarding remove all RAW hazards? I read a statement in the textbook that : Operand Forwarding cannot remove all RAW Hazards in Pipelined Processor but am unable to conceptualize that in my brain. Can you please explain it with an example where Operand Forwarding will not be able to remove RAW Hazard .

Sure!
And I can assure that is a fairly good question, if you are not able to see all the combinations.
See, operand forwarding can indeed remove all RAW hazards inside CPU but it is helpless when not all execution inside the CPU.
What I mean is all the RAW hazard scenarios, that we can write involving REGISTERS only and execution is some ALU operation, operand forwarding can escape the hazard.
like:
r1 <- r2 + r3            : I1
r4 <- r1 - r3            : I2
r1 is being calculated in ALU for I1, while I2 needs to load r1 as operand for ALU. Here the trick is even though you load the operands of ALU for execution, bt ALU will first execute I1 and then I2 in that order. So, even though r1 is not ready at the assigned time for operand fetch phase of I2, but it will be available before ALU starts execution of I2, and thus taking the benefit of same fact:

CPU notes that I2 is wanting the ALU execution output as an operand.
So, CPU saves this information as setting a bit inside the circuitry. And allowing I2 to proceed with "OPERAND FETCH PHASE" while skipping fetch of I2.

(Fetch of I2 is actually done, when CPU sees the RAW and sets the bit, but that's just assurance of fetch done, NOT THE ACTUAL FETCH)
THIS IS OPERAND FORWADING!
Now as soon as ALU computes the value, as the bit of oprand forwarding is 1, it transfers the contents of ALU output to the ALU operand.
(NOW THE GUARANTEE HAS BEEN COMPLETE, AND r1 for I2 has been fetched).
But observe, the write to r1 by I1 may be not done yet and in next cycles this be done. But I2 might be in ALU execution phase at this cycle.
So, as the FUTURE OPERAND(r1) is inside CPU and ALU being sequential, we could solve RAW.
But the problem is with LOAD/STORE involved in RAW.
load r1, Address1        : I1
r3 <- r1 + r2            : I2
Now the ALU for I2 can't get r1 before complete I1 is executed and r1 has been really written into.
So, this time "OPERAND FETCH PHASE" of I2 will have stall and can't proceed.
Hope this helps.


Reactiveness, cpu and caches I was messing around with a reactive-based frameworks and found it very expressive. Unfortunately, most of them are using techniques that are not very efficient on CPU cashing mechanism such as calling indirect code, and traversing sometimes big collections of subscribers, some of which are readonly, but some can mutate them. That made me thinking of some optimizations that could be implemented : for example, you can imagine that when a core encounters an object that broadcast changes, which is implemented as calling indirect functions, the cpu may miss that data and spend hundreds of cycles loading necessary information. That makes some potential application domains to not be populated with reactive approaches. So my question is that if it would be possible to make it such that cores can be delegated execution of such code in parallel? Or am i mistaken and this kind of code could still be efficiently processed due to all speed-up tricks in modern cpus?

And if the former is true, how to make cpu cores signal they companions in multiprocessor cpu to load pieces of data so they handle them concurrently?

CPUs are developed with typical code in mind. For example, indirect function calls are no problem - the destination of such a function call will be predicted, just as we do with branch prediction.

Remember that "hundreds of cycles" are only "tens of nanoseconds". Typically, 3,000 cycles is just one microsecond. So if a programming pattern wastes "hundreds of cycles", that's no big deal and no reason not to use that pattern. "Traversing big collections of subscribers" - there are efficient methods for doing so.


Lambda calculus without free variables is as strong as lambda calculus? First question: How would one prove that by removing free (unbound) variables from lambda calculus, and allowing only bound variables, its power is not reduced (it is still Turing-complete) ?

Second question: Is the proposition given above really true? Is lambda calculus sans free variables really Turing-complete?

I'm assuming you are referring to the untyped lambda calculus.

If so, write $\newcommand{\num}[1]{\ulcorner #1 \urcorner}\num{n}$ for the Church numeral of the natural unmber $n$.

It is known that there exists a closed term (i.e., without free variables) $TM$ such that
$$
TM\ \num{i}\ \num{n}\ =_{\beta\eta}\ \num{m}
$$
if, and only if, the $i$-th Turing machine (in some standard enumeration) run with input $n\in\mathbb N$ (encoded as usual) halts returning $m$ as output.

Indeed, writing $TM$ is a standard "programming" exercise in the lambda calculus. For that, one can represent the tape as a pair-or-pairs-of-pairs-of... (AKA a cons list) of symbols. Then a "stepping" subroutine to advance the tape and the TM state can be written. Finally, the stepping subroutine is invoked until a halting state is reached. This last step can be achieved using a fixed point combinator such as $Y$.

Since we can simulate any Turing machine, we get Turing completeness.

Alternative proof, which is (in my opinion) easier to actually perform in full detail: prove that any general recursive function can be $\lambda$-defined using a closed lambda term. For that, proceed by induction on the definition of general recursive function.

Indeed, even if you do not aim for closed terms, in this programming exercise you will obtain a closed one in a natural way. After all, when programming one never needs a variable which was not declared beforehand.

Since the general recursive functions are exactly those which can be computed by a Turing machine, we get Turing completeness for the closed lambda calculus.


How does one enter in a boolean expression into an SAT solver? For example, if we had an extremely large expression, how do we even first get it into the program? I can't imagine entering each clause in one by one..

Typically, the huge SAT instance is generated by a reduction from some other problem, so it's computer-generated in the first place.  You write it to a file and tell the SAT solver to read it.


Call by value-return with void function If I'm passing parameters as call by value-return and call a void function, will the local values within the function still be copied to the corresponding values in the caller function even though the called function doesn't return? For example:

int x = 4;

void foo(int a) {
    a = 8 + 8;
}

int main() {
    foo(x);
    print x;
}

Will the value printed be 4 or 16? My hunch is that because foo never returns, the local value for a within the stack frame of foo never gets copied back to the value for x in the stack frame for main, but I wanted to double check.

It will print 4 because sending by value will change the copy not the original variable which is x in your example.


Removing vertices that belong to a given set from a graph If I'm given a graph $G$ with the set of vertices $V$ and a set $B \subseteq V$, can I remove all the vertices $\in B$ from $G$, as well as all edges that connect any other vertex to a vertex $\in B$ in linear time ($O(V + E)$)? It can be assumed that checking if a vertex $\in B$ is $O(1)$.

My thoughts on this are-
If I represent $G$ as an adjacency list, this is not possible as I'd have to loop over all vertices and the vertices that they're connected to. So worst case would be $O(n^2)$.

In case I have an adjacency matrix, I feel like this would be possible in $O(n)$ as I could zero out the entire row and column of the vertices in $B$. However, actually getting rid of the vertices themselves would require shifting elements of the array so overall $O(n^2)$.

My end goal is to be able to perform graph traversals (specifically, finding strongly connected components in the set $G - B$) over the leftover subset in a directed graph. Would simply ignoring any edges leading to vertices in $B$ and ignoring any vertices in $B$ work just fine?

Yes, this can be done on an adjacency list representation in $O(|V|+|E|)$ time.  Looping over all the edges can be done in $O(|V|+|E|)$ time.  As you look at an edge, you can check both endpoints; if either one is in $B$, you can delete it.  Afterwards, you can iterate through the vertices and remove the vertices in $B$ (their adjacency lists will be empty, so no need to do anything with their adjacency lists); this takes $O(|V|)$ time.  The entire process takes $O(|V|+|E|)$ time.


Distribution of cycles length in a graph Given a random directed Graph G:

$$
 G=(V,E) \\
 \lvert V \rvert = n , \lvert E \rvert = k
$$

where for each vertex, either:
$$
  d_{incoming}(v) = 1 , d_{outgoing}(v) = 1
$$
meaning - for each incoming (outgoing) edge to vertex v, there is also an outgoing (incoming) edge from vertex v.

Or:
$$
d(v) = 0
$$

What is the distribution of lengths of the longest cycles for this set of random graphs?

This question relates to the riddle presented in the last minute-physics video. (for the general case)

When $k = n$ and self-loops are allowed, what you have is a random permutation. The expected length of the longest cycle in a permutation is known to be $\alpha n$ for $\alpha \approx 0.624$, see Shepp and Lloyd. If self-loops are not allowed then you will get a different constant $\beta$ that can probably be computed using the methods of Shepp and Lloyd.

When $k < n$, you just get a permutation on $k$ vertices, so instead of $\alpha n$ or $\beta n$ you would get $\alpha k$ or $\beta k$.


Is equivalence of CFGs decidable for finite sets of grammars? Is there a way to show that for all finite sets $S$ of context free grammars, there exists a Turing Machine $M$ such that for all grammars $G_1, G_2 \in S$, we have that $M(G1,G2)$ terminates and answer yes if and only if $L(G_1)=L(G_2)$? Is that even true?

I know that this problem is in general undecidable, but I also know that a finite set is in general decidable. I just can't figure out how to determine the answer for this problem.

A problem is decidable if there is a TM which decides instances of the problem.

Given two arbitrary CFGs $G_1$ and $G_2$, we know this for certain: either $L(G_1) = L(G_2)$, or $L(G_1) \neq L(G_2)$. Consider the first case: a TM that accepts on the input $(G_1, G_2)$ correctly decides this problem. Consider the second case: a TM that rejects on the input $(G_1, G_2)$ would be correct in that case.

Now, consider a finite set of grammars $\{G_1, G_2, ..., G_n\}$. For any two grammars $G_i$ and $G_j$ in this set, we know that either $L(G_i) = L(G_j)$ or $L(G_i) \neq L(G_j)$.

Consider the following TMs:

TM #1:

if input is (G_1, G_1) then accept
if input is (G_1, G_2) then accept
...
if input is (G_n, G_n) then accept

TM #2:

if input is (G_1, G_1) then accept
if input is (G_1, G_2) then accept
...
if input is (G_n, G_n) then reject

...

TM #N

if input is (G_1, G_1) then reject
if input is (G_1, G_2) then reject
...
if input is (G_n, G_n) then reject

Each TM can either accept or reject for each of the $n^2$ (ordered) inputs; so there are $N = 2^{n^2}$ different TMs (as many as binary strings of length $n^2$).

One of these TMs is guaranteed to correctly decide your problem. I can't tell you which one, but one of these gives all the correct answers. Since there is a TM for your problem, it's decidable.


Understanding memory mapping conceptually I've already read several blogs and questions on stack exchange, but I'm unable to grasp what the real drawbacks of memory mapped files are. I see the following are frequently listed:

You can't memory map large files (>4GB) with a 32-bit address space.

QUESTION #1:
Why? Isn't that the whole point of virtual memory? If a file is greater than 4GB, it may cause trashing by swapping out some memory mapped pages, but why is there a limitation?

If the application is trying to read from a part of the file that is not loaded in the page cache, it (the application) will incur a penalty in the form of a page-fault, which in turn means increased I/O latency for the operation.

QUESTION #2:
Isn't this the case for a standard file I/O operation as well? If an application tries to read from a part of a file that is not yet cached, it will result in a syscall that will cause the kernel to load the relevant page/block from the device. And on top of that, the page needs to be copied back to the user-space buffer.

Is the concern here that page-faults are somehow more expensive than syscalls in general - my interpretation of what Linus Torvalds says here? Is it because page-faults are blocking => the thread is not scheduled off the CPU => we are wasting precious time? Or is there something I'm missing here?

Overhead of kernel mappings and data structures - according to Linus Torvalds. I won't even attempt to question this premise, because I don't know much about the internals of Linux kernel. :)
No support for async I/O for memory mapped files.

QUESTION #3:
Is there an architectural limitation with supporting async I/O for memory mapped files, or is it just that it no one got around to doing it?

One drawback that I thought of was that if too many files are memory mapped, this can cause lower available system resources (memory) => can cause pages to be evicted => potentially more page faults. So some prudence is required in deciding what files to memory map and their access patterns.

QUESTION #4:
Vaguely related, but my interpretation of this article is that the kernel can read-ahead for standard I/O (even without fadvise()) but does not read-ahead for memory mapped files (unless issued an advisory with madvice()). Is this accurate? If this statement is in-fact true, is that why syscalls for standard I/O maybe faster, as opposed to a memory mapped file which will almost always cause a page-fault?

With memory-mapped files, a file is mapped to a pointer p, and byte #i of the file can be accessed through the pointer p+i. For each byte in the file, there must be an address available in the logical address space. With 32 bit, there are only 2^32 possible logical addresses, so 2^32 bytes in a memory mapped file that can be accessed at all.

You are confusing address space and RAM. A 64 bit computer with just 1 GB if RAM can memory map multi-terabyte files without problems. There will be lots of paging, but it will work. With a 32 bit computer, no chance.


Flip-based algorithm for Delaunay triangulation in expected or average-case O(nlogn) Focusing on the 2D plane:

Lawson's Flip Algorithm works in worst-case $O(n^2)$ flips. I have seen it mentioned that (other?) flip-based algorithms work in expected $O(nlogn)$ time for two dimensions. What is a simple example of an algorithm like this (perhaps with proof of complexity)? How would this be found?

Edit: If there are none in expected $O(nlogn)$, are there average-case $O(nlogn)$ flip-based algorithms?

The proof that edge flipping is expected to perform well goes back to this paper below as well as a couple related one around the same time-frame:

Guibas, Leonidas J., Donald E. Knuth, and Micha Sharir. "Randomized incremental construction of Delaunay and Voronoi diagrams." Algorithmica 7.1-6 (1992): 381-413.

A relatively concise algorithm and proof is given in the paper below by Edelsbrunner and Shah which describes a flip-based algorithm that runs in expected O(n log n) time.

Edelsbrunner, Herbert, and Nimish R. Shah. "Incremental topological flipping works for regular triangulations." Algorithmica 15.3 (1996): 223-241.

The algorithm involves adding points to the triangulation one at a time and using some history of the construction process to locate the new points. The paper is slightly more general, dealing with regular triangulations for which the Delaunay triangulation is a special case.


Are there well-specified formal languages that are not regular? Given a finite alphabet, there are well-specified formal
  languages that can not be recognized by regular expressions, FSAs or regular
  grammars True/False

I am studying for my exam and I am unsure about this question. From my understanding, you generate formal languages from regex, FSA. For i.e. for a* our formal language will be

empty,a,aa,aaa etc.

So I can identify if a formal language can be described by a regex, but not sure if that is always the case. Could somebody please help me with this?

There are indeed well-specified formal languages that cannot be represented by regular expressions, even on a one-letter alphabet. Examples include $\{a^{n^2} \mid n > 0\}$ and $\{a^p \mid p \text{ is a prime number}\}$.


How to score a given arrangement of windows on a screen to produce good layouts (this is related to my other question, see here)

I would like to write a function that scores a given arrangement of windows on a screen.

The purpose of this function is to determine whether a particular layout is good and by going over other possible layouts, finding the one with the highest score.

Here are some characteristics that I think make a good layout:

maximizing amount of space used by windows (or in other words, the free space on the screen should be minimized)
windows are (more or less) evenly sized

Bonus: assigning each window a priority and giving a higher score for layouts where windows with a higher priority take more space.

Here's an example: Suppose our screen is 11x11 and we want to put two windows on it. Window A's initial size is 1x1 and window B is 2x1.

When we resize windows, we preserve their aspect ratio. So here are two possible layout:

The function should give the one on the right a higher score.

Another nice thing to have is the option to 'dock' a window to one or more sides of the screen. Then suppose we want to dock A to the bottom-left of the screen, the scoring function should prefer this layout than the above one on the right:

I will expand on my comment on the other question and propose a target function that ensures that no very small windows occur and that windows are not unnecessarily far away from screen edges. Let $\mathcal{W} = \{1,\dots,n\}$ a set of windows and $T = \mathcal{W} \to \mathbb{N}^4$ a tiling; if $T(W) = (x,y,w,h)$ window $W$'s top-left corner is positioned at $(x,y)$ and $W$ has width $w$ and height $h$. Now let $c : (\mathbb{N}^4)^\mathcal{W} \to \mathbb{R}$ a cost function from the space of all tilings to the reals:

$\qquad \displaystyle c(T) = \left[ \min_{W \in \mathcal{W}} T(W)_3\cdot T(W)_4 \right] - \sum\limits_{W \in \mathcal{W}} \operatorname{empty}(W)$

where $\operatorname{emtpy}(W)$ the maximum number of empty tiles between one of $W$'s edges and the respective nearest screen edges. The objective is maximisation.

Note that this is a (non-equivalent) simplification of the multicriteria optimisation goal of maximising

$\qquad \displaystyle c(T) = \left( \min_{W \in \mathcal{W}} T(W)_3\cdot T(W)_4 \ ,\ -\sum\limits_{W \in \mathcal{W}} \operatorname{empty}(W)\right)$.

Of course you need appropriate restrictions in place that ensure that now window is placed outside of the screen and windows do not overlap.


Show that if $\mathcal{H}$ is PAC learnable in the standard one-oracle model, then $\mathcal{H}$ is PAC learnable in the two-oracle model This is a question $9.1$ from Understanding Machine Learning Chapter 3. It goes like this:

Consider a variant of the PAC model in which there are two example oracles: one that generates positive examples and one that generates negative examples, both according to the underlying distribution $\mathcal{D}$ on $\mathcal{X}$. Formally, given a target function $f : \mathcal{X} \to {0,1}$, let $\mathcal{D}^+$ be the distribution over $\mathcal{X}^+ = \{x \in \mathcal{X}: f(x) = 1\}$ defined by $\mathcal{D}^+(A) = \frac{\mathcal{D}(A)}{\mathcal{D}(X^+)}$, for every $A \subset \mathcal{X}$. Similary $\mathcal{D}^-$ is the distribution over $\mathcal{X}^{-}$ induced by $\mathcal{D}$.

The definition of PAC learnability in the two-oracle model is the same as the
standard definition of PAC learnability except that here the learner has access
to $m^{+}_{\mathcal{H}}(\epsilon, \delta)$ i.i.d. examples from $\mathcal{D}^+$ and $m^{-}_{\mathcal{H}}(\epsilon, \delta)$ i.i.d. examples from $\mathcal{D}^{-}$. The learner’s goal is to output $h$ s.t. with probability at least $1-\delta$ (over the choice of the two training sets, and possibly over the nondeterministic decisions made by the learning algorithm), both $L_{(\mathcal{D}^+,f)}(h) \leq \epsilon$ and $L_{(\mathcal{D}^−,f)}(h) \leq \epsilon$

I am trying to prove that if $\mathcal{H}$ is PAC learnable in the standard one-oracle model, then $\mathcal{H}$ is PAC learnable in the two-oracle model. My attempt so far:
Note that $$L_{(D,f)}(h) = \mathcal{D}(\mathcal{X}^+)L_{(\mathcal{D}^+,f)}(h) + \mathcal{D}(\mathcal{X^{-}})L_{(\mathcal{D}^-,f)}(h).$$
Let $d = min \{ \mathcal{D^+}, \mathcal{D^-}\}$, then if $m\geq m_\mathcal{H}(\epsilon d, \delta)$, then it is clear that:
$$\mathbb{P}[L_{(D,f)}(h)\leq \epsilon d] \geq 1-\delta \implies \mathbb{P}[L_{(D^+,f)}(h)\leq \epsilon] \geq 1-\delta$$
And,
$$\mathbb{P}[L_{(D,f)}(h)\leq \epsilon d] \geq 1-\delta \implies \mathbb{P}[L_{(D^-,f)}(h)\leq \epsilon] \geq 1-\delta$$
So we know that if we have $m\geq m_{\mathcal{H}}(\epsilon d, \delta)$ samples drawn iid from $\mathcal{D}$, then we can guarantee $\mathbb{P}[L_{(D^+,f)}(h)\leq \epsilon] \geq 1-\delta$ and   $\mathbb{P}[L_{(D^-,f)}(h)\leq \epsilon] \geq 1-\delta$.
How do I choose $m_{\mathcal{H}}^+(\epsilon, \delta)$ and $m_{\mathcal{H}}^-(\epsilon, \delta)$ such that if we have $m^+ \geq m_{\mathcal{H}}^-(\epsilon, \delta)$ samples iid according to $\mathcal{D}^+$ and $m^- \geq m_{\mathcal{H}}^-(\epsilon, \delta)$ drawn iid according to $\mathcal{D}^{-}$, then we can guarantee $\mathbb{P}[L_{(D^+,f)}(h)\leq \epsilon] \geq 1-\delta$ and   $\mathbb{P}[L_{(D^-,f)}(h)\leq \epsilon] \geq 1-\delta$?
When is drawing $m^+$ samples according to $\mathcal{D}^+$ and $m^{-}$ samples according to $\mathcal{D}^-$ the same as drawing
$(m^+ + m^-)$ samples according to $\mathcal{D}$?

Recall the following lemma. Let $X,Y$ be two random variables satisfying $\Pr[X\le\epsilon]\ge 1-\delta$ and $\Pr[Y\le\epsilon]\ge 1-\delta$ then $\Pr[X\le \epsilon \land Y\le \epsilon]\ge 1-2\delta$.
Suppose $\mathcal{H}$ is PAC learnable (realizable and proper). Let $m(\epsilon,\delta)$ be the guaranteed PAC sample complexity. Given $m(\epsilon,\delta/2)$ samples from $D^+$ and $m(\epsilon,\delta/2)$ samples from $D^-$, find $h_{ERM}$ that is consistent with all samples (both positive and negative). Since $\mathcal{H}$ is PAC learnable, we know that
$\Pr[L_{D^+}(h_{ERM})\le\epsilon], \hspace{1mm} \Pr[L_{D^-}(h_{ERM})\le\epsilon]\ge 1-\delta/2$. Note that we strongly used the fact that the PAC bound is achieved by any sample consistent hypothesis. Now Use the above lemma to show that the overall empirical risk minimizer is a 2-oracle PAC learner for $\mathcal{H}$.