Bit-parallelism and NFA simulation In several papers I have read that Bit-parallel pattern matching is an NFA-simulation.

My questions are:

1- Is it true in general? Or, is there any restrictions?

2- As any regular expression can be converted to NFA, how Bit-parallelism is able to handle some regex like: a?5

Update: Bit-parallel pattern matching is a family of well-known pattern matching algorithms in the literature of hardware-based pattern matching. It was introduced by Baeza-Yates and Gonnet (A New Approach to Text Searching, Communications of the ACM, 35(10):74–82, 1992; PDF) and has gained more attention recently, for example in Faro and Lecroq, Twenty Years of Bit-Parallelism in String Matching (Festschrift for Bořivoj Melichar, pp. 72–101; PDF).

In these papers there are several statements like:
"Bit-parallelism is indeed particularly suitable for the eefficient simulation
of non-deterministic automata.", second reference, page 2.

on p4-5 of your 2nd ref by Faro and Lecroq they write:

  Online string matching algorithms (hereafter simply string matching algorithms)
  can be divided into three classes: algorithms which solve the problem by making
  use only of comparisons between characters, algorithms which make use of deterministic
  automata and algorihtms which simulate nondeterministic automata using
  bit-parallelism.

however, while sounding general, these statements seem to be wrt "within the realm of string matching algorithms". in other words there is massive use/ research of bit parallelism of NFAs for string matching algorithms in particular, but have not seen much bit parallelism ideas applied to arbitrary NFAs, even though it is clearly applicable. here are two refs turned up that do consider bitwise operations on a more general/ arbitrary case (apparently the focus of your question). in the 2nd case, "vector algorithms" are capable of/ nearly the same as "bit parallelism".

Implementing WS1S via Finite Automata / Glenn, Gasarch, sec 4, "internal representation of Automata"

  we do this with elementary bitwise operations

Fast Implementations of Automata
Computations / Bergeron, Hamel sec 2.2 "solving more complex automata"

  In this section, we establish a sufficient condition for the existence of a vector
  algorithm for an automaton.


When and what must be present on the left-hand side of the turnstile in metalogics? Let me show the problem on an example...
An actual task from one of the former exams:

Consider a simple functional language:
$$e::= x|n|e_1e_2|\lambda x.e$$
With typing rules:
$$\tau ::= \mathtt{int} | \mathtt{foo} | \tau_1 \rightarrow \tau_2$$
$$\Gamma \vdash n : \mathtt{int}$$
$$\Gamma (x : \tau) \vdash x : \tau$$
$$\begin{array} {c} \Gamma(x : \tau) \vdash e : \rho \\ \hline \Gamma \vdash \lambda x.e : \tau \rightarrow \rho\end{array}$$
$$\begin{array}{c} \Gamma\vdash e_1:\tau\rightarrow \rho\quad\Gamma\vdash e_2:\tau \\ \hline \Gamma\vdash e_1e_2 : \rho\end{array}$$
$$\begin{array}{c}\Gamma\vdash e:\tau \\ \hline \Gamma\vdash e: \mathtt{foo}\end{array}$$
Where the environment $\Gamma$ is a partial function from the set of variables into the set of types and $\Gamma(x:t)$ denotes an environment that assignts the type $t$ to the variable $x$ and works like $\Gamma$ for all other variables.
Derive types for the following expressions:
(omitted for brevity)
Example: Type derivation for $\lambda x.\lambda y.x$:
$$\begin{array}{c}x:\alpha,\;y:\beta\vdash x:\alpha \\ \hline x:\alpha\vdash \lambda y.x:\beta\rightarrow\alpha \\ \hline \vdash\lambda x.\lambda y. x : \alpha \rightarrow (\beta\rightarrow\alpha) \end{array}$$

It is this example that perplexes me. Why is it necessary to put $x:\alpha$ on the left-hand side of $\vdash$ in the second step of the derivation? My thinking is that $\lambda x.y : \beta\rightarrow \alpha$ results from both $x:\alpha$ and $y:\beta$ so there's no reason to put $x:\alpha$ on the lhs of $\vdash$ but not $y:\beta$.
But $\begin{array}{c}x:\alpha,\;y:\beta\vdash x:\alpha,\; y:\beta \\ \hline x:\alpha,\; y:\beta\vdash \lambda y.x:\beta\rightarrow\alpha \end{array}$ is a tautology that brings in nothing, so we should instead simplify this to $\begin{array}{c}x:\alpha,\;y:\beta \\ \hline \vdash \lambda y.x:\beta\rightarrow\alpha \end{array}$. Note that this is precisely what the third step of derivation seems to be doing: $\begin{array}{c} x:\alpha\vdash \lambda y.x:\beta\rightarrow\alpha \\ \hline \vdash\lambda x.\lambda y. x : \alpha \rightarrow (\beta\rightarrow\alpha) \end{array}$ They simply put nothing on the left-hand side of the $\vdash$.
What am I missing here? Is this related to the form of the axiom that seems to be used here - $\begin{array} {c} \Gamma(x : \tau) \vdash e : \rho \\ \hline \Gamma \vdash \lambda x.e : \tau \rightarrow \rho\end{array}$ - where the environment used above the vertical line contains the assignment $x:\tau$ while the environment used below the vertical line is devoid of this assignment? Which is why in $x:\alpha\vdash \lambda y.x:\beta\rightarrow\alpha$ the assignment $x:\alpha$ must be present before the $\vdash$, but the assignment $y:\beta$ must not? Is my reasoning correct? But if it is, then why does the third step seem to differ and is of the form $\vdash\lambda x.\lambda y. x : \alpha \rightarrow (\beta\rightarrow\alpha)$ and not $\lambda y.x : \beta\rightarrow\alpha \vdash\lambda x.\lambda y. x : \alpha \rightarrow (\beta\rightarrow\alpha)$?
Or am I splitting hairs here? But my thinking is that I'm not certain what degree of accuratness is required by this professor so I wouldn't like to loose points on something of this sort... Could you clear my confusion?

Perhaps what you're missing (although you seem to suspect) is that the left hand side of the $⊢$ is not just for specifying what types variables have. In fact, as you've noted, it doesn't necessarily have all (or only) the variables on the right hand side (although in this situation it does only have variables, not things like $λy.x : α→β$).

What it's doing is keeping track of what are sometimes called the "free variables" on the right hand side, along with their specified types. The idea is essentially that there are actually no free variables in this formalism; variables are either bound by a $λ$ or in the context $Γ$. The lambda introduction rule:

$$\begin{array}{c}Γ(x:τ) ⊢ e : ρ \\ \hline Γ ⊢ λx.e : τ → ρ\end{array}$$

moves a variable from being bound in the context to being bound by a lambda. In some presentations this might even be written $λx:τ.e$ to still be explicit about what type $x$ has, but this is not really necessary when working with a derivation where the type is already recorded in the judgment (and there are other situations as well).

Of course, variables can go in the context even if they don't occur on the right hand side, like $y$ in your example. This allowed writing a constant function that doesn't actually use its argument.

One way to think about this is to read the tree bottom to top. We want to verify that $λx.λy.x$ has type $α→β→α$. The way we do this is to start in the empty context, and move upward. We use the lambda introduction rule to push lambda-bound variables into the context with an appropriate type, and eventually verify that $$x:α,y:β⊢x:α$$ holds. This is maybe more obvious if the variable rule has a line above it, allowing you to create a completed tree:

$$\begin{array}{c}\\
  \hline x:α,y:β⊢x:α \\
  \hline x:α ⊢ λy.x : β→α \\
  \hline ⊢ λx.λy.x : α→β→α
  \end{array}
$$

The root of the tree is our goal at the bottom, and the leaves at the top are all empty lines. $Γ$ is the local context in which we are verifying the inner parts of the lambda term, and its content is actually motivated by wanting to move under the lambda and verify the type of its body; it contains the variables and their types that have been brought into scope in that process.


Is it feasible to solve this subset cover problem with SAT solver? The problem is to find $\mathcal{S}$, a minimal collect of subsets of $\{1,\dots, 17\}$ such that the two conditions are satisfied:

if $S \subseteq \mathcal{S}$ then $|S|=6$;
for any $A \subseteq \{1,\dots,17\}$ with $|A|=3$, there exists a $S \in \mathcal{S}$ with $A \subset S$.

See here for a related combinatorial problem..

I think this can be formulated as a Min SAT problem.

For each $S \subseteq \{1,\dots,17\}$ with $|S|=6$, we introduce a variable $X_S$. And for each $A \subseteq \{1,\dots,17\}$ with $|A|=3$, we introduce a clause
$$
\vee_{S: A \subseteq S, |S|=6} X_{S}
$$
Then in principal we can use a SAT solver to find the minimal number of $X_S$ that needs to be true to satisfy all the clauses.

This needs $\binom{17}{6}=12376$ variables, $\binom{17}{3}=680$ clauses of length $\binom{17-3}{3}=364$.

I have very little experience in actually using SAT solvers. So is this actually worth trying on my laptop or there's no hope at all?

——-

Update

Turn out there are many research on set covering. It seems that I was over ambitious to try to solve the problem for the parameters  (17, 6, 3).

It is already an open problem for (12, 5, 3).

See here for more details.

———

Update 2

Tried to write everything in pure SAT and it’s quite a bit faster using cadical than z3.

Also, it is significantly faster to find a solution than to show no solutions exist.

I tried to break the symmetry by adding the constraints that the first and the last subset in lexicon order must be selected.

Optimization with SAT is usually referred as MaxSAT instead of Min SAT. In particular, I suggest looking for solvers for "weighted partial MaxSAT", for example MaxHS and RC2.

The problem size you have is fairly small in the context of modern MaxSAT-solvers, so yes it is worth trying. There are no guarantees that the solver will work efficiently, and it is very hard to predict if it will work efficiently, so the best thing to do is to try.


assign points to non-overlapping rectangles I have N (~100M) points in 2D and M (~10k) non-overlapping axis-parallel rectangles. I'm looking for an algorithm to assign each point to a rectangle it is contained in (or say that it is outside of any rectangle). I'm looking for a solution that works faster than bruteforce.

In 1D, it is achievable in N * log(M) using binary search. is something like that possible in 2D?

I care about practical performance. Two or more points can and often would be in the same rectangle, but the opposite never happens as rectangles are non-overlapping.

Most spatial indexes should be good, especially if your rectangles are axis aligned.

Spatial indexes typically have about $O(log{M})$ insertion time so you could build in index in $O(M * log{M})$.
Lookup time is similar, so finding the best/correct rectangle for every point should be around $O(N * log{M})$.

For rectangles, the simplest index is probably a quadtree (but may not scale as well with larger $M$). R-Trees such as the R*Tree (R-Star-Tree) are harder to implement but probably better than plain quadtrees. You could also look into STR-Trees (sort-tile-recurse-loaded R-Trees), they take longer to build but have faster lookup.

In case you are using C++, have a look at libSpatialIndex or the Boost R-Tree. If you are using Java, have a look at my TinSpIn library. In the case of Java I can also strongly recommend the PH-Tree (disclaimer: self advertisement).


Böhm-Jacopini theorem I had a discussion with a friend developer and teacher. He told me about the Structured program theorem arguing that this theorem is one of the most important to know about. However, I have never heard about it and I don't understand how it may have deeply contributed to the computer theory. It seems quite cited in academic papers though.

I had never heard about it before, but taking a quick look at it I can understand why it is considered so important.

Basically, being able to prove that any program can be implemented via three basic operations (sequence, seletion, iteration) allows for simpler formalization when designing a new programming language.

It's basically a one-to-one correspondance to a Turing machine programme, therefore you can easily prove your programming language to be Turing complete.


Efficient algorithm for finding maximum subset of intersecting rectangles What is an $O(n \log n)$ algorithm to find how big the largest subset of $n$ axis-aligned rectangles (in the plane) that contain a common point is? Perhaps by reducing this to a problem with such runtime?

An $O(n^{3})$ algorithm could be

for each of the n rectangles
    for each of the 4 sides of the rectangle
        find the points where it intersects other rectangles and keep the set of those points
        loop through the intersection points set and update the count

You need a sweep line and an interval tree (modified so that it reports a number instead of intervals). I assume this is a course book problem and you are familiar with its background.

Move the sweep line bottom to top, stop at each horizontal segment. If the segment is the bottom side of a rectangle, insert it as an interval into the interval tree and remove it when the sweep line hits the top side of that rectangle. At each step you can query the number of rectangles containing a point on the sweep line. There are $O(n)$ stops for sweep line, each one adds $O(\log n)$ for interval operations, so it is $O(n\log n)$ in total. The only remaining issue is to keep track of the maximum covered point in $O(1)$ at each step. You should be able to complete this solution.


Algorithm Comparison with Theta-notation We consider two algorithms, Algo1 and Algo2, that solve the same problem. For any input of size n, Algo1 takes time $T_1(n)$ and Algo2 takes time $T_2(n)$.

Prove or disprove each of the following statements.

To prove a statement, you should provide a formal proof that is based on the definitions of the order notations. To disprove a statement, provide a counter example and explain it.

Suppose that $T_1(n)$ ∈ $\theta(n^2)$ and $T_2(n)$ ∈ $\theta(n^3)$.

Does it imply that there exists $n_0$ such that for $n$ ≥ $n_0$, Algo1 runs faster than Algo2 on inputs of size $n$?

By definition of $\theta$-notation,$\\$

If $T_1(n)$ ∈ $\theta(n^2)$, then $c_1 n^2 \leq T_1(n) \leq c_2 n^2$ for all $n \geq n_1$for $c_1, c_2, n_1 > 0$.

If $T_2(n)$ ∈ $\theta(n^3)$, then $d_1 n^3 \leq T_2(n) \leq d_2 n^3$ for all $n \geq n_2$ for $d_1, d_2, n_2 > 0 $.

We choose $n_0 = max(n_1, n_2)$

Then, $\\$
$\frac{c_1 n^2}{d_1 n^3} \leq \frac{T_1(n)}{T_2(n)} \leq
\frac{c_2 n^2}{d_2 n^3} \text{ for all } n \geq n_0$

$\lim_{n \rightarrow \infty} \frac{c_1 n^2}{d_1 n^3} = 0$ and $\lim_{n \rightarrow \infty} \frac{c_2 n^2}{d_2 n^3} = 0$

Hence, by Squeeze Theorem, $\lim_{n \rightarrow \infty} \frac{T_1(n)}{T_2(n)} = 0$.
Therefore, Algo1 runs faster than Algo2 for $n >= n_0$

This is my solution, and I am wondering if this is right way to solve this question.

Any help is appreciated, thank you,

If $T_1(n) = \Theta(n^2)$ and $T_2 = \Theta(n^3)$, then since $n^2 = o(n^3)$, it follows that $T_1(n) = o(T_2(n))$. In particular, $T_1(n) < T_2(n)$ for large enough $n$. In fact, for every $C>1$, $T_1(n) < CT_2(n)$ for large enough $n$ (how large depends on $C$).


NP-hardness of a scheduling problem Problem: Given an undirected, weighted, complete graph $G = (V, E, w, c)$. $w$ is the time weight function on edges, $w:E \to \mathbb{N}^{+}$; $w(e)$ represents the time it takes to travel along edge $e$. $c$ is the time deadline function on vertices, $c:V \to \mathbb{N}^{+}$.
Given a source vertex $s$, the question is whether there exists a tour $p: v_{0} = s \to^{e_{0}} v_{1} \to^{e^{1}} v_{2} \to \cdots \to v_{i} \to^{e_{i}} \to \cdots$ such that

$\{ v_{i} \}$ is a multi-set. That is, $p$ is not necessarily a simple path.
$\{ v_{i} \}$ contains all vertices, i.e., $V \subseteq \{ v_{i} \}$.
For each vertex $v \in V$, suppose that it first appears in $p$ as $v_{i}$, then we require that
$$\sum_{n=0}^{n=i-1} w(e_{n}) \le c(v).$$

Background: A courier needs to deliver goods to the places represented by $V$. Each  consignee has specified a deadline. The question is whether there is a tour satisfying all these deadlines.

I guess that this problem is NP-hard, and it reminds me of the scheduling problems with deadlines. However, I cannot find a suitable one for the reduction. Any ideas? (Other reductions for NP-hardness or algorithms are also appreciated.)

This sounds very much like a Hamilton path problem. If you set the edge weights all to $1$ and the deadline of the vertices all to $|V| - 1$, then each vertex can only be visited once, since there is not enough time to visit one twice before the deadline runs out. Finding a Hamilton path on the other hand is NP-hard. Thus, your problem is NP-hard as well.


Universal Turing Machine algorithm First, I learned this based on these facts:

Turing machine (TM) will be define with 7-tuple Notation, $M=\langle Q,G,b,S,d,q_0,F\rangle$.
Any computation rules that can use to simulate any possible TM is called Turing-Complete.
Universal TM (UTM) is TM that is Turing-Complete.

Then, the question begins:

If we have 7-tuple Notation of any U that is UTM, Is there an algorithm to find initial tape content P that U to simulate any TM T with any I input(s)? If it exists, Does it based on each U or pattern of U? If it does, give me some example(s)? If it does, explain the algorithm?
Since all possible computations can be done with TM, Is there an algorithm to make TM simulate any algorithm P written in any language? If it exists, give me some example(s)?
If both questions above exist the algorithm, Why don't we just make a single UTM U and use it to program itself then do every possible computation?

With regards too your first question I would take a different easier to understand route.
Firstly you should note that most programming languages are (theoretically) Turing-Complete (which implied that for a program written in some programming language like C or Python you could transform it into a TM or vice versa).
I'm sure that you heard of the concept "interpreter". It's a program that takes a script as input and runs it (e.g. the python interpreter). You can probably write a simple interpreter yourself (great tutorial).
Now notice that your interpreter could be converted to a TM which takes programs as inputs and runs them, thus you could construct a UTM, and the input would be e.g. a python script.
With regards to your second question: as I mentioned most programming languages used today are (theoretically) Turing-Complete meaning that you could transform any Turing-Machine too a program in this language. The straight forward approach, which works in most object oriented languages is just to model a Turing-Machine (using e.g. a string as tape and an int to remember where on the tape your head is and so on...simple example).
Algorithms that convert one program from one language to another are called transpilers.
I think I don't fully understand your last question. Of course you could plug a UTM into itself. It's like writing a python interpreter in python. The "problem" is that simulation comes at a cost. Generally if you simulate a UTM on a UTM the complexity of some operations increases.


minimum number of edges that should be added to an undirected graph to make it a tree Basically, it's this rosalind problem.
You're given a number of nodes and an adjacency list.
My initial guess was that the answer was the number of connected components minus 1, since by joining every connected component you would have a connected graph, and since it's stated that there are no cycles, that would be a tree.
Why is this approach wrong? The real answer is just the number of nodes-1-number of edges, which I understand, but can't see how is this not equivalent to my answer.
Also, the sample dataset given bugs me. I see three connected components so I don't see why the answer is not 2.
Bear in mind, i'm almost new to graph theory so i'm sorry if i'm missing something simple.

Your first guess is correct. Sometimes there is more than one way to write the same solution.
Clearly, if there are $k$ connected components you'll need exactly $k-1$ edges to connect them (without forming any cycle).
On the other hand, a tree with $n$ nodes must have exactly $n-1$ edges, so if the graph is acyclic and already has $m$ edges, then it is missing $n-1-m$ edges.
Regarding the example: the given graph has $n=10$ vertices, $m=6$ edges, and $k=4$ connected components (not 3), so the answer is $3=k-1=n-m-1$. The sets of vertices in each connected component are $\{1,2,8\}, \{3\}, \{4, 6, 10\}$, and $\{5, 7, 9\}$.


Duplicating the quotation marks in in the quotation-mark enclosed strings There is such a grammar

string_literal ::= " { graphic_character } "

The double-quotes that you see must appear in the user program and curly braces mean "any number of graphic characters in the string". The characters are defined further

graphic_character ::= basic_graphic_character | lower_case_letter | other_special_character
basic_graphic_character ::=
upper_case_letter | digit | special_character | space_character

with special characters listed

  " # & ' () * + , - . / : ; < = > ? @ [ ] _ `

I have encountered a situation where I need the double quote to be the part of the string. This is admitted indeed: double quote is a first special character and it enters the basic graphic characters and, thus, graphic characters. So, I can legally put it into my string. But, this means that terminating quotation mark will be considered a part of the string also and parsing will fail. The language specification says that we need to double the quotation marks to produce a single qmark in the string. I do not get why this requirement it is not a part of the grammar. How should proper grammar had to look in this case?

Just replace " in the list of possible characters with "".

That might have consequences for other grammar productions which use the same non-terminals, in which case you might need to separate special_character into special_character_not_quote and ".


Showing that the class of regular languages are closed under merging / modified shuffle Consider $ab$ and $cd$ which are two words. We merge these two into 6 possibilities: $abcd, acbd, acdb, cabd, cadb, cdab$

So in general, a merge of words/sequences $x, y ∈ Σ∗$ , is a word of length $|x| + |y|$ with both $x$ and $y$ as disjoint subsequences in it.

For two languages $L1$ and $L2$ their merge is defined as the set of all possible merges of two words $x ∈ L1, y ∈ L2$.

So basically, a merge is a modified shuffle and should be of length that of the sum of the length of two languages, and should also be in order (see $ab$ and $cd$ example, as $b$ could not come before $a$).

I was thinking of just connecting the states of all $L1$ and $L2$ but this seems wrong as if you connect them all like a fully connected graph, one can jump and go back which is not acceptable.

What's a basic idea on the construction I could do to prove this?

Express the two languages as NFA.  Use a product construction.  Think carefully about what transitions should exist in the product automaton.


How do I check if two if-stmt blocks are the same? Consider the following two snipets of code:

If a >= 5:
   If b == 0:
     ....
   Else:
     ....
Else if a <= 5:
   ....

If a > 5:
   ....
Else If a >= 5 and b == 0:
   ....
Else If a >= 5:
   ....

Then these two constructs are logically equivalent. I am interested if there algorithms that detects if two or more constructs are the same. Papers in this field are also welcome.

(Here, I am assuming that the statements are taken from a Turing-equivalent programming language, since this is the common case in practice.)

In the general case, we know this is not feasible. That is, we know that there exists no algorithm (not even an inefficient one!) that, given two statements, can always output whether they are equivalent.

This is one of the standard results that can be proved using computability theory. A short proof is that, if $equiv(s_1,s_2)$ were decidable, then we can choose any  statement $s_{\sf fixed}$ and obtain that the set $A = \{\langle s1 \rangle \ | \ equiv(s_1,s_{\sf fixed}\}$ is decidable. Indeed, to decide that, we can simply use a decider for $equiv(-,-)$ fixing its second argument to $s_{\sf fixed}$. However, Rice's theorem proves that $A$ is not decidable.

This can also proved without Rice, e.g. using the fact that the halting problem is not decidable, and constructing a suitable reduction.


About the connection of pipelined execution and latency Let's consider we want to calculate a[i]=a[i]*c for a vector the size of N=12 on some random processor.
We do assume that c is some given constant already present in the register. We do not consider any superscalarity or vectorization.
We also know the latencies for the following instructions:

Load operand to register (4 cycles)
Multiply a(i) with c (2 cycles); (a[i],c in registers)
Write back result from register to mem./cache (2 cycles)
Increase loop counter as long as i less or equal N(0 cycles)

The result my class gives me for the pipelined execution of this is the following, where each line represents one CPU cycle:

Why is this correct? Or is this even correct?
If we consider the first load (load a[1]) shouldn't it block my only load unit on the processor for 4 cycles?   How can I even load a[2]in cycle 2then?
Or is latency only the time to that is needed to send information that something is e.g. loaded, and the actual load unit is only busy for one cycle for each load operation?

In a processor that would nowadays be considered simple, you need two numbers for an instruction: what is the total execution time (for example 4 for load) and how long you need to wait before another independent operation can be issued - it seems that someone assumed 1 cycle between instructions for load. A different processor might only allow a load every two cycles, and your numbers would be totally different.
The PowerPC 603 was interesting in that a multiplication took 4 cycles, but it couldn’t start four multiplications in a row, so your multiplications would have started at cycles 4, 5, 6, 8, 9, 10, 12 etc.
Things get more interesting when you have multiple independent execution units; like you assume at least three units capable of load, store, and multiplication. And more interesting if you have limits decoding instructions, dispatching to execution units etc.


The Height of subtree in Heap In order to find the recurrence function of The Height in Heap, the following figure is drawn.

Question 1: How can we compute the height if Right subtree in form of Log in base 3, and why do we have the height of Left subtree as log in base 3/2?

Question 2: it is stated that:
 "for a complete binary tree to have the maximum height the last level should be half full."
i don't grasp the logic behind this line.why?

You are asking several question. I will only answer one. If you start with a set of size $n$ and you repeatedly reduce it to at most $rn$ elements, then after $t$ steps, you will have at most $r^tn$ elements. If $r^tn < 1$, then after $t$ steps you will have no elements. This happens for $t > \log_{1/r} n$. This explains where $\log_{3/2} n$ and $\log_2 n$ come from.


Why does an inverted page table keep a chain of pages per frame when it can only store one of such pages? I'm currently dealing with inverted page tables and how they work. If I understood correctly, an IPT is a table that maps a frame number to a PID and page number. The way this works is by having a hash function map a tuple (PID, page_number) to (frame_number). If the entry of the table given by the frame number contains (PID, page), then we have a hit. Because a hash function can map multiple inputs to one output, we have to keep a chain of pages for each frame (according to my lecture notes).
Why does an inverted page table keep a linked list of pages per frame? Only one page can be loaded into a single frame at a time, how does this make sense? To me this seems more an issue similar to that of direct-mapped caching, where you have to throw out the previous block to make place for a new block.

Hash functions can have collisions, and you need to resolve the collisions.  If two (PID, page_number) pairs map to the same row, only one can be stored there, and you need to have a mechanism to find the other one.
You can use page tables to map multiple virtual addresses (pages) to the same physical address (frame).  For instance, this may be used to support shared memory, copy-on-write, on-demand zeroing for memory allocation, and more.


Are all adjacency matrices represented by 0 and 1s? Are there any cases when adjacency matrix should have entries other than 0 and 1?

Yes, because the (i,j)th entry simply talks about whether or not there exists an edge from vertex i to vertex j, and represents existence by a 1 and non-existence by a 0.

However, many graph representations store the edge weight instead of 1s in the matrix. This way, a single matrix can compactly represent both the edges and their weights.


Check if a tree is formed by 3 subtrees with given number of nodes I have run into a  contest problem (ACM like) that sounds like this:

Input: a tree of $N$ nodes; integers $X,Y,Z$ such that $X+Y+Z=N$
Question: Can the tree be partitioned into three trees of $X,Y,Z$ nodes by removing only two edges?

I am promised that $N \le 10^5$.  My code must finish within 200ms.

The brute-force method of generating all possible partitions of X, all possible partitions of Y, and all possible partitions of Z and checking if they form the tree is too slow. This got me thinking about dynamic programming. The only thing I see here to help me form a DP algorithm is counting how many children does a node have (treating the current node as a root of a tree).  However, checking between the nodes themselves for X, Y, Z would still take $O(N^3)$ time, which is too much.

So do you see any other algorithm for this task?

Example: We're given a tree of 8 nodes and X = 3, Y = 3, Z = 2 and the following edges:
2-3; 4-2; 2-1; 1-5; 1-8; 5-6; 5-7. The answer is yes because you can
delete edges 1-2 and 1-5 to form 3 partitions like this {1,8} (Z) and {2,3,4}/{5,6,7} (X/Y).

This problem is from a preparation stage of a local competition that happend a while back.

Let's root the tree arbitrarily at node $r$. Now with a DFS, compute the size of each subtree rooted at each node $v$. Let $good(u,i)$ be true, if there is some subtree rooted at $v$ where $v$ lies in the subtree rooted at node $u$ such that the size of the subtree rooted at $v$ is exactly $i$. We will maintain this property for only three values of $i \in \{X,Y,Z\}$. This can be done in the same DFS itself (which is left as an exercise for you).

Since we have rooted the node at $r$, due to the DFS traversal from $r$, all nodes except $r$ have a parent which we will denote by $p(u)$ for a node $u$. Now let's compute the same function $good'(u,i)$ for the same 3 values of $i$ but instead for the subtree which is obtained after deleting the subtree rooted at node $u$. This value can be computed via a second DFS (which I also leave as an exercise for you).

  HINT: Read up on how to find the longest and second longest paths starting at some node in a unrooted tree for each node.

Now the answer to the question is "Yes" if $\exists\ u \in$ tree $T$ such that $good(u,i)$ is true and $good'(u,j)$ is true and $i \not= j$

Since we have only two DFS traversals, the time complexity is $\mathcal{O}(n)$
and a constant amount of memory per node implies $\mathcal{O}(n)$ memory as well.


Are the frequencies of the Huffman encoding of 3 characters unique? I have to figure out the frequencies of 3 letters for Huffman encoding of {0, 10, 11}. One suggestion is in the order {$\frac{2}{3}$, $\frac{1}{6}$, $\frac{1}{6}$} as given in part (a) the 2nd slide of page 3 here. My question is whether the last 2 character frequencies need to be evenly split. Could we not have had {$\frac{2}{3}$, $\frac{2}{18}$, $\frac{1}{18}$}? Or could the 3 character frequencies be entirely different say {$\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{4}$}?

You want frequencies $f_1,f_2,f_3$ for three characters, so that their Huffman encodings are $(0,10,11)$.
The Huffman algorithm repeatedly "merges" the two least frequencies. So any choice that assigns the two least frequencies to the last two characters will work. That means $f_2,f_3 \le f_1$. Since these are frequencies you probably also want the values to add to $1$, but that is of no consequence for the algorithm.
In general the Huffman algorithm does not specify which branches go left and which go right (unless we add that to the implementation) so it is hard to guarantee codes $(0,10,11)$ instead of $(1,00,01)$ for instance.


Centre, diameter, and radius of graph I have been thinking a lot on some questions related to centres, diameter ($D$), and radius ($R$) of an undirected connected graph, but couldn't find anywhere the answers, so am posting here.

Ques1. If $x,y$ are two vertices such that distance between them is $D$, then is it true that any shortest path between them will contain at least one centre?

Ques2. If $D=2R$, then does the graph contains only one centre?

Ques3. Also, can we say that if $D<<2R$, then graph would contain a lot of centres?
(Intuitively I feel so because in figure below, $D$ is smaller than $2R$, and graph contains a lot of centres, the red coloured vertices.)

A quick way of gaining some confidence or disproving a conjecture is using a computer to generate examples.

For Q1, if $x,y \in V$ such that $d(x,y) = D$, it is not true that any shortest path between $x$ and $y$ contains at least one central vertex (highlighted in red). Here, you can walk from 1 to 6 via 9, 5, and 8 avoiding the red vertex.

For Q2, the answer is also no. Below is a graph whose radius is 2 and diameter is 4. It has 3 central vertices (highlighted in red).

You can use ideas from these counterexamples to optimize the graphs further.


Efficient algorithm for iterated find/replace I'm looking for an algorithm for doing iterated find/replace, where the act of finding the replacement list of tokens for a given find is slow.

Specifically: I have a function, f, that maps a sequence of tokens to either a shorter list of tokens or None. However, it is slow.

I want to repeatedly try to replace the (first, in the case of ties) shortest unexplored subsequence in the input with the result of applying the function to it, assuming that there is a valid replacement for it. However, the naive way to do this ends up with exponential runtime. Is there a better algorithm for doing this?

(So, for example, if f maps ba -> b, aaa -> ab, and aba -> bb, and I apply the algorithm to aaaaa, I want to get (aaaaa->abaa->aba->)ab, not (aaaaa->abaa->bba->)bb or any of the other sequences of replacements possible, if any.)

(Note: this example uses characters for simplicity)

This isn't a complete answer, but it provides some context that's far too long to put in a comment. What you've described is an instance of a string rewriting system, also known as a semi-Thue system. Start with a finite alphabet, $\Sigma$, and a binary relation, $R$, on strings over $\Sigma$. For your example, we'll have $R$ defined by

$$
ba\, R\, b,\quad aaa\, R\, ab,\quad aba\, R\, bb
$$
We can then define another relation, $\Rightarrow$, on strings by, basically, applying $R$ to substrings. For two strings $x, y$, define $x\Rightarrow y$ if and only if
$$
\text{there exist strings }p, q, r, s\text{ such that } x=prq, y=psq,\text{ and }r\, R\ s
$$
In your example, we have, for instance, the chain of rewrites $aaaaa\Rightarrow abaa\Rightarrow aba\Rightarrow bb$, and there we stop, since we cannot reduce $bb$ any further. In a rewriting system, a string like $bb$ which cannot be rewritten is called irreducible or sometimes a normal form. If there is a chain of rewrites starting from a seed string $x$ that leads to a normal form we denote the result by $x\downarrow$. Again, in your example, the normal forms derivable from $aaaaa$ are $ab, bb, aab, abb$.

Your question in its most general form is

  Question 1. In a string rewriting system, is there a computationally efficient way to find a normal form for a given string $x$?

In general, the answer is no, there isn't. The problem comes in part from the fact that some (or all) seed strings might never lead to a normal form. This could arise in a rewriting system that permits chains like
$$
x_1\Rightarrow x_2\Rightarrow \cdots\Rightarrow x_i\Rightarrow x_{i+1}\Rightarrow\cdots\Rightarrow x_i
$$
Fortunately, you've imposed a helpful constraint, namely that whenever $x\,R\,y$ then the lengths satisfy $|x|>|y|$. We'll call such a system monotone or length-reducing. In a monotone rewriting system we're always going to have a normal form for any seed string, since every rewrite operation strictly decreases the length of the string. A rewriting system for which every string has at least one normal form is called noetherian, by the way. Refining the question gives us

  Question 2. In a monotone string rewriting system, is there a computationally efficient way to find a normal form for a given string $x$?

The answer to this question is yes, of course: given a seed string $x$, simply apply rewrite rules until you reach a normal form. More systematically, if $|x| = n$ and you have $m$ base rewrite rules $\{w_1\,R\,z_1,w_2\,R\,z_2,\dots w_m\,R\,z_m\}$ with $M=\max\{|w_i|\}$, then we'll require $O(nmM)$ character comparisons, even if we don't use efficient string search algorithms.

We haven't quite gotten to your real question, though, since you also stipulate that at each step you will choose to apply your base rewrite rules in order of the lengths of their left-hand sided, |w_i|, from shortest to longest. It's not clear that this is a useful constraint; in fact, some string search algorithms (Boyer-Moore, in particular) are more efficient when searching for longer substrings than they are for shorter ones. It might be helpful to impose another constraint, though: when searching for a substring to replace, always choose the leftmost substring, regardless of length. This would put you in a situation involving prefixes and there's a fair amount known about this. Choosing rightmost substrings as replacement candidates might also be a useful avenue.

Finally, we come to the most interesting question:

  Question 3. In a monotone string rewriting system, is there a computationally efficient way to find a normal form of minimal length?

This should help you to find answers. There's good news for your search, namely that there's a lot of material out there, both in books (yes, whole books have been written on string rewriting systems) and online. I did a search for "string rewriting systems" and got a million and a half hits. The bad news is that there's a lot of material out there, so finding an answer is likely going to take some serious drilling. Frankly, I don't know the answer to Question 3, but my uninformed guess is that the answer is affirmative. If you haven't gotten a definitive answer in a few days, you might want to ask your question, suitably reworded, over at theoretical computer science.


Inference rule with two conclusions or rather inverse function application I want to express a simple correctness theorem for a term-desugaring function $\Delta$. The goal is to express that if the evaluation of a desugared term yields a value, this value is the desugared result of evaluating the original term.

Since the implication operator $\Rightarrow$ is already used in my dynamic semantics, I'd rather use an inference rule to express the implication. However, in the premise I have to introduce a variable $v$ that is the result of applying $\Delta$ to a variable bound in the conclusion. Since there is no inverse of $\Delta$ I am somewhat stuck between two odd variants to express the relation.

The first variant uses two conclusions (like multiple premises the idea is that both always hold):

$$
\frac{\Delta(t) \Downarrow v}{t \Downarrow v^\prime \quad \Delta(v^\prime) = v}
$$

This looks odd to me. The alternative would be to see the rule as a scheme subject to some substitution over the meta-variables $t$ and $v$. In that case I could also write:

$$
\frac{\Delta(t) \Downarrow \Delta(v)}{t \Downarrow v}
$$

This is obviously cleaner, but I am not quite happy with the implications (pun not intended) to the theorem: In the first case, if $v \neq \Delta(v^\prime)$ the premise still holds, but the conclusion does not, so $\Delta$ is not correct. In the second case the premise would not apply - so correctness simply does not cover the case at all.

Is there a common pattern to deal with such problems? Did I overlook something?

Let us introduce an auxiliary predicate $t \downarrow$ whose intended meaning is "$t$ evaluates to something". Its inference rule is
$$\frac{t \Downarrow v}{t \downarrow}.$$
Now you can express your condition with the following two rules:

If $\Delta(t)$ evaluates to $v$ and $t$ evaluates $v'$ then $v$ equals $\Delta(v')$:
$$\frac{\Delta(t) \Downarrow v \qquad t \Downarrow v'}{\Delta(v') = v}$$
If $\Delta(t)$ evaluates to something then so does $t$:
$$\frac{\Delta(t) \downarrow}{t \downarrow}$$.

This is not quite the same as using first-order logic and writing $(\exists v . \Delta(t) \Downarrow v) \implies \exists v' . t \Downarrow v'$. You have to go "meta" and use inversion to conclude from $t \downarrow$ that there exists $v'$ such that $t \Downarrow v'$.

By the way, you said that "since the implication operator $\Rightarrow$ is already used in my dynamic semantics, I'd rather use an inference rule to express the implication" That's a pretty awful reason to choose inference rules over axioms (which is what an implication would give you). You should ask instead what your semantics is for. If you are interested in operational semantics, i.e., you want to express how your programs will be executed, then the rule you are talking about does not really contribute anything. If you want your semantics for reasoning about $\Delta$ and $\Downarrow$, then it might actually be use good old first-order logic.


Competitive ratio of the ski rental problem Reading about the Ski Rental Problem in Wikipedia, I got confused on the "when" is the buying of the skis occur. I could think of 2 possible ways, but each of them would have a different competitive ratio for a deterministic (and non- deterministic) algorithms:

Let's say that renting costs 1 dollar a day and buying costs 10 dollars.

Buy the skis on the day before, this means that you can decide to buy the skis and never use them even once: So if you decide on an algorithm that rents for 9 days and buys the skis on the 9th day, skiing for exactly 9 days (which is the worst-case input for that algorithm) would cost (9 + 10)/9 = 2.111...
Buying the skis on the current day: So you wake up on the morning of day N, you know already you can ski - and then decide if you want to buy  or rent. This changes the competitive ratio of the algorithm in the worst case (for the input: skiing for exactly 9 days) to be: (9+10) / 10 = 1.9

The second method was presented in the Wikipedia article as well as in Algorithm Design and Application by Michael T. Goodrich and Roberto Tamassia. However -it is never written explicitly when does the buying of the skis occur.

My question here is - Are these 2 problems completely different from each other? and the first one can never have a competitive ratio of 2 or less ?

I think the first approach can give an arbitrarily bad competitive ratio for any algorithm: if we ski $0$ days, the optimal would be to neither buy nor rent (pay $0$), while any algorithm either buys or rents the skis before the first day (pay something $>0$).

So the problems are different, and for the first problem we cannot have a "good" algorithm.


Finding an index such that $A[i] = i$ in a strictly increasing integer array I'm looking for a hint for solving the following problem :

  Given an array $A[1, \dots, k]$ of integers where $A[1] < A[2] < \dots < A[k]$
  write pseudocode for an algorithm that determines whether $A[j]=j$ for some $j\in \{1,\dots,k\}$. Worst-case running time should be $\Theta(\log k)$.

I shall find an easy to calculate criteria which finds the index involving the special structure of $A$.

Let's say $A = [-3 , 2 , 4, 5, 7, 8, 9, 10]$. My first approach would be to subdivide $A$ into two parts around the median (here $A[4]$). Since $A[4] = 5 > 4$ and the sequence keeps increasing, I don't have to look at $A[4,\dots,8]$.

My criterion would then be: For a sequence of numbers $A[a, \dots, b]$, if $A[a] > a$, then the solution can't be in that sequence since $A[a]< \dots < A[b]$.

Am I going in the right direction?

Let $B[i] = A[i] - i$. Since $A[i] < A[i+1]$, we have $A[i]+1 \leq A[i+1]$ and so (subtracting $i+1$ from both sides) $B[i] \leq B[i+1]$. In other words, $B[1] \leq \cdots \leq B[k]$ is nondecreasing. Your goal is to find an index $i$ such that $B[i] = 0$, if any such exists. You can use binary search to do this in time $O(\log k)$. In fact, you can even find all such indices (or rather, a succinct representation of them) in that running time.


Understanding connection between minimum spanning tree, shortest path, breadth first and depth first traversal In CLRS, in the later part of breadth first search topic, for unweighted graphs, it says:

  At the beginning of this section, we claimed that breadth-first search finds the distance to each reachable vertex in a graph $G=(V,E)$ from a given source vertex
  $s \in V$ . Define the shortest-path distance $\delta(s,v)$ from $s$ to $v$ as the minimum number of edges in any path from vertex $s$ to vertex $v$; if there is no path from $s$ to $v$, then $\delta(s,v)=\infty$. We call a path of length $\delta(s,v)$ from $s$ to $v$ a shortest path from $s$ to $v$.

So for many months, I was content with the fact that for unweighted path, BFS gives shortest path. But today I came across problem asking whether breadth first search gives minimum spanning tree for unweighted graph. I was like, BFS gives shortest path not the minimum spanning tree. And to my surprise I was wrong. Somehow, stupidly, I assumed what CLRS stated was the only connection among minimum spanning tree, shortest path, depth first search and breadth first search, because I was subconsciously thinking that its not given in CLRS (in any of four sections), then it should not be the case. I did not give any extra thought for evaluating any possible connection. But now I want to know what all are the connection.

I have done quick google and found many links, some of which are:1, 2, 3.

My conclusion is:

  For unweighted graph,

  Breadth first search gives both minimum spanning tree and shortest path tree.
  Depth first search gives only minimum spanning tree but not the shortest path tree.

Now I have further small doubts:

  I know for weighted graph MST and SPT are not same. But are they same for unweighted graph? Somehow I feel no, as otherwise point 2 will be wrong, and DFS would have given both MST and SPT for unweighted graph. However I am not able to come up with the unweighted graph for which MST and SPT are different.
  MSTs given by BFS and DFS on given unweighted graph may be different, its just that the number of edges contained in them will be the same.

Which of above points are correct and which are wrong?

In fact, a MST is a subset of the edges building a tree (thus without cycle) using the minimum edge weights. It has exactly N-1 edges for a N nodes graph.

It may exist several different MST for the same graph. For an unweighted graph, which is in other way a graph with weight 1 on every edges, the total weight of any spanning tree is N-1. Thus any spanning tree is a MST.

When you use BFS or DFS to explore a graph, you build an exploration tree, which is the shortest path tree for BFS. And if the graph is unweighted, you can say this tree is a MST, yes so 1. and 2. are true.

3. is true, MST and SPT are different. Just make BFS and DFS on a 3-clique (3 nodes connected to each other) to have an example.

4. is true but remember that "minimum" adds no information to any spanning tree of an unweighted graph. And also that a N nodes tree has exactly N-1 egdes.


Time complexity of art gallery-like problem Suppose that $G = (V,E)$ is a directed graph such that each vertex in $V$ is in at least one edge in $E$. We'd like to decide whether or not $w$ watchmen can be placed on $w$ distinct vertices in $G$ such that every vertex in $G$ is being "watched" by some watchman. More formally, we'd like to decide whether there exists a $w$-sized watch set $W \subseteq V$ (with $|W| = w$) such that for any vertex $v \in V$, either $v \in W$ or there exists a (directed) edge in $E$ of the form $(u, v)$, with $u \in W$.

I'd like devise a deterministic polynomial time algorithm for deciding whether, for a given $w \geq n/2$, where $n$ is the number of vertices in $G$, $G$ has a $w$-sized watch set $W \subseteq V$. So the decision problem would be $\{\langle G, w \rangle : w \geq n/2 \mbox{ and } G \mbox{ has a size } w \mbox{ watch set}  \}$.

One approach I'm considering is finding, in polynomial time, a minimum edge covering for $G$. If the size of this edge covering is strictly larger than $w$, then we know a size-$w$ watch set does not exist; otherwise we can easily construct a watch set from this edge covering. However, the polynomial time edge-covering algorithms I've seen are a bit complicated, so I'm looking for a simpler approach.

Your problem is a special case of finding a dominating set of size at most $w$ for directed graphs $G$, where we require that there are no isolated vertices in $G=(V,E)$ and that $w\geq |V|/2$.

Unfortunately, this problem is still NP-hard, since there is a polynomial time reduction from the general directed dominating set problem:

Given an arbitrary directed graph $G=(V,E)$ and an integer $w$, construct the instance $(G',w)$ as follows:

Set $G_0 \leftarrow G$ and $w_0\leftarrow w$.
Remove all $i$ isolated vertices from $G_0$ and 'place guards on them': $w_0\leftarrow w_0 - i$. If $w_0\leq 0$, simply construct some instance that yields NO and we're done.
If $w_0\geq |V|/2$, we are done. Otherwise, 'add two guards' for every cycle we will introduce: $w'\leftarrow w_0+2\cdot(|V_0|-2w_0)$ and add $|V_0|-2w_0$ directed 3-cycles to $G_0$. Set $G'\leftarrow G_0$.

Observe that now $w'\geq |V|/2$, since if we have added the three-cycles, we get $2w'= 2w_0+4(|V_0|-2w_0) \geq |V_0| + 3(|V_0|-2w_0) = |V'|$. The reduced instance is a YES-instance if and only if the original instance is, since 'disconnected' components do not influence the rest of the graph and at least 2 guards are required to watch a 3-cycle.

So a polynomial time algorithm most likely doesn't exist, even for this special case.


Halting problem without input? I'm only a layman therefore only discuss stuff naïvely.

I read some introductory articles about halting problems with a scenario that if there were such a decider accessible to us, we should be able to solve some unsolved mathematical problems. We could write some brute-force programs to check Goldbach conjecture, say, and then throw it into the decider to see what happens. Then he refers to halting problem to say that such kind of dream is not possible.

However I notice that there's difference between halting problem and his scenario. Such a brute-force checking program has nothing to do with input data, but for halting problem, we assume the decider to check for every input. So I wonder whether halting problem without input is also undecidable?

I googled and found this. Personally I think it's wrong and couldn't be corrected because of self-reference.

Thanks for your help!

Here is a different proof using Berry's paradox instead of the liar paradox. Suppose that the halting problem (for programs with no input) were decidable. For each $n$, let $f(n)$ be the smallest number which cannot be computed by a program of length at most $n$ (without inputs). Consider the following program for computing $f(n)$:

  Go over all programs of length at most $n$, and for each one that halts, store the number it computes. Output the smallest number not encountered in this way.

This is computable since we can solve the halting problem for the relevant programs, and so we can determine which programs halt. What is the length of this program? The code itself is fixed apart from the length $n$, which can be encoded using $2\log n$ bits. All in all, this program has length $2\log n + C$ for some constant $C$. For large enough $n$ we have $2\log n + C \leq n$, and so there is a program of length at most $n$ which computes $f(n)$! This cannot be, and we are forced to conclude that the halting program is not computable.


What is a student process? According to Galvin and Silberschatz, 5 queues are maintained in multilevel queue scheduling, each for:

System Process
Interactive Process
Interactive Editing Process
Batch process
Student Process

where System process has highest priority and Student process has lowest priority.

What is meant by Student Process?

Also, I only have a vague idea about the rest except system process. If possible, elucidate them.

My best guess: a student process is a process run by a student.

All users have to log in. The OS may well know various types of users, and may be able to determine from some table that a given user is a student. This can be useful to lower their priority for computer time in a shared machine used mainly for research, or possibly do the opposite during exam period. So having a scheduling queue for student processes would make sense.

As far as I know ... there is no direct relation to learning machines who would run processes that are studying something. But who knows? It may be coming.


Merge Recurrence Analysis Say I have a dynamic array of the proper length $n$. A sort pivot is given.

I run the sort algorithm, wait, and get $j$ unbalanced pivots. Is the time complexity $O(n\log n)$ or has it destabilized to quadratic in the best case? I believe that it will be useful to use recurrences to model each scenario, but not sure how to set up from there.

This answer is for the following version of the post:

Say I have an array sized $n$. A quicksort pivot is balanced when each side of the partition ends up with $n/c$ ($c$ is a fixed constant). Else, the partition in unbalanced.
In both these cases, partitioning takes $pn$ time ($p=O(1)$). Let's say I run quicksort and after one balanced pivot, I get $j$ unbalanced pivots. Is the runtime still $O(n\log n)$? I believe that it will be useful to use recurrences, but not sure how to set up from there.

The running time should still be $O(n\log n)$. Intuitively, the size of the array decreases by a factor of $c$ every $j+1$ recursion levels, so the total number of levels would be $(j+1)\log_c n = O(\log n)$. The work at every level is $O(n)$, for a total of $O(n\log n)$.
How would a recurrence look? We will have $j+1$ different functions: $T_j$ for the balanced levels, and $T_0,\ldots,T_{j-1}$ for the unbalanced levels. The recurrences are
$$
T_j(n) = \max_{n/c \leq m \leq n-n/c} T_0(m) + T_0(n-1-m) + pn, \\
T_i(n) = \max_{1 \leq m < n/c} T_{i+1}(m) + T_{i+1}(n-1-m) + pn.
$$
Actually solving the recurrences could be a chore, so it's better to formalize the intuitive argument outlined above.


Prove that this language is not context-free I'm not very comfortable with pumping lemma for context-free grammar. I understand the sufficient conditions that must hold but proving it gets me everytime. For example, I need to prove whether $L=\{0^{2^n}∣n \geq 0\}$ is not context-free.

There is no pattern of 0's that can be recreated by a pushdown automata but alas I need to prove this. I know you start off assuming it is by being able to create a substring $uvxyz$ where $v$ and $y$ are raised to the $i$th power where $i≥0$. I'm having trouble from there, any help in this and the understanding would be greatly appreciated.

A unary language (a language over a unary alphabet) is context-free if and only if it is regular. The easiest way to see this is to convert a context-free grammar to a regular grammar using the fact that $xy = yx$ over a unary alphabet.

There are many ways of showing that $L$ is not regular, and so not context-free. One way is using the Myhill–Nerode criterion. Since $0^{2^n} 0^{2^n} \in L$ while $0^{2^m} 0^{2^n} \notin L$ for $m \neq n$, we see that the words $\{ 0^{2^n} : n \geq 0 \}$ are pairwise inequivalent, and so $L$ is not regular.

A proof using the pumping lemma is also not too difficult. Given a pumping length $n$, choose $m$ so that $2^{m-1} > n$, and consider the word $0^{2^m} \in L$. According to the pumping lemma you can write $0^{2^m} = xyz$ with $|xy| \leq n < 2^{m-1}$ and $|y| \geq 1$ so that $xz \in L$. But $xz = 0^{2^m-|y|}$ cannot be in $L$ since $2^{m-1} < 2^m-|y| < 2^m$. This contradiction shows that $L$ is not regular.


Why does a color video compress better than a black and white video? It was asked in an exam why a color video compress better than a black and white (grayscale) video using MPEG but can't find anything explaining it.

In other words, we would apparently get a better compression ratio when compressing color videos than when compressing BW videos.

Human eye is very sensitive to luminance change and order of magnitude less sensitive to chrominance change.
MPEG under the hood is based on JPEG transform, so you have 8x8 blocks of DCT.
It blurs a bit the whole block approximating it. Colour space changes to YUV or YCbCr, to encode two channels of colour and one of luminance.
Luminance (grayscale if it was colour) is not compressed as much as new created two colours. These colours are fitted more loosely than luminance.
The most heavy tricks are in colour space and luminance is preserved with lower compression (and less stages).

If you have BW frame it cannot be dealt with high compression as this faster degrades quality. MPEG was not created to deal with BW data. Origins of this codec are from times when grayscale tv was appended colour on top of existing frame.
Here I mean origins, not the same scheme as bandwidth was smaller at this time, I am referring to colour space and compression over chrominance.

MPEG popular scheme is 4:2:2 which encodes four parts of luminance (BW) and two times two colour parts. Colour is encoded as differences, because there are two channels and three colours.
So simply 50% of data is well preserved luminance and 50% are three colours with higher compression ratio. Compressed better means greater ratio of original vs processed channel.
Luminance takes (taking it simple as luminance is part of these colours) roughly equal space as colour info.

Different codecs are using different strategies, I referred to MPEG, not some new mixed schemes.


Complexity of variation of partition problem I want to know whats the complexity of the following variant of the partition problem:

Partition problem:

http://en.wikipedia.org/wiki/Partition_problem

Suppose we have one set formed by integers and we want to partition the set in two subsets of the same size, the same cardinality(the same number of integers in each subset) in such a way that each subset equal a given number called S.

Let's call this problem "2-partition" like the 3 partition problem

What's the complexity of the problem is easier,is in P?

Is still in NP?

I tried looking on google but i didn`t found anything, i dont even know if the problem is mentioned in some book or publication

Thanks

Is it in NP? Yes - any restricted version of an NP problem is also in NP.

Is it still NP-hard? Yes. 2-partition (without the constraint that both subsets should be equal cardinality) is NP-hard. Let's call your form of the problem "equal cardinalty 2-partition". To reduce from regular 2-partition to equal cardinalty 2-partition, we can pad the 2-partition problem by adding lots of extra 0's to the set, so that the 0's can be used to balance out any valid 2-partition solution to a solution that is an equal cardinality 2-partition.

You might object to the use of 0's in the input, and define "positive balanced cardinality 2-partition" where the input must be positive (so 0's are not allowed). But I can reduce any balanced cardinalty 2-partition problem to positive balanced cardinalty 2-partition by incrementing all numbers in the input by 1. This does not change the solution because of the equal cardinality constraint (each part of the partition gets increased by equally much).

Now you might still object that this reduction requires that you allow duplicate numbers in the input set. Even if you disallow duplicates in the input it remains NP-hard, and you can show so by a reduction from Positive 1-IN-3 SAT.

Is it in P? Answering this question would settle the P vs. NP problem so you're not very likely to get an answer any time soon.


provability of while loop vs for loop I'm abit afraid to ask this question here seeing as I asked it on programmers SE already, the thing is I think the question is more about the underlying theory than the use in practice (or call it confirmation bias). (If people here agree i should not have asked it here I will delete it and offer my sincere apologies) however I do think it will get a deeper meaning here as to why this is or isn't true.

Here is the question:
I have a teacher who (to me) seems quite intelligent, he really knows what he is talking about but he said something which surprised me (I'm paraphrasing): while loops can be proven where as for loops cannot.
I think this translates to: One can completely explain what happens in a while loop whereas you cannot do that for a for loop

Is my teacher right? (maybe this was the case when he started learning? ) and a more subjective question: Is there any clear reasoning behind this (why he would have stated this)?

In a nutshell: What your teacher probably meant is that the semantics of while is pretty much the same in most languages, while the semantics of for may change considerably (see discussion below). Hence, abstract language independent proof are more reliable with a while, but one should be careful that a proof with a for loop may not match the semantics of the for loop in many languages.

Your question is not precise enough (though that may not be your
fault).

The point is that, afaik, there is no official, ISO supported
standard, or otherwise officially accepted reference definition of
for and while loops. The definition depends on the programming
language.

Hence you cannot make any general statement regarding their
equivalence before you have defined precisely what each can do. I
adress that more precisely, since it is one of the main argument used
in other answers (and the discussion will be useful in what follows).

On intertranslatability of for and while loops

Summary: it depends on the programming language, but is always
possible a long as you can have one infinite loop and a way to get out
of it.

But you can make such a statement for a specific programming language,
and the answer will depend on the features fo the language.

That also means that there is no general proof, but only one for each
programming language.

One thing that is generally true is that a while loop can generally
mimic a for loop, because the while loop can do the exit condition
testing of the for loop, doing the initialisation of the control
variable with an assignment before entering the loop, and doing the
incrementation at the end of the loop body, so that

for i from 1 by 2 to 10 do { xxx }

becomes

i=1
while i≤11 do { xxx; i←i+2 }

This more or less works for most languages, but it is not as obvious as
it seem, and there may be many "details" to worry about.

For example, in many languages, the for loop evaluates it 3
arguments (initial value, increment, and final value) as strict
arguments, evaluated once before entering the loop, while others will
take then as thunk arguments to be reevaluated at each turn, or
possibly as lazy argument to be evaluated only when first needed.

Another point may be that the increment variable may be local to the
for loop, or have to be a local variable of the function where the
loop appears.

Depending on such issues, the translation of a for to a while may
vary widely, though it is usually possible to achieve it.

The same holds for the converse, thranslating a while into a for loop.

Th first problem is that a while loop will always reevaluate the
exit condition at each turn. But some for loops do not provide for a
condition that is reevaluated at each turn, other than comparison of
the control variable with some fixed value computed on loop entry.
Then the translation is not possible unless there is some other mean
to jump out of the loop on some arbitrary conditions.

That is achievable with various devices, usually starting with a
conditional statement testing the condition, followed by an a jump out
implemented, as available, by a loop exit statement, a return
statement (after encapsulating the loop in a function), a goto
statement or an exception raising.

In other words, it is again very dependent on languages, and possibly
on subtle features of languages.

This say, as answered by @milleniumbug, the intertranslation is easy
in the language C, because a for lopp is essentially a while loop
plus some extra for an incremented control variable.

But this does not necessarily apply to other languages, and most
likely not in the same way.

This being said, programming languages are usually supposed to have
Turing power with only one of these loops, since all you need for it
is one infinite loop. So, as long as you have some way of looping for
ever, and possibly deciding to stop, you are pretty sure you can mimic
any other construct ... but not necessarily easily.

Regarding proofs

Summary: There is no reason known to me to assert that proofs should be significantly harder with one or the other (unless some weird feature of the language).

There is probably a misunderstanding, or your teacher had his mind on
something else.

Formals semantics can be defined for the various kinds of loops
defined in programming languages, and then used for proving
properties.

It may be, again depending on the language, that conducting formal
proofs regarding programs may be more complex in some cases. But that
depends on the language.

I cannot imagine a reason why proofs should be significantly harder with one construct more than with the other. The for loop may be more complex since it can offer, as in C, all that is done with a while plus other things. But if you did it with a while, you would have to add the extras in some other form.

I could use the formal general argument of intertranslatability, as long as there is the possibility for a single infinite loop. I will however refrain from doing that, as the constructions involved are nothing you want to deal with in a proof, and it would clearly be an unfair statement, at least in practice.

Following the above discussion, however, we have seen that the difficulties for intertranslatability come from the great variability of the for loop from language to language. Hence the following conclusion which is probably the right answer:

One possibility to understand your teacher's statement is that the semantics of the while loop is pretty much the same in all programming languages, while the syntax and semantics of the for loop can vary significantly from language to language. Hence, it is possible to make general "abstract" proofs with while loops that have language independent semantics to a good extent, while this is not possible for the for loop that has syntax and semantics changing too much from language to language. But this does not apply within a given language, when the semantics of both are precisely defined.

My best suggestion is that you should ask your teacher what he precisely meant, and whether he can give you an example. Misphrasing or misunderstanding is a common event.


Are conditionals necessary in computation? I know this question might seem weird, maybe I'm just overthinking, but this is really troubling me because I've been a computer engineer for some time now and conditionals (if statements for instance) always seemed pretty clear and intuitive!

I mean, let's assume that I have a program which starts at

int main(int argc, char** argv) // in C

How am I supposed to know what is inside argv and argc? My old, intuitive answer: if statements. Using if statements, I would decide based on the input how to execute my program... I never considered any possibility other than having the input provided under this way, and I, as a programmer, could only mess with what is after the call to the program, with the input already defined. Hence I had no doubt that I needed to use conditionals.

I have ONLY 1 PROGRAM that needs to execute for ANY input and provide the right answers, hence I can't avoid if statements. It all seemed alright, for years now... until I started to think... Could there be other ways?

What if I had a different version of my program for each possible input? The operating system or the hardware could then call a different version according to the input. Then I thought – this would simply delegate the if statements to either the operating system or the hardware, respectively.

Then I even thought, what if the user had a different computer for each different input? I know this might seem really stupid, but I'm just trying to understand the "law" behind the need for conditionals in our physical world!

Also, in this last example it could be argued that the conditional would simply have to be executed in the user's brain (when he decides which computer to use based on the intended input).

Can someone give me some light in this subject? This is really troubling me :( maybe I've overthought things and now I'm paying the price for it...

One argument that conditionals are not fundamental to computation is that there are turing complete models of computation that don't use anything resembling conditionals. For example, you can think of the lambda calculus as an untyped programming language where the only operation is function application. There is no branching involved: all the computation is just taking the function's arguments, and substituting it in for all uses of that argument inside the function itself.

But, another way of looking at this is that any turing complete model of computation can simulate conditionals in some way. For example, a simple idea for branching in the lambda calculus is that "true" is a function that takes 2 inputs, an if branch and an else branch, and then returns the if branch $(\lambda x. \lambda y . x)$. Meanwhile "false" is a function that takes 2 inputs, an if branch and an else branch, and returns the else branch $(\lambda x. \lambda y . y)$.

Then, in the lambda calculus, a program like "if T then foo else bar" would be encoded like $(T)(foo)(bar)$, which is to say applying foo and bar as arguments to the function T.

Or, more trivially, every turing complete model can simulate the turing machine, which is a state machine (and thus evaluates based on a conditional at every time step).

Anyways, as for the more realistic models of computation that you are used to, one reason you need conditionals is because if you didn't have conditionals, every program you write would either loop forever or execute in O(1) ((where we consider the size of your program to be constant)). Think about it: no conditionals means no loops (unless you use an unconditional jump, but then you will just loop forever). But, without loops, each line of your program will be executed exactly once. Thus, every program runs in O(1). This essentially means you can't solve any interesting problems.

However, I would argue that the more fundamental issue here is that loops (or some equivalent, such as combinators) are fundamental for computation. If you remove the ability to make a "goto", then even with conditionals your language will not be turing complete (by the same argument: your code will simply execute along some control flow path exactly once then terminate in O(1), and not every problem can be solved in O(1)).


How do we distinguish NP-complete problems from other NP problems? I just learned that when we have a polynomial algorithm for NP-complete problems, it is possible to use that algorithm to solve all NP problems.

So, the question is how we then distinguish non-NP-complete NP problems from NP-complete problems? It seems that all these problems will have a polynomial algorithm to convert into other problems...

To provide the flip side of 042's answer: it's important to understand that if $P=NP$ then every problem in $NP$ is $NP$-complete (caveat: under the usual poly-time reductions): $NP$-complete simply means 'every problem within $NP$ can be solved in polynomial time with an oracle for this problem'.  But if every problem in $NP$ can be solved in polynomial time—that is, if $P=NP$—then the second part of that statement is vacuous.

On the other hand, if $P\neq NP$ then it's known that the problems that are in $NP$ but not in $P$ have a very rich structure - in particular, there have to be 'intermediate' problems that aren't in $P$ but also aren't $NP$-complete, and in fact an infinite number of distinct ones (that is, such that at least one can't be reduced to the other).  For more details on this result (Ladner's Theorem), you might start with Lance Fortnow's notes on the topic.


Learning a small disjunction using an input distribution of our choice I have a boolean function $f: \{0,1\}^n \to \{0,1\}$ that I know takes the form

$$f(x_1,\dots,x_n) = x_{i_1} \lor x_{i_2} \lor \dots \lor x_{i_k}.$$

I don't know the values of $i_1,\dots,i_k$, but I do know $k,n$.  My goal is to recover $i_1,\dots,i_k$ from the value of $f$ on randomly chosen inputs, using as few evaluations of $f$ as possible.

There's a twist.  I can choose any efficiently sampleable distribution $D$ on $\{0,1\}^n$ that I want, depending on $k,n$.  A referee will pick $f$, randomly sample many values of $x$ from $D$ (iid), and then give me $(x,f(x))$ for each such $x$.  Then, my ultimate task is to infer $i_1,\dots,i_k$.

I'm looking for an efficient algorithm to select $D$ and then recover $i_1,\dots,i_k$, given the pairs $(x,f(x))$.  How efficiently can this be done?  What distribution $D$ is optimal?  The most relevant complexity measure is probably the number of pairs needed.  Randomized algorithms are OK.  I'm particularly interested in the regime where $k \ll n$.

This is a generalization of a prior question of mine, where I showed that if we take $D$ to be the uniform distribution on $\{0,1\}^n$ then $\Theta(2^k \lg n)$ pairs are necessary and sufficient.  However, it seems likely that the uniform distribution is not optimal.  I suspect we can do better by choosing a distribution $D$ that is biased towards values of $x$ with lower Hamming weight.

On first glance, it feels like maybe we can restrict attention to distributions $D$ that is symmetric (i.e., $x$ and $\pi(x)$ have the same probability, for all permutations $\pi$ on the $n$ bits).  For instance, we could consider a distribution $D$ where the bits of $x$ are iid Bernoulli(p), for some parameter $p$.  Is this right, and if so, what is the optimal distribution $D$ and how many pairs does this mean we will need?

This is motivated by an application in inferring input-output relationships in programs (black-box taint analysis).

$\Theta((k+1) \lg n)$ pairs are sufficient.  I think this is the best that's achievable.

Here's the distribution $D$ that achieves this result.  Let $p = 1/(k+1)$ and choose each bit of $x$ from Bernoulli(p) (i.i.d.), i.e., each bit of $x$ is $1$ with probability $p$ and $0$ otherwise.

Call $x$ good if $f(x)=0$.  Note that if $x$ is chosen according to $D$, it has probability $(1-p)^k$ of being good.  This is $(1-1/(k+1))^k$, which is approximately $e^{-1}$ (using the standard approximation $(1-y)^z = e^{-yz}$).  So, $\Pr[f(x)=0] \approx 1/e$, and about a constant fraction of pairs are good.

Now we can take all of the good pairs we have, and look for bit positions that are consistently zero in every good pair.  If we have enough good pairs, only correct positions $i_1,\dots,i_k$ should remain.  Fix a particular incorrect bit position; it has a probability $p$ of being eliminated by each good pair, so the probability that it survives all the good pairs is $(1-p)^g$, where $g$ is the number of good pairs.  Taking $g = -2\lg(n)/\lg(1-p) \approx 2 \lg(n)/p$, we find that the probability of survival for a single incorrect bit position after all $g$ good pairs is $1/n^2$.  By a union bound, this means the probability that any of the incorrect bit positions survive is about $1/n$.  In other words, if we have $2\lg(n)/p$ good pairs, with overwhelming probability this procedure will succeed in correctly inferring $i_1,\dots,i_k$.

Putting these two together, we need about $2e \lg(n)/p$ pairs.  Since $1/p=(k+1)$, this is $\Theta((k+1)\lg n)$.

It's possible to show that this is the best possible value of $p$.  Define $f(p) = p (1-p)^k$.  Then
$$f'(p) = (1-p)^{k-1} (1-(k+1)p),$$
since $f'$ is zero at $p=1/(k+1)$, and one can verify that the maximum value of $f(p)$ on the interval $[0,1]$ is attained at $p=1/(k+1)$.  Now the total number of pairs needed by the above procedure is $2 \lg(n)/f(p)$, which is minimal for $p=1/(k+1)$.  This justifies the choice of $p$ suggested above.

I'd conjecture that you can't do better than this class of distributions $D$ (where each bit of $x$ is chosen iid Bernoulli).  If that is right, then it follows that the result given above is the best possible: $\Theta((k+1)\lg n)$ pairs are necessary and sufficient to solve this problem.


How to determine the maximum valued play in Rummikub? This question is meant as a follow-up this question and my answer here.

The question asked multiple questions about algorithms for playing Rummikub and my answer provided an algorithm that, given a set of Rummikub pieces $S$, determines whether they can be arranged as a set of valid plays (called an arrangement).

However, when we actually play Rummikub, the situation is slightly different: there is a given board state $B$ and a hand $H$. We want to empty our hand by adding pieces to the board. We assume the board $B$ has a valid arrangement.

So, the problem now becomes:

  Does there exists a subcollection $S\subseteq H$ such that there exists a valid arrangement for $S \cup B$; and
  What is the largest such subcollection $S$ ?

Obviously, we can iterate over every subcollection $S$ of $H$ and test validity for each of them, but that is inefficient. To make precise what I mean by 'efficient' here, consider the game to be played with $3,4$ or $5$ colours and the numbers $1\ldots n$ for each color.

Does there exist an polynomial (in $n$) time algorithm that solves problem 1 or 2? Or this 1 or 2 intractable (e.g. NP-hard)? Feel free ignore complications such as jokers or assume all tiles are distinct.

I will describe a polynomial time algorithm that solves both problem 1 and problem 2. I learned of the algorithm from this paper.
I am going to make the following assumptions:

No jokers (adding them is a small change).
There are only four colors.
There are at most two copies of each tile.
The face values range from 1 to 13.

To find the maximum value play, complete these steps:

Recursively enumerate every valid configuration that can be built from tiles in $hand \cup board$
Ignore any configuration where not all tiles from board are used (the board constraint).
Of the visited configurations, choose one with maximal score. Where score is the sum of values of tiles played or number of tiles played (whichever you prefer to maximize).

Step 1
How do we build a configuration from a given set of tiles?
We proceed by playing tiles in order of their face value.
First play all tiles of value 1.
Then play all tiles of value 2, and so on.
We can visit every configuration by recursing for each way to play tiles of the current value.
Let's look at the different ways to form runs.
Assume we are playing tiles of value 5, that we have a red 5, and that we will use it in a run.
Our tile can be used to start a new run or it can be used to extend any existing run (or partial run) that contains a red 4.
If we extend an existing run then there is at most two choices for where to put it since there is at most two runs that contain a red 4 (there are at most two red 4's).
If we have two copies of our tile then we can extend or start two runs.
In forming runs there is an optimization that can be made.
We should not start a new run if we know in advance that there is no way we could finish the run.
This can be implemented by counting the number of tiles of greater value.
Now on to forming groups.
For a given way to play runs we should recurse for every way to play groups using the remaining tiles since we want to enumerate all possible valid configurations.
However this would be very slow and in the end we really only care about finding the best configuration.
So instead we recurse for only the best way to play groups.
Notice, for a given choice of how to form runs, how we form groups does not effect what choices we have in forming groups and runs using tiles of greater value.
So given a choice of how to form runs, we should use as many of the remaining tiles in groups as possible.
To do this enumerate all ways to pick groups and choose the one containing the most tiles.
Finally after choosing how to play all tiles, discard any tile not used in a valid set.
Step 2
How do we ensure every valid configuration we visit uses all tiles from board?
After choosing how to play all tiles and discarding invalid sets, do not accept the configuration as valid if not all tiles from board are contained in it.
This is correct but it would be inefficient.
Instead we check at each step, after choosing how to form runs and groups, whether we have used enough tiles of the current value.
For example, if the current value is 5 and we have chosen a way to play the red 5's, then we need to check if we have played at least as many red 5's as are contained in board.
If we have not, then we choose another way to play red 5's before moving to the next value.
Note if we have played $n+m$ red 5's where $n$ is the number of red 5's in board, then we have played $m$ red 5's from our hand.
If there is no way to play red 5's (including not playing red 5's) then this branch of the recursion tree does not lead to a valid configuration and we should return.
However, these checks are not sufficient to guarantee we never violate the board constraint. Why?
Because when forming runs using tiles of value 6 we can choose to not extend a run that has length one or two.
The tiles in that run would have to be discarded which could violate the board constraint due to not having enough 4's or 5's.
In this case we would not be able to catch this error because so far we only know how to check the board constraint for the current value.
The way to fix this is to keep count of how many tiles we have played of the previous two values (for each color separately).
Then when forming runs with red 6's we can check if not extending a red run (of length one or two) puts us in a state where not enough red 4's or 5's have been played.
Note that if a run has length at least three then not extending it does not force us to discard any tiles and so can not violate the board constraint (so we do not have to check in this case).
We do not have to do anything special for choosing groups. In the following proof of this fact I will use 'configuration' to mean a set of groups.
Also, I will use 'maximal configuration' to mean a configuration containing the most tiles possible among all configurations where tiles come from some set $S$.
Note that if we have $n$ tiles of color $c$ in a configuration then there are at least $n$ groups in the configuration.
Also if a subset of the available tiles can be arranged into a configuration of $n$ groups then a maximal configuration contains at least $n$ groups (there are at most three groups, if using two jokers, and at most two groups of four in any configuration).
Now assume a subset $S$ of the available tiles can be arranged into a configuration with $n$ tiles of color $c$ and that we have arranged some maximal configuration $M$.
If $M$ contains $k < n$ tiles of color $c$ then $M$ contains at least $n - k$ groups which do not contain a tile of color $c$ (groups of size three).
In this case we can add $n-k$ tiles of color $c$ from $S$ to $n-k$ groups of three in $M$ which contradicts that $M$ is a maximal configuration.
Thus $k\geq n$.
This shows that if there are $n$ tiles of color $c$ in the set of tiles of current value that remain after playing runs and if those $n$ tiles can be played in some configuration then every maximal configuration contains those $n$ tiles.
So choosing a maximal group guarantees that we satisfy the board constraint if it is possible to satisfy the board constraint by playing groups.
Step 3
A simple way to do step 3 would be to compute the score of a configuration when you accept it as valid then update some global variable with the configuration of max score ('configuration' meaning set of runs & groups).
But this solves the same subproblem many times (compute score for sets common to more than one valid configuration).
Instead make use of the fact that we know at each step how many tiles of the current value we will play.
Multiply this number of tiles by the current value to find how much these choices contribute to the score.
Sum the contribution with the return value of the recursive call and then update the max if necessary.
Instead of updating a global max variable, we will update a local (available only in scope of recursive call) max variable which will hold the score of the best way to play tiles of the current value.
The recursive function should return the value of this max variable.
After attempting to play tiles of current value in all ways, if no play leads to a valid configuration (every play violates the board constraint), then return $-\infty$.
Returning $-\infty$ is useful because even if we have a high contribution (from runs & groups), adding that contribution to $-\infty$ is still $-\infty$.
Note that we cannot know the contribution of extending a length zero or length one run. This is because, when playing tiles of the next greater value, we may choose to not extend a run of length one or two and so the tiles in those runs would be discarded.
Instead we say the contribution of extending a length zero run (starting a run) or length one run is 0.
When a run is extended from length two to length three then we say it's contribution is the sum of the values of the three tiles in the run.
When extending a run that has length at least three then the contribution is just the value of the tile played into the run.
There are other things you can do here too. For example, It may be desireable to find a configuration that is maximally similar to the previous configuration of the board.
This can be done by maximizing score and then maximizing some similarity function. This would inflate the dp table size by two.
State, Memoization, & Time Complexity
The only state we need to know is the current value and the length of the runs that we could possibly extend.
The length of runs can be recorded in a list of pairs, for example [(0,0), (0,0), (0,1), (0,3)], where the $i^{th}$ pair is the length of the two possible runs of color $i$.
The order of the numbers in the pairs does not matter so the above state is the same as [(0,0), (0,0), (1,0), (0,3)].
A particular extension (i.e. child state) of those runs could be [(1,1), (0,1), (0,0), (1,3)].
Also, we never need to know if a run is longer than three tiles (so an extension of (3,3) is (3,3)).
We will only need to distinguish between when a run is of length 0, 1, 2, or 3.
A benefit of this is the size of the state space is reduced which makes memoization much more effective.
This algorithm is exponential in the number of distinct values in $hand \cup board$.
However it can be made linear by memoization.
To memoize, store in a dictionary the key-value pair key=(currentTileValue, runLengthsList) and value=localMaxValue.
Other inputs like the board, $hand\cup board$, number of jokers available, number of tiles played per color on the last two turns, etc, are just used to bound the search and so we do not need to memoize them.
Hopefully I have been able to effectively communicate most of the ideas of this algorithm.
For more details see the paper and my implementation.
Note, the paper claims that the dynamic programming state space (number of unique inputs, max size of dp table needed, i think) is of size $n * k * f(m)$.
Where $n$ is the number of possible tiles, $k$ is the number of colors, $m$ is the max number of copies of a tile, and $f(x)$ computes 4 choose $x$ with replacement.
This might be a typo, I do not know.
In any case the state space of the algorithm I've described is $n * f(m)^k$.
Note both the paper and my implementation refer to what you call the board as the table.
By the way, before learning of this algorithm, I tried to understand the algorithm you gave here.
I could not understand how to deal with duplicates.
I can see how breaking into sublists, ordering those sublists, and then combining them into a single list again would allow your recursive formula to handle duplicates for some inputs.
But you did not describe how exactly to break the original list into sublists nor how to combine them into a single list again.
For some inputs, your recursive formula will give different answers depending on how sublists are split/recombined.
Unfortunately, I do not have enough stackoverflow reputation to comment on your answer to ask for clarification.
Thanks for giving the answer though, your recursive formula is nice.


What is the theoretical speedup with pipeline system over a nonpipelined system? What is the theoretical speedup that could be achieved with the pipeline system over a nonpipelined system?

The equation I use for speedup is

$$ S = \frac{nT}{(k+n-1)t}\,$$

where:

$n$ is the number of tasks
$T$ is the time to process a task
$k$ is the number of stages segments
$t$ is the time per stage segment

I dont understand how to use this equation for this particular question.

The total time to compute $n$ tasks with no pipelining is $nT$ (the top of your fraction).  The total time to compute $n$ tasks with a pipeline $k$ stages deep, and a clock cycle time of $t$ is $nt$ (to produce the results once the first task reaches the last pipeline stage) + $(k-1)t$ to get the first task from the beginning of the pipeline to the last stage.  This is the $(k + n - 1)t$ in the bottom of your fraction.

The part you are missing is that $kt$ (the time for each task to get from beginning to end of the pipeline) must be larger than $T$.  This is because in the perfect case you would divide the circuit of delay $T$ into $k$ exactly equal segment, but then you would need to insert a register between each segment and the next, which will add delay.

So replace $t$ with $T/k$ in your fraction and take the limit as $k\rightarrow\infty$ and you will have your answer.

More interesting is to replace $t$ with $T/k + r$ where $r$ is the  constant extra register delay that you need to add between stages, take the derivative of your fraction with respect to $k$ and set it equal to 0 and solve


Which sorting algorithm is most efficient to 'continuously' sort a vector again and again? I have an uncommon use case

I have a vector, which contains a fixed number of taxi's real-time fees (the red/green number that keeps bumping up when you sit in the back).

This vector is continuously updated by message sent back from taxis. I need to find the top 10 taxis every time when there is an update.

if I only need to do this once, then std::sort() or std::partial_sort would easily solve the problem. However, since the vector is largely the same after only a few updates, the sorting result from step T should be largely the same as sorting result of step T+1

I am wondering if the std::partial_sort will be 'smart' enough to 'incrementally' sort the vector, rather than start-over again from scratch.

Can anyone share any ideas here?

Thanks!

Look at what your problem actually is: Your problem is not sorting the list, but finding the largest ten items. That's a much easier problem, which can be solved without sorting the list again and again.

Start by finding the top ten items once. Let $X_{10}$ be the value of the tenth largest item.

If an item outside the top ten is changed to a value ≤ $X_{10}$, ignore it. If it is changed to a value > $X_{10}$, then drop the tenth item and insert the changed item in the array in the right position.

If an item in the top ten is changed then move it up or down according to the new value. If the new value is less than < $X_{10}$ then remove it from the top ten leaving you with the top nine, find the largest item that is currently not in the top nine, and put it into the tenth position.

So most of the time you do no work at all, a lot of the time very little work, and occasionally it takes linear time.


Design a DFA that recognizes the following language My assignment asked to design a DFA that computes the language:

$L = \{ w \in \{a,b,c\}^\star | \#_a(w) $ is even, $\#_b(w)$ is odd, $\#_c(w)$ is even}

I have been stuck on this question for 2 hours, I draw approximately 20 sketches but still fail. The only thing that I observed so far is we need at least 8 states, or maybe more. And if a non-accept state reads a letter to an accept state, then it must read the same letter back to the non-accept state, or vice versa.(to keep the property of even or odd numbers) But I'm failing to handle all the cases, such like I can handle aabcc, ccbaa, but fail to abcbbca or abcbbac.  Any suggestions?

As mentioned in the comments, you’ll need 8 states exactly. I like to label my states with semantic meanings, so in this case I’ll use a 3-digit number where each digit represents the number of as, bs, or cs we’ve seen ($\mod 2$).

Then we have all the states from $000$ to $111$ in binary.

You already know that $000$ is the start state and $010$ is the accept state.

All that remains are the transitions, which are independent of the accept rules at this point. From each state, there are 3 transitions: one for each of a, b, and c.

But now notice that for each letter, the corresponding transition is to the state with the corresponding bit flipped! For example, $110 \xrightarrow{a} 010$.

More mathematically, for any state $\alpha\beta\gamma$:

when we see an a, we go to the state $\alpha'\beta\gamma$, where $\alpha'$ is 1 if $\alpha = 0$, and vice versa;
etc., for the remaining letters.


Lamport’s fast mutual exclusion algorithm intuition Here's Lamport’s fast mutual exclusion algorithm:

want[i]:=true
fast-lock:=i
if slow-lock<>0 then
     want[i]:=false
     while (slow-lock<>0) {//busy wait}
     goto 1
slow-lock:=i
if fast-lock <> i then
     want[i]:=false
     for j:=1 to n do:
       while (want[j] = true) {//busy wait}
     if slow-lock <> i then
         while (slow-lock <> 0) {//busy wait}
         goto 1
CS
slow-lock:=0
want[i]:=false

I understand why eventually all 4 criteria for mutual exclusion hold,
 but i dont understand the intuition behind this algorithm:

In what sense are this locks fast/slow?
What's the point, for    example, after freeing the slow lock, go
back to the beginning of    the algorithm?

I tried to read this article, but it was to complex for me to understand.

In what sense are this locks fast/slow?

Lamport optimizes for a very specific scenario, as pointed out in the paper:

  The current belief among operating system designers is that contention
  for a critical section is rare in a well-designed system; most of the
  time, a process will be able to enter without having to wait.

The reasoning goes like this: Most of the time, only a single thread will attempt to get into the critical section. So the codepath that we should try to optimize is the one where the lock is readily available.

The case where there is actual contention on the critical section is considered exceptional. It is fine if the algorithm behaves less than ideal in that case - less than ideal here means, you will never let more than one process into the critical section, but if there's lots of contention, you might have to wait a long time (possibly forever) for your turn to enter the critical section.

To illustrate this point, let's take a look at a classic algorithm for mutual exclusion (coincidentally also by Lamport), the Bakery algorithm. Here, in a nutshell, a thread that wants to enter the critical section picks a number that represents its place in the waiting queue. The thread with the smallest number is at the front of the queue and can enter the critical section, all others have to wait. How do we determine whether we have the smallest number (and hence can enter the critical section)? We have to compare our number against the numbers of all the other threads. This means even if none of the other threads are in the queue at that time (no contention), we have to check the numbers of all the other threads. This is obviously not nice, as locking becomes more expensive as the number of threads increases.

The fast mutual exclusion avoids this: If there is no contention we check slow-lock, which is available. Then we check the fast-lock, which is also available and we enter the critical section. We only need two write operations and two read operations to get into the critical section, regardless of the number of threads.

  What's the point, for example, after freeing the slow lock, go back to the beginning of the algorithm?

It's the only safe thing to do. Remember, it is crucial that no more than one algorithm is allowed to enter the critical section. If we fail the slow-lock check, it means that some other thread might already be in the fast-lock check or even in the critical section. Thus we have to back off and restart from the beginning. We will keep doing this until the other thread has left the critical section, which will allow us to pass the check.