A relational algebra extended to model the full DML ("CRUD") domain

Excellent question, and since you referred to us ("jOOQ developers", which I am - working for the company behind jOOQ), I feel qualified to give a partial answer.

A bit of historic context first

Since the very beginning of software, there had been:

Theory (which is what "Computer Science", i.e. this Stack Exchange subsite is about)
Practice (more like Stack Overflow, i.e. "how can I get the compiler to stop barking at me")

The origins of set theory, relational algebra, and relational calculus were clearly on the theoretical side. Up to this day, popular RDBMS implementations have only managed to approximate this theory, mostly through SQL.

Although there had been competing languages before SQL was standardised mainly by Oracle and IBM, the power of SQL lay in the fact that it was a very practical language, which worked sufficiently well both for computer programs (e.g. written in COBOL, which was an equally practical language), software engineers, and most importantly: "other people", including analysts, project managers, and also managers. Everyone can quickly write up a SELECT * FROM person WHERE first_name = 'John' query. More theoretical languages like QUEL, which would have been closer to relational calculus, lacked the business vision that Oracle had.

Since then, SQL has emancipated from the outdated relational model and embraced a lot of alternative models, including procedural extensions (stored procedures), OLAP features, XML, JSON, etc. Not all of these enhancements were very well executed. To this day, the XML integration, for instance, is rather weak, poorly standardised and hard to grasp. I'm just speculating that the ANSI/ISO/IEC SQL standards committee and the w3c didn't work together closely enough to truly embed XQuery into SQL at the time. Unfortunately for w3c, as hardly anyone is using XQuery today, while everyone still uses SQL.

The historic irony here is that a lot of innovation came from academia, and I'd like to specifically mention Michael Stonebraker (Quel, Ingres, the original Postgres, Vertica, H-Store, and much more) who was recently awarded with the well-deserved turing award. Stonebraker has always been innovating into new areas. Most of the recent in-memory column store "hype" (also often referred to as "NewSQL") evolved around him. Stonebraker is a good example of the difference between academia and business. We've blogged about this some time ago here:

http://blog.jooq.org/2013/08/24/mit-prof-michael-stonebraker-the-traditional-rdbms-wisdom-is-all-wrong (very interesting talk by Stonebraker)
http://blog.jooq.org/2013/08/27/column-stores-teaching-an-old-elephant-new-tricks

When you hear the excellent talks by Oracle's Andrew Mendelsohn for instance, or other influencers from companies like Microsoft, SAP, IBM, you will notice that business has always embraced SQL for very good reasons, which were often not at all academic.

Context for your question

You have to differentiate between around four levels of abstraction:

Relational calculus
The SQL standard
The SQL Server specification
The SQL Server implementation

Your example is a particularly interesting one, because UPDATE .. SET .. FROM is not part of the latest SQL:2011 standard. To our knowledge, the UPDATE .. FROM clause is supported in at least:

SAP HANA
Ingres
Postgres
SQL Server
Sybase

Other databases allow for updating views, e.g.

UPDATE t1 JOIN t2 ON ... SET ...
UPDATE (SELECT * FROM t1 JOIN t2 ON ...) SET ...

In terms of Codd's Rules, the following two would apply:

  Rule 6: The view updating rule:

  All views that are theoretically updatable must be updatable by the system.

  Rule 7: High-level insert, update, and delete:

  The system must support set-at-a-time insert, update, and delete operators. This means that data can be retrieved from a relational database in sets constructed of data from multiple rows and/or multiple tables. This rule states that insert, update, and delete operations should be supported for any retrievable set rather than just for a single row in a single table.

So, Codd demands that an RDBMS can update views using sets, but he wouldn't want to specify how to actually do that (e.g. syntax-wise).

In fact, the concrete rules which apply to these kinds of statement are rather different from database to database. This has nothing to do with the SQL language, or with relational calculus per se, but simply with the individual implementations of each database - often also because of how the locking / concurrency model is implemented - something that is left open to implementations by both Codd's Rules as well as to some extent by the SQL standard. For instance, the standard does not explicitly refer to MVCC.

In the particular case of UPDATE .. FROM, think of it this way (assumptions only):

Some customer probably wanted to be able to write UPDATE statements that take into account more than one table
Some database vendor then implemented a "reasonable" syntax that fits into the general feeling of writing SQL
Some other database vendor then copied this syntax in order to provide migration paths, but "improved" on syntax and/or semantics
Yet another database vendor (probably IBM or Oracle) came up with yet another, much more powerful syntax for such use-cases, namely MERGE
As that database vendor has closer ties to the ANSI/ISO/IEC standards committee, and as this syntax was clearly more useful, MERGE now became a standard, and is now implemented in more and more RDBMS. To our knowledge in at least:

CUBRID
DB2
Firebird (upcoming 3.0 only)
HSQLDB
Informix
Oracle
SQL Server
Sybase SQL Anywhere

Answer to your questions

  Are jOOQ developers breaking ground with new and proprietary ways of understanding DML operations [...]?

We're not really breaking ground here. Before jOOQ, there had been many many SQL parsers and translators / migrators that allowed for standardising some vendor-specific SQL features. One example is Gudu Software's SQL Parser - the use case being migrating off DB2 towards Oracle, for instance.

What's new in jOOQ is that we introduced another "SQL dialect" implemented directly in Java, which mimicks a bit of the SQL standard and a bit of popular vendor-specific SQL dialects. Since jOOQ users explicitly create an Abstract Syntax Tree in their Java programs by using jOOQ API, jOOQ can easily perform a lot of SQL transformation internally in order to standardise the generated SQL output for all currently supported ~20 RDBMS, without the need to previously parse SQL statements (which is extremely hard). This extends to DML statements only to a certain degree, of course, as the underlying database implementation still needs to be able to process the semantics of a given statement.

What's also new (or at least different) in jOOQ is that unlike HQL, JPQL, LINQ, and many other abstractions, jOOQ is sticking to SQL instead of embedding also other concepts / domains like objects (ORMs) or XML/Collections (LINQ)

  Or is there published work on this?

jOOQ is not academic work. It evolved from real user needs over the past 6 years. We're following SQL here as we want to follow real business needs. We're not aware of third-party publications about jOOQ, although there had been a lot of similar papers about other, similar APIs in the past:

The World According to LINQ (and many other publications) by Erik Meijer
Embedded Typesafe Domain Specific Languages for Java by Jevgeni Kabanov and Rein Raudjärv
Database Queries in Java by Christopher Ming-Yee Iu (see also our article)

Embedding an external language like SQL in Java is rather easy, though. The basic technique is published in our article

The Java Fluent API Designer Crash Course

  I'm so far overwhelmed trying to reverse-engineer the domain models from an implementation.

So are we :-)

As you can see, SQL is a very real-world, pragmatic, sometimes (often) a bit ugly, vendor-specific (although well standardised), huge thing. The SQL:2011 standard's main document has almost 1500 pages, including DML (you can find some publicly available draft document versions here, for free). This doesn't even include extensions like XML, the INFORMATION_SCHEMA or other extensions.

Most people I've talked with in the past would agree that we really need something better than SQL. But the ugly truth is, there is nothing better than SQL right now, and even if there were, it would have to be backwards-compatible. There is no way that our whole industry will stop using the excellent and huge tool-chain that has been built around SQL. If "NoSQL" databases want to be successful these days, they build SQL-esque langauges (e.g. Cassandra with CQL, Couchbase with N1QL, Neo4j with Cypher). Oracle shows that SQL-on-Hadoop (BigDataSQL) is possible, and SAP's HANA completely bypassed NoSQL and implemented their number-crunching in-memory database directly on top of SQL.

The flip-side of this focus on practicality is that the academic quality of something like UPDATE .. FROM deteriorates to a point where you simply shrug and accept that this is merely a useful, perhaps a bit weird SQL statement.

TL;DR

If you want to understand the individual error messages that your SQL Server instance displays to you, then you're probably best off learning about SQL Server first. These concrete, real-world problems are so far away from the original theory ("Codd's Rules", "Tutorial D") that you'll be much better off bypassing the theory for these cases.


Logistic model and Linear regression model

You should just keep reading:

  These predictions are not sensible, since of course the true probability of default, regardless of credit card balance, must fall between 0 and 1.

A probability cannot be smaller than 0 or larger than 1. The problem is that the model might predict such a "probability".


Computability of an expression of a function rather than a function itself?

I assume that a closed form of a function is a finite expression involving function symbols from some fixed natural finite list together with some real[1] parameters. Since we know what it means to compute a real number, and since we know what it means to compute finite tuples of stuff we know how to compute with, we obtain in a direct way a notion of what it means to compute a closed form of a function.

Then in particular we can ask questions such as "given these parameters for the differential equation, can we compute a closed form of the solution".

Note however that all usual continuous functions are computable. Given a closed form of a function $f$ and some input $x \in \mathbb{R}$, we can compute $f(x)$. However, the problem "given a continuous function that has a closed form, find that closed form" is not computable.

So asking for closed forms is asking for more, not asking for less.

[1] If you don't like computing with real numbers, go for parameters from the algebraic closure of $\mathbb{Q}[\pi,e]$ instead.


How does one choose an optimal alphabet for finding a Huffman encoding?

The size required to store the Huffman code table scales like the number of codewords. We expect the number of unique $k$-letter words to be exponential in $k$, in fact roughly $2^{kH}$, where $H$ in the source entropy, though since the file is not infinite, for large $k$ we will actually see less. Still, this suggests that for logarithmically large $k$, most of the $k$-letter strings will be almost unique, and so the overall compression for such a $k$ would typically be quite small. In view of that, you can just try several values of $k$, and choose the best one. After you do some such experiments, you can formulate and perhaps prove a hypothesis as to the optimal value of $k$ in different situations.


Different iterations of regular expressions

First, note that, over any finite alphabet, there are countably infinitely many regular expressions. This is immediate from the fact that regular expressions are finite strings (which gives the upper bound) and that $a$, $aa$, $aaa$, ... are all regular expressions (which gives the lower bound).  From now on, I'm just going to say "infinite" instead of "countably infinite" because we've established that nothing in this context is uncountable.

If you're allowed to use $\varepsilon$, there are infinitely many regular expressions that match $abcd$: for example, $abcd\epsilon^n$ for all $n\geq 0$.

If you're allowed to use alternation, there are infinitely many: for example, $abcd$, $(a+a)bcd$, $(a+a+a)bcd$, ... .

If you want regular expressions that match only the string $abcd$, Kleene star isn't useful. If it's applied to any regexp that matches any non-empty string, then the resulting regexp will match strings of arbitrary length, so will be invalid. If it's applied only to regexps that are equivalent to $\varepsilon$ then we could have already used those regexps to get infinitely many regexps for $abcd$, as in the $\varepsilon$ case. The only remaining case is that $\emptyset^*\equiv\varepsilon$, so Kleene star and $\emptyset$ together yield infinitely many regexps for $abcd$. However, this case isn't relevant in your case structure, since you eliminate $\varepsilon$ and $\emptyset$ from consideration at the same time.

If you're only allowed concatenation, then there is exactly one regular expression that matches $abcd$: $abcd$ itself.


Which method is preferred for storing large geometric objects in a quadtree?

Assuming you are storing a reference, not the object itself, it may make sense to do this differently depending on your application.

For instance, if you were computing collisions with this (solid) circle and the collision was occurring in the lower left hand corner, it'd be easier if you had access to all geometry in that leaf directly from that leaf (method #3) (without having to traverse the tree upward and determine inherited geometry). But, say you were just using quadtrees for drawing geometry, you'd want to use method #1, because it only makes sense to draw something in the node for which it is fully contained (it would be more difficult to figure out which portion to draw for each leaf node and where).

As for what is more commonplace, my only experience with quadtrees is with writing an n-body simulation where the geometric objects were really just points that had no area, so I can't definitively answer that.


Why is deciding regularity of a context-free language undecidable?

Myhill–Nerode does indeed provide a characterization of the regular languages but that isn't enough to show that the problem is decidable.  "Decidable" means that there is an algorithm (more formally, a Turing machine) that terminates for every input and, of course, always gives the correct answer.  So, in this case, you would need to give an algorithm that, given a language as input, determines whether the Myhill–Nerode relation has a finite number of equivalence classes.  It turns out that this cannot be done for context-free languages; details in your favourite formal languages textbook.

If you want to decide whether a general language is regular, a further subtlety is that you have to be careful about what is the input to your algorithm. The input must be a finite string – otherwise, even just reading the input would be a non-terminating algorithm.  In the case of context-free languages, you could use a grammar as a finite representation of an infinite language.  For more general languages, you would need... well, something more general.  Ultimately, though, if you want to deal with all languages, you're doomed.  Over any finite alphabet, there are uncountably many languages but only countably many finite strings. That means you can't possibly describe all languages using finite strings.1 Therfore, trying to write an algorithm to determine whether arbitrary languages given as input are regular actually fails before it begins. It's not just that you can't write the algorithm: you can't even write the input!

Note that this doesn't mean that you, a human being, can't use Myhill–Nerode to determine whether languages are regular. It just means that you can't write down a set of precise instructions to tell me how to do that.  At some point, any such set of instructions would have to say something like, "And then play about with it to see what works," or "From there, you have to figure it out on your own."

In particular, this means that some languages must be undecidable, since there are more languages than there are algorithms.


If a language is context free, then its complement is decidable

If $L$ is context free, it is decidable. Thus so is it's complement (to see if $\sigma \in L^c$, check if it is in $L$ and answer the opposite).

$L \cap L^c = \varnothing$, which is certainly decidable (just say no).

Your question is seriously confused...


approaching dynamic programing for problem

This problem is easily solved if you:

transform the input graph $G=(V,E)$ by either creating $n-1$  "levels", where each level is a copy of $G$ and edges go from one level to the next; or
consider the line graph $G'$ of $G$ instead (so that edges in $G$ become vertices in $G'$, and two vertices in $G'$ are adjacent if the corresponding edges in $G$ share an endpoint); or
For each color $c \in \{red, blue\}$, identify the maximal components $C$ of $G$ such that connectivity within $C$ is preserved using only edges of color $c$.

If you insist in using a dynamic programming algorithm, then the problem can be solved in $O(m)$ time using a Dijkstra-like algorithm.
Let's start with some definitions:
Given a color $c \in \{red, blue\}$, define a $c$-ending path as a simple path $P$ such that either 1) $P$ is empty, or 2) $P$ ends with an edge of color $c$.
Given a path $P$, let $\ell(P)$ be the number of color changes encountered when traversing $P$.
We will say a path $P$ from $s$ to $v$ is a shortest $c$-ending path if there exist no other $c$-ending path $P'$ such that $\ell(P') < \ell(P)$.
We will call $\eta(v,c)$ the value of $\ell(P)$, where $P$ is a shortest $c$-ending path from $s$ to $v$.
According to the above definitions $\eta(s, red) = \eta(s, blue) = 0$.
Moreover, the following suboptimality property holds:
Claim: Let $P$ be any shortest $c$-ending path from $s$ to $v$, let $u \in P$.
The subpath $P[s:u]$ of $P$ going from $s$ to $u$ is a shortest $c'$-ending path where $c'$ is the color of the incoming edge in $u$ (if $u=s$ then $c'$ is any color).
Proof:
Assume that $u \neq v$, otherwise the claim is trivial.
Let $c''$ be the color of the edge leaving $u$ in $P$.
Suppose towards a contradiction that $P[s:u]$ is not a shortest $c'$-ending path.
Let $P'$ be a shortest $c'$-ending path from $s$ to $u$, and notice that $Q = P' \circ P[u:v]$ is a (not necessarily simple) path from $s$ to $v$.
$Q$ ends with an edge of color $c$ and we have:
$$
\ell(P) = \ell(P[s:u]) + 1_{c' \neq c''} + \ell(P[u:v])
> \ell(P') + 1_{c' \neq c''} + \ell(P[u:v])
= \ell(Q),
$$
contradicting the fact that $P$ is a shortest $c$-ending path. $\square$
For each node $v$ we will maintain two upper bound $\tilde{\eta}(v, red)$ and $\tilde{\eta}(v, blue)$ on $\eta(v, red)$ and $\eta(v, blue)$, respectively. Initially $\tilde{\eta}(s, red)=\tilde{\eta}(s, blue)=\eta(s, red) = \eta(s, blue) = 0$ while, for $v \neq s$, $\tilde{\eta}(s, red)=\tilde{\eta}(s, blue) = +\infty$.
Finally, we will maintain a priority queue $Q$ in which keys are pairs $(v,c)$ where $v$ is an unmarked vertex and $c$ is a color, and the corresponding priority will be $\tilde{\eta}(v, c)$. Initially all pairs $(v,c)$ are in the queue.
The algorithm proceeds as follows: while $Q$ is not empty, extract $(u,c)$ from $Q$; for each edge $e=(u,v) \in E$ let $c'$ be the color of $e$ and set $\tilde{\eta}(v, c) = \min\{\tilde{\eta}(v, c), \tilde{\eta}(u, c) + 1_{c \neq c'} \}$ (thus possibly updating the priority of $(v,c)$, if such a pair is in $Q$).
It is clear by construction that all values $\tilde{\eta}(v, c)$ are upper bounds to $\eta(v,c)$ as claimed. We now prove that, when the pair $(v,c)$ is extracted from $Q$, $\tilde{\eta}(v, c)$ is also a lower bound to $\eta(v,c)$, thus proving that $\tilde{\eta}(v, c) = \eta(v,c)$.
Claim: When $i$-th pair $(v_i,c_i)$ is extracted from $Q$, $\tilde{\eta}(v, c) \le \eta(v,c)$.
Proof:
Let $i$ be the smallest value such that, when $(v_i, c_i)$ is extracted from $Q$ we have $\tilde{\eta}(v_i, c_i) > \eta(v_i,c_i)$.
Since the values $\tilde{\eta}(v_i, c_i)$ never decrease during the execution of the algorithm and cannot become negative we know that $v_i \neq s$.
Let $P$ be a shortest $c_i$-ending path from $s$ to $v_i$ and consider the last vertex $x$ such that the incoming edge in $x$ in $P$ has color $c_x$ (if $x=s$ let $c_x$ be any color) and $x=v_j$ and $c_x=c_j$ for some $j<i$ (notice such a vertex always exists since the above conditions are satisfied for $x=s$).
Let $y$ be the vertex following $x$ in $P$ and $c_y$ be the color of the incoming edge.
Since $(v_i, c_i)$ was extracted instead of $(y, c_y)$ we must have:
$$
\tilde\eta(v_i, c_i) \le \tilde\eta(y, c_y)
$$
Moreover, since $(x, c_x)$ was already extracted from $q$ we have:
$$
\tilde\eta(y, c_y) \le \tilde\eta(x, c_x) + 1_{c_x \neq x_y} = \eta(x, c_x) + 1_{c_x \neq x_y}
$$
And, by suboptimality:
$$
\eta(x, c_x) + 1_{c_x \neq x_y} =
\eta(y, c_y) \le \eta(v_i,c_i),
$$
which is a contradiction $\square$.
The sought quantity is then $\min\{\tilde\eta(t,red), \tilde\eta(t,blue) \}$.
Finally, notice that the the priority can only decrease in $Q$, that the priority of the extracted pairs is monotonically increasing, and that the only possible values of the priorities are $\{0, 1, \dots, n\} \cup \{ +\infty \}$. Therefore it is possible to implement a priority $Q$ that requires $O(n+m) = O(m)$ time to perform all the required $O(n)$ insertions and $O(m)$ priority updates.


Matching a set of paths to an incrementally generated graph

I'll outline a solution to your problem.  There are two key insights: (1) each path can be analyzed independently of all the others; (2) the best match can be computed using dynamic programming.  I'll start with a simpler version of your problem and build up to a solution for the full problem.

Finding the best match for a single path

Suppose we have a single path (from graph A) and we want to find its best match in graph B.  This can be solved with dynamic programming.

Let $P$ denote the path from graph A, and $P_k$ denote the prefix of the graph containing its first $k$ edges.  If $v$ is a vertex in $B$ and $k$ is a natural number, define $f(k,v)$ to be the number of edges present in the optimal match of $P_k$ inside graph B, such that the match ends at vertex $v$.  Then $f(k,v)$ follow the following recursive relation:

$$f(k+1,w) = \max(\max \{f(j,v) : v \to^* w,j \le k \}, 1 + \max \{ f(j,v) : v \to^* v' \to w, j \le k\})$$

where the former max is taken over all $v$ such that $w$ is reachable from $v$ in B, and latter max is taken over all $v,v'$ such that $v'$ is reachable from $v$ in B and there is an edge from $v'$ to $w$ in B whose label is the same as the label on the $k$th edge of $P$.  Also, we have the base case $f(0,v) = 0$ for all $v$.  Finally, notice that the number of edges matched in the optimal match for $P$ is given by $\max\{f(k,v) : v \in V\}$.

This recursive relation immediately gives us a dynamic programming algorithm to compute the number of edges matched in the optimal match for $P$.  You can also augment the algorithm to retrieve the match itself, if desired.

The running time is polynomial.  Suppose the path has length $\ell$ and graph B has $n$ vertices and $m$ edges.  Then there are $O(\ell n)$ subproblems, and each subproblem takes $O(m \el)$ time to solve (on average), so the running time is $O(nm \ell^2)$.  [It might be possible to further improve the running time by decomposing B into strongly connected components and only computing $f(k,v)$ values for one vertex $v$ in each strongly connected component, but I haven't tried to optimize this algorithm.]

Note that this gives the exact optimum, not an approximation.  It's not a heuristic -- it always gives the optimal solution.

If you don't find the dynamic programming algorithm intuitive, here is another perspective.  You can think of this from an automata theory perspective.  Suppose the path has edge labels $e_1,\dots,e_{\ell}$.  Let $M$ be the automaton that accepts every subsequence of regexp $\Sigma^* e_1 \Sigma^* e_2 \Sigma^* \cdots \Sigma^* e_{\ell} \Sigma^*$ (this is a regular language, so it has a NFA, call it $M$).  Form the parallel composition of $M$ and B, using the product construction; call it $M'$.  Now look for the longest path in $M'$.  This is exactly the optimal match you are looking for.

Finding the best match for a collection of paths

Now suppose we have multiple paths and want to match them all to B.  Well, it turns out that the optimal way to match a collection of paths is to consider each path separately, finding the optimal match for that path in isolation (independent of all the other pairs), and then combine these matches.

So if we have $q$ paths, we can just invoke the algorithm above $q$ times, once for each path.  The running time will be $O(nm \ell^2 q)$.

Dealing with changes to B

In your problem, each time you find the best matches for a collection of paths, you then update B to get a new graph.  This can be easily handled by simply running the algorithm from scratch again on the new graph.  In each round, you run the $O(nm \ell^2 q)$-time algorithm from above on the current graph B.  Then, you use whatever technique you have in mind for growing the graph B, and start over again.  This doesn't let you re-use work from previous rounds, but it's a very simple technique, and it computes the optimal solution.


What does 'computable in the limit from above' mean?

To quote Wikipedia/Scholarpedia,

  A partial function $f$ from the rational numbers to the real numbers is
  upper semicomputable if it is defined by a rational-valued partial
  computable function $\phi(x,k)$ with $x$ a rational number and $k$ a
  nonnegative integer such that $\phi(x,k+1)≤ϕ(x,k)$ for every $k$ and
  $\lim_{k \to \infty}\phi(x,k)=f(x)$. This means that $f$ can be computably approximated
  from above.

Further, using the squeeze theorem, we could conclude:

  If a function $f$ is both upper semicomputable and lower semicomputable
  on its domain, then we call $f$ computable


Big O notation comparison with constant time

In fact, $1/n = O(1)$. Recall the (simplified) definition of big O: for positive functions $f,g$, $f(n) = O(g(n))$ if there exists a constant $C > 0$ such that $f(n) \leq Cg(n)$ for all $n$. In your case, the constant $C = 1$ would do since $1/n \leq 1$ for all $n$.

The fact that $f(n) = O(g(n))$ just means that $g(n)$ is an upper bound on $f(n)$, i.e., that $g(n)$ grows at least as fast as $f(n)$. The two functions need not have the same order of growth.


How do bridges divide a larger network into smaller broadcast domains?

After quite a bit of research through YouTube and whatnot, I finally managed to find the answer.

A bridge (or a switch, both being data-link layer devices) DOES NOT divide the broadcast domains of the VLAN (the virtual LAN is formed by connecting the different physical segments using the bridge/switch).

A broadcast is sent with a special MAC address FF:FF:FF:FF:FF:FF (48 bits of 1s), of which the bridge/switch has no entry in its bridge table (and for that matter, will never have). The essential point to be noted here is that a bridge/switch follows a learning approach, in which until it is absolutely sure on which of it's port (or interface) a MAC address lies, it just forwards the frame to all the ports (except the one from which the frame has arrived). Hence, the bridge/switch, having no details of the destination MAC address of the broadcast frame, will go on to forwarding the frame to all of its ports (except one, the one from which it arrived).

What this means is that a bridge/switch cannot break the broadcast domain of the VLAN it is forming.

More related information:

https://youtu.be/reXS_e3fTAk?t=335


Finding the area of a rectangle in python

To calculate the area of a rectangle on a coordinate system, you need the length between x1 and x2, and the length between y1 and y2.
x1 = int(input())
y1 = int(input())
x2 = int(input())
y2 = int(input())

xDiff = abs(x1 - x2) # Using absolute value to ignore negatives
yDiff = abs(y1 - y2)

area = xDiff * yDiff

Edit: Forgot to mention, if x2 is always greater than x1, and y2 is always greater than y1, instead you can just use xDiff = x2 - x1 and yDiff = y2 - y1


String Search - how to find the "most" accurate string?

One way to do so is as follows:

Sort the company names from longest to shortest.
For each company name $c$:

a. Find all the substrings of the input string that equal $c$ and don't use any characters from a previous occurrence of a company name.

b. If some substring exists, add $c$ to the solution.

This strategy works if you're trying to solve the problem you've stated. But if you want a more robust solution, you should look into using natural language processing tools like Python's NLTK. These tools allow you to take syntax and context into account, and might help you tell the difference between "I ate a big apple", and "I bought shares in Big Apple".


Here is a paraphrase of the proof in the cstheory answer. We reduce from the halting problem. Suppose that we are given a machine $M$, and we are to decide whether $M$ halts on the empty input. We construct a new machine $M'$ accepting a single input $x$, which operates as follows:

Let $n = |x|$.
$M'$ runs $M$ for $n$ steps.
If $M$ halted within $n$ steps then $M'$ runs a dummy loop taking exponential time $\Omega(2^n)$. Otherwise, $M'$ just halts.

Since Turing machines can be simulated with only polynomial overhead, if $M$ doesn't halt then $M'$ runs in polynomial time. If $M$ halts, then $M'$ takes exponential time. Hence $M$ halts iff $M'$ is not polynomial time.

More generally, this shows that even if we know that $M$ runs in time at most $f(n)$ for some superpolynomial time-constructible $f$, then we cannot decide whether $M$ runs in polynomial time.


Why do heuristic functions only approximate the real value of the cost?

If you create a heuristic that returns the exact cost for each node in the search tree, you can find the optimal solution easily: Start at the initial state and generate all successor states. Take the state with the best heuristic value and repeat, until you find the goal state. Because the estimated cost (from the heuristic) for each node in the search tree is equal to the actual cost, you never make a wrong decision.

Unfortunately for most problems constructing such a heuristic would mean that for each node to evaluate you calculate the solution and then return the cost of the solution. Thus you already solve your problem inside the heuristic function.


How to write an EBNF grammar for Java float literals?

You could try answer the question "How do I define double and float literals?"

doubles are usually defined as:

double a = 12d;
//or
double b = 12.1;
//or
double c = 12.1d;
//or
double d = 12;

while floats could be defined as:

float m = 10;
//or
float n = 10.4f;
//but this is invalid:
float p = 10.4;

Note that by default a literal like 10.123 is considered to be double, so if you really want to assign it to a float variable, you need to append a f
character in the end. However, f is optional when the literal is 10.

Let's also list the properties of both types:

float: 32 bits (4 bytes) where 23 bits are used for the mantissa (up to 9 decimal digits). 8 bits are used for the exponent, so a float can move the decimal point to the right or to the left using those 8 bits. There is 1 bit used as the sign bit. The max long value that double can hold is $10_18$

double: 64 bits (8 bytes) where 52 bits are used for the mantissa (up to 19 decimal digits). 11 bits are used for the exponent and 1 bit is the sign bit.

So, double and float could be defined like:

digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";

double = 19 * digit, [ [, | .]  18 * digit]["d" | "D"];
float = 19 * digit, [ [, | .]  18 * digit, "f" | "F"];


If you accept a proof that TSP without triangular equation is NP-complete then it is easy: If you take an instance of "TSP without triangular equation", then you just add a large enough constant to each edge to get the triangular equation, solve it as an instance of "TSP with triangular equation", and that solves your original problem.


Finding the maximum of a bitonic sequence

The first thing that comes to my mind after reading your question is as follow. Draw the sequence as a graph given below. Each $B[i]$ you can think of a point in the graph given below.

The idea to do binary search should be clear from the question as input sequence is almost sorted. Now if you guess the peak point then you are in a good position, but during the binary search if you choose a number which will give you two cases.

The above two cases are the cases in which you need to think, but if you have tried few problems on binary search then now the problem will be easy to solve. More formally you can see the yuval's answer. You ask for the thought process, I have tried to give you my thought process. For any two persons thought process is different, there may be many other way to visualise the problem you have described.


How to prove that this language is not recursive enumerable?

You can directly use the extension of Rice's theorem to prove that $L\notin RE$


Proof of NP-completeness of a special case of longest-path problem

We can prove that requiring the graph $G$ to be connected does not decrease the hardness of our problem here.

Reduce from Hamiltonian path between $2$ specified vertices, namely $s,t\in V(G)$

Like before, we want to add new vertices to the graph while keeping it connected.

Now, do some arithmetics:

A Hamiltonian path between $s$ and $t$ is of length $n-1$, where $n=|V|$

If we attach some paths of length (at most) $k$ to $s$ and $t$, then we can increase the length of a path up to $n-1+2k$.

We should have $4(n-1+2k)=|\mathcal{V}|$ in the new graph $\mathcal{G(V,E)}$.

So $|\mathcal{V}|-|V|=3n-4+8k$. Take $k=\sqrt{n}$. Alternatively, attach $s$ and then $t$ and again $s$, etc. to a new short path of length (at most) $k$ (i.e. $k$ new vertices).

The point of setting $k=\sqrt{n}$ is to prevent one from concatenating $2$ short paths attached to the same vertex (either $s$ or $t$). So, one must take one path attached to each vertex among $s$ and $t$. And the middle part of the path is a Hamiltonian path between $s$ and $t$.


Interpretation of this regular expression: (1*0*)*

For any two words $w_1$ and $w_2$, the regular expression $\texttt{((}w_1\texttt{)*(}w_2\texttt{)*)*}$ is equivalent to $\texttt{(}w_1\texttt{|}w_2\texttt{)*}$. Hence, both your examples are elements of the language generated by $\texttt{(1*0*)*}$.

In this setting, it is impossible to specify $w_1$ and $w_2$ occur equally often with a regular expression (except for a finite number of possibilities). Otherwise, you would be able to generate a non-regular language, in this case $\{ 1^n 0^n \mid n \in \mathbb{N} \}^\ast$.


Why does the map function in MapReduce take two parameters?

Let me quote the documentation (emphasis mine):

  Map You write a map function that runs once for each input value. It returns a collection of name-value pairs which are passed on to the next stage. If there are many, many input values, then this function runs many, many times. The framework divides up the input so that subsets are handled in parallel on multiple instances of your application. A typical map function could count things that occur in each input value that matches some filter.

So there are two immediate uses I can imagine:

Use the "chunk" name in the returned names. For example, you might want to distinguish bible_author from fiftyshadesofgrey_author in the result.
Identify "subprocesses". If anything goes wrong (and something will go wrong) an error message like "Error processing bible: Illegal character at position 666" is obviously only useful if you include the document name.

And, of course, you may also want to use the name in the actual computation. A general API should cover that case.


Why is backpatching needed during intermediate code generation?

Suppose you encounter a jump instruction "goto L1" before encountering the label L1 itself. The solution you propose (as far as I understand) is to reserve a location M1 in memory at which L1 will be stored, and to translate "goto L1" into an instruction of the form "jump to the address stored at address M1". Later on, upon reaching L1, you update location M1 with the address of L1.

This is a form of "runtime backpatching", in which the processor itself is doing the backpatching when running the code. Accessing memory tends to be slow, and so it is much better to hardcode addresses, shifting the effort from runtime to compile time. This is where backpatching comes in. When encountering "goto L1", the compiler will note that the address is missing, and will fill it in later, when the address of L1 is known.


What would be a natural generalization of a byte parity check?

For $i \in \{0,\ldots,M-1\}$, add a new byte which is the sum (or XOR) of every byte whose index equals $i$ mod $M$. For example, if $M=2$, one byte is the sum of all the bytes in the even positions, and the other one is the sum of all the bytes in the odd positions. Since bursts have length at most $M$, each of these checksums will only be missing a single byte.


How are the number of bytes less than the number of pixels in an image?

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


You solve the following more general problem: find the least number $N$ with sum of digits $T$ such that $N \mod M = R$ (the inputs are $M,T,R$). Initially, $T=M=S$ and $R=0$. Now you go over all possible least significant digits $b$. Using the formula
$$
(10n+b) \pmod{M} = 10(n \pmod{M}) + (b \pmod{M}),
$$
you reduce the problem to a smaller one, and so on.

The total amount of work appears to be $O(S^2)$, since the number of possible values for $T$ and $R$ is $O(S^2)$. Care needs to be taken with zero digits, however, a detail which I leave you to ponder.


I am not sure I understand the question.

When designing a CPU, you decide how many pipeline stages it will have and accordingly how much work is done at each stage.

Often, all the parts of the CPU work at the same frequency (well, this is not really true, but...), so the most complex part will be what limits the frequency that the CPU will be able to achieve.

Some CPUs are optimised for high frequency and have many pipeline levels (ex : Intel Pentium IV, AMD Steamroller). Good for number crunchers.

Some CPUs are optimised for lower frequencies but cram more work for each pipeline level (ex. : Intel Core, Apple A8...). This option is often more power efficient.

Deeply pipelined CPUs waste more cycles than narrow ones when the pipeline must be emptied : mispredicted branch, interrupt... The number of cycles wasted is higher, but as the frequency should also be higher, the delay for each cycle should be a bit shorter than for a short-pipelined CPU.

[Maybe you should give more context to your question. This answer was probably not what you were looking for ;-)]


Size of constant depth circuit for digital comparator?

Comparison can be implemented by subtracting twos-complement numbers and then testing whether the most significant bit is 0 or 1.  Subtraction can be implemented as addition ($x-y = x + \overline{y} + 1$, where $\overline{y}$ is obtained by flipping all bits of $y$).  Addition can be implemented using carry-lookahead methods.

If you put all this together, I think you get a comparison circuit that uses $O(n)$ gates and has constant depth.

In particular, let $g_i = a_i \land b_i$ ("generate"), $p_i = a_i \lor b_i$ ("propagate"), $q_i = p_{i+1} \lor \cdots \lor p_{n-1}$, $t_i = g_i \land q_i$, and $c_{n-1} = t_0 \lor \cdots \lor t_{n-2}$ ("carry").  This lets you compute the carry into the most significant bit in constant-depth and $O(n)$ gates.  That's all you need for the results of the comparison (you don't need to compute the value of the other bits of the sum).  The reason this requires fewer gates than a full addition or full subtraction is that we only need the carry into the most significant bit, not all the carry bits.

Double-check my reasoning -- I could have gone awry somewhere.


Here is one interpretation of this question. We want to count rooted trees with ordered children in which each internal node has either 2 or 3 children.

Denote by $T_d$ the number of 2-3 trees of depth at most $d$, so $T_0 = 1$ (the tree consisting of a single node) and $T_1 = 3$ (the tree consisting of a a single node; a root with two children; a root with three children). More generally, a 2-3 tree of depth at most $d$ is either just a single node or consists of a root with two or three children, each of which is a 2-3 tree of depth at most $d-1$. Therefore $T_d = 1 + T_{d-1}^2 + T_{d-1}^3$.

Finally, the number of 2-3 trees of depth exactly $d$ is $T_d - T_{d-1}$. For example, the number of 2-3 trees of depth exactly 1 is $T_1 - T_0 = 3-1 = 2$.


What can we conclude about a machine $m$ from that fact that it solves a particular problem $P$?

The computational power of machines / automata / programming languages and similar computational models, is usually studied in these theoretical fields:

Computability (for what can be computed at all)
Complexity (for what can be computed efficiently)
Formal languages (several kinds of automata exist, with different expressiveness)

You will find many textbooks about these topics, as well as university courses (some video lectures could even be available on the 'net)


Mathematical optimization with thresholded optimization function

I guess $f_2(x)$ is some sort of oracle that tells you if $\Phi_2(x)$ is greater than $t$?  If the set $\{\mathbf{x} : \Phi_2(x) \le t\}$ is convex, then I think projected gradient algorithm might be helpful. Could you provide more information on $\Phi_2(x)$? The question is kinda confusing with the information provided.


Drawbacks of repeating a single pattern matching procedure for many patterns

One common way of solving pattern matching problems is compiling a DFA that matches the pattern. If you have several patterns in mind, you can combine all of them into a single DFA, which will match all of them with a single pass, rather than one pass per pattern. On the flip side, the DFA could have many states and so might not fit into cache, which would cause a performance hit.


Minimum no. of coin flips (switch) needed so that all coins face the same side (Heads or Tails)

Here is a general algorithm. The maximum number of flips needed is $2^{n-1}-1$.

Input: coin 0, coin 1, coin 2, ..., coin $n-1$

Procedure:
$\quad$  If all coins face the same side, return.

$\quad$  For $i$ from 1 to $2^{n-1}-1$ inclusive:
$\quad\quad$  If $i$ is divisible by $2^k$ but not $2^{k+1}$:
$\quad\quad\quad$  Flip coin $k$
$\quad\quad\quad$  If all coins face the same side, return.

For example, if there are no more than 8 coins, then just flip the coins at the following places successively as long as all faces do not face the same side.

0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0


Doubt on Performance Comparison of Splay Trees

There has been various real world applications that use splay tree. One of the most prominent example is the gcc compiler that applies splay tree. There are many other examples. In fact, ACM Kanellakis Theory and Practice Award 1999 was given to Daniel Sleator and Robert Tarjan for their seminal work on the splay tree data structure.

It looks like you have some misconception on the splay tree about its worst performance.

Take the example you have mentioned, where we access a splay tree of $n$ nodes that labelled from $1$ to $n$ according to their level in the tree, starting from $n$ down to $1$. Your intuition indicates "this case would be significantly slower than an AVL tree." Indeed, the height of the tree before and after those search operations is $n-1$. That is, the tree is the most unbalanced tree before and after that search operations.

However, contrary to your intuition, it turns out that case is a showcase of the stellar performance of a splay tree. Although an $O(n)$-time operation is needed to access the first few nodes, the average cost for all search operations is smaller than a constant that is not dependent on $n$ (assuming the usual RAM arithmetic computation model)! In fact, we have the sequential access theorem for splay tree, which says that if you look up all $n$ elements in a splay tree in ascending or descending order, the amortized cost of each lookup is $O(1)$. You cannot achieve such amazing performance with any kind of search tree that keeps intact during a search, including an AVL tree. To experience that phenomenon, you can go to splay tree visualization. Enter $32$. Hit "insert". Enter $31$. Hit "insert". And so on until you have inserted $1$. Then find $32, 31, \cdots, 1$. Observe what is happening.

Once you have that experience, it is not hard to understand that extraordinary phenomenon. After initial about $\log_2(n)$ search operations, the tree becomes almost completely balanced, that is, its height is about $\log_2(n)$. Since that point of time on, accessing each next node will take at most $\log_2(n)$ time. Furthermore, whenever a node that is somewhat far from the root is accessed, the nodes along its path to the root are brought up significantly closer to the root. In the end, the vast majority of the nodes will be found within some constant time.


Is the union of infinitely many regular languages always regular?

Every language is a union of infinitely many regular languages:
$$
L = \bigcup_{w \in L} \{w\}.
$$


Perceptron and non linearly seprable data

A single-layer perceptron can only learn linearly separable patterns (with 100% accuracy), as noted in the Wikipedia article on perceptrons.  (Advice for the future: check standard references before asking here.)
A multilayer feedforward neural network (sometimes called multilayer perceptron) can learn other patterns.
If someone just says "perceptron", in my eyes it is at least a little ambiguous whether that means a single-layer perceptron or possibly could encompass multi-layer networks.


What is the "spatial information" in convolutional neural network

Spatial Information refers to information having location-based relation with other information.

For example,
00100
01100
00100
00100

This looks like the number "1".

If this was represented in a single line,
001100011100001100001100

It wouldn't be recognizable.

Earlier layers of CNN are convolutional layers, which take into account the image as a 2D (spatial) information. Whereas, the deeper layers flatten that (convoluted) information.


A regular expression for a given formal language

Try and build it step by step:

a language with an odd number of $a$'s: $a(aa)^*$;
between which there is an even number of $b$'s: $b^*a((bb)^*a(bb)^*a)^*b^*$;
and an arbitrary number of $x$'s: $(b+x)^*a(x^*(bx^*bx^*)^*ax^*(bx^*bx^*)^*a)^*(b+x)^*$.


How to find the square with the highest total sum

Try building a summed area table—a table where the value in each cell is the sum of all the values above and to the left, inclusive, of the cell in the original table. See if you can figure out an $O(n^2)$ solution from that.


What is the probability of comparision between smallest and greatest element in array when quick sort randomly choose the pivot element?

It is $2/N$ : the probability of picking the smallest or the biggest as pivot.
If you choose one of them, they will be compared.
If you choose any other, then the smallest and the biggest elements will be put in different partitions, and thus will not be compared.


This is a very subjective question, but generally speaking, a computer science degree is (arguably) a mix of the "mathematical" and "engineering" aspects of computer science (there are also "scientific" aspects, but they are hardly usually encountered in undergraduate studies). The shared aspects include basic mathematics such as calculus and linear algebra. "Mathematical" computer science is discrete mathematics, automata theory, computability, computational complexity, algorithms, data structures and so on. "Engineering" aspects include programming computer organization, operating systems, databases, and so on. Advanced topics such as machine learning and computer graphics are (in my view) engineering topics which are relatively mathematical, though usually require continuous mathematics rather than discrete mathematics.

If you agree to this picture, then the conclusion is that computer science is less mathematical than mathematics. Computer programmers typically need to know a very small amount of mathematics. Indeed, even an understanding of mathematical induction is probably beyond what is needed. Most of your fellow classmates will probably have modest mathematical skills, so unless you have mathophobia, I think computer science is within your means.


Is there a strictly non-deterministic one-counter language whose complement is one-counter?

In response to Shaull's comment above :

The first one is an image of 1-counter accepting $a^ib^j$ s.t. $j<i$

The secong one is an image of 1-counter accepting $a^ib^j$ s.t. $j>i,\ j<2i$

The third one is an image of 1-counter accepting $a^ib^j$ s.t. $j>2i$

Here a/-/plus means on seeing a, irrespective of the counter value, increment the counter.
b/>1?/sub means on seeing b, if counter value is greater than 1, then decrement the counter.

nop =>  no operation

$\lambda $ => empty string


Standard notation for the language of the universal Turing machine?


Algorithm to find a simple path with maximum weight less than a constant in DAG

Since there is no negative weight, you only need to keep at each node the set of path lengths no more than $K$. Because $K$ is a constant, you only keep a constant number of path lengths at each node. Hence, the algorithm remains polynomial-time.


The claim is this:

  If $L$ is a regular language and $M$ is a non-regular language, then the concatenation $LM$ of the two languages is necessarily non-regular.

If this claim is false, all you need to do is to provide one counterexample showing that it's false. If the claim is true, you need to prove that it's true for any languages $L$ and $M$, a much harder task. Fortunately, this claim is not true.

If we let $L = \emptyset$ and let $M$ be any non-regular language, then $LM = \emptyset = L$, a regular language.

Now, if that feels too much like cheating, we can find other examples. Consider this:

$L = \Sigma^*$
$M = \{ww^R \mid w \in \Sigma^*\}$

$L$ is regular, $M$ is non-regular (in fact, it's the language of palindromes, a canonical context-free language). Since the empty word is in $M$, we have $LM = \Sigma^* = L$, so the concatenation is regular.


Need help removing ambiguity from grammar

In your attempt put $T\rightarrow UV \ \bracevert\  V\  \bracevert\  [E]$ instead of $T\rightarrow E$.

The idea is not to just replace symbols arbitrarily, but replace in such a way that it's derivations are a subset of possible derivations (which should be unambiguous).

And you can also use the procedure prescribed in textbooks or in Jonathan's answer in https://stackoverflow.com/questions/3106195/converting-ambiguous-grammar-to-unambiguous to remove ambiguity (unless the language in inherently ambiguous). I like Jonathan Leffler's answers because he gives lot of detail as well as intuition behind answers.


Convert a digraph to the corresponding undirected graph in linear time using adjacency lists

If you perform the check at the end rather than throughout, it will be much faster.

Start by going over all edges, and for each edge $(i,j)$ add the edge $(j,i)$ to the adjacency list of $j$.

Now given the adjacency list of $i$, we want to remove duplicates. For that we use an array indexed by $V$, which is initialized to zero (we only need to initialize it once). Go over the list and count how many times you see each edge. Now go over the list a second time and only add the first occurrence of every edge. Finally, go over the list a third time to reset the array back to zero. In all, we do $O(1)$ work per edge.

One drawback of this algorithm is that the resulting adjacency lists aren't sorted, even if you started out with sorted ones. Here is a different algorithm which works in $O(|V|+|E|)$ time and maintains this invariant (assuming it holds originally). For each vertex $i$, compute the sorted lists $\{ j : (i,j) \in G \}$ and $\{ j : (j,i) \in G \}$. Then merge them and remove duplicates.


Correctness proof for greedy algorithm based on ratio

The strategy to prove your ratio greedy algorithm is what I called "unimprovable solution by exchange of elements".

Instead of proving that an algorithm produces the optimal solution, this strategy require you to show that every optimal solution that cannot be improved by an exchange of two or more elements must be or must be equivalent to the solution produced by that algorithm.

Firstly, there must be at least one optimal solution in this scheduling problem. You may want to take a moment to verify that this is indeed true.

Now suppose $OPT$ is an optimal solution. Let us analyze two adjacent jobs in $OPT$. Note that we can switch these two adjacent jobs without changing the contribution of other jobs to the weighted sum of completion times, since the switch does not change the completion times of other jobs. How should these two jobs be arranged so that the total contribution of these two jobs to the weight sum of completion times might be smaller? Now it is time to show the power of arithmetic using unknowns. You will be able to conclude that, the job whose weight/length ratio is bigger must be scheduled earlier than the other job. Assuming the ratio weight/length of each job is distinct, you can then deduce that $OPT$ must schedule all jobs by the descending order of their weight/length ratio; otherwise you will find two adjacent jobs in ascending order of their weight/length ratio. Well, the only scheduling that schedules all jobs by the descending order of their weight/length ratio is produced by your greedy algorithm!

I will let you fill the detail of a complete rigorous proof, which should mention why there should no idle time between two adjacent jobs and which should deal with the case when there are jobs of the same weight/length ratio.


First define a type family $P : \mathtt{Nat} \to \mathtt{Type}$ such that
$P\,0 \equiv \top$
and
$P\,1 \equiv \bot.$
For instance, we could define it by induction as
\begin{align}
P\, 0 &\equiv \bot \\
P\, (\mathtt{succ}(n)) &\equiv \top.
\end{align}
Let $\mathtt{tt}$ be the inhabitant of $\top$.

Suppose $e : 0 = 1$. Then, using $J$ we can formulate the transport map $\mathtt{transport}^P_e : P\,0 \to P\,1$, and use that to transport $\mathtt{tt} : P \, 0$ to
$$\mathtt{transport}^P_e(\mathtt{tt}) : P \, 1.$$
We are done because $P\,1 \equiv \bot$.


Why we use context-free grammar for parsing?

Because regular expressions are too weak and context-sensitive languages are too difficult to parse. More specifically, regular expressions can't specify that the brackets in your program match up; determining whether a string matches a context-sensitive language is PSPACE-complete (so probably takes exponential time).


This is simply a way to generate 32-bit hash for the string.
Assuming that MD5 is a good cryptographic hash function, it doesn't matter which bits you take from the hash and in which order you arrange them (as long as they are different bits). The behavior of the bits should be equally unpredictable.

There's no explanation, why exactly 32 bits are required, though my guess is that it enables the use of simple integer types in the code.


Is the Rice's theorem applicable to $\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}$?

Well, Rice's theorem doesn't apply but we don't need it—$L^*$ is empty and therefore decidable.

To figure this out, we just need to be meticulous about what these languages are.

$L^*$ is the set of all Turing machines that recognize the totality problem. It is the set of all Turing machines that can take in a Turing machine $\langle N\rangle$ and accept just if $N$ halts on all inputs.
$L^\prime$ is the set of all Turing machines that halt on all inputs.
They're different languages: $L^*$ is the set of all machines whose language is $L^\prime$.

The totality (all-halt) problem is unrecognizable: there is no Turing machine that takes in a TM $\langle N\rangle$ and accepts just if $N$ halts on all inputs. (Consider a reduction to the halting problem.) Therefore, $L^*$ is empty and $L^\prime$ is unrecognizable.

$L^*$ is empty, therefore decideable (when given a machine $\langle N\rangle$ and asked if it recognizes the totality problem, always say no.) $L^\prime$ is unrecognizable, which is stronger than merely undecidable.

But, if we didn't already know that $L^\prime$ was unrecognizable, we could use Rice's theorem to show that $L^\prime$ is undecidable. There's a string in $L^\prime$, for example the Turing machine that ignores its input and always accepts. There's a string not in $L^\prime$, for example the Turing machine that ignores its input and loops forever.

Also, a side note: Rice's theorem says that non-trivial language properties of TMs are undecideable. As you point out, there are two trivial languages which the theorem doesn't cover: the empty language $\varnothing$ and the language of all strings $\Sigma^*$. Note that we don't need Rice's theorem for these languages to determine decidability— we already know they're decideable. In fact, they're regular: there's a DFA that accepts all strings, and a DFA that accepts no strings.


How to solve a knapsack problem with increased weight limit?

That guess is obviously wrong. If all items have weight 666 and value 1, then you can fit 3 items into a bin of size 2000, and only one into a bin of size 1000.

If all weights are W < $w_i$ ≤ 2W, then O = 0 and O' = highest value of a single item.

There is very little that you can say except the obvious O ≤ O'. You might have "valuable" items with a total weight ≤ W, and all other items are worthless. Then O' is not or only very little greater than O. Or all items with weight ≤ W might be worthless with some items with weight W < $w_i$ ≤ 2W very valuable, then the ratio O' / O can be arbitrarily large.


Is the Complement of the Language $L=\{wxw^r|w \in (a+b)^+, x \in (a+b) \}$ Context free?

Generally speaking, the way to figure out whether a given language is context-free is twofold:

Try proving that it is not context-free, say using the pumping lemma.
Try proving that it is context-free, say by constructing a grammar or a PDA.

If any of these methods succeed, you will have found whether the language is context-free.

In your particular case, we can notice that a word $y$ is not in $L$ if one of the following three cases occurs:

$y$ has even length.
$y$ has length one.
$y$ has odd length, and when written as $y = z \sigma w^R$, with $|z| = |w|$, the two words are different.

In the third case, let us suppose that $z_i = \alpha \neq \beta = (w^R)_i$, and put $\ell = |z| = |w|$. Then $y \in \Sigma^{i-1} \alpha \Sigma^{\ell-i} \sigma \Sigma^{\ell-i} \beta \sigma^{i-1}$, and all such words are not in $L$. We conclude that
$$
\overline{L} = (\Sigma\Sigma)^* \cup \Sigma \cup \bigcup_{\substack \sigma, \alpha \neq \beta \in \Sigma \\ j,k \geq 0} \Sigma^j \alpha \Sigma^k \sigma \Sigma^k \beta \Sigma^j.
$$
It is routine to construct a context-free grammar for the expression on the right, and so $\overline{L}$ is context-free.


Check if a binary tree is a perfect tree

Assuming you are given the root and nothing else, this problem has a lower bound of $\Omega(n)$.

An informal proof:

Consider an adversary who creates a perfect tree of height $h$ and size $n$. Now this adversary also has one extra node whose parent has yet to be determined.

The adversary, being sneaky, doesn't determine the parent of this node until you've checked every other node in the tree. To be more precise, the parent of this extra node will be the very last leaf node you check.

Clearly this will take $\Omega(n)$ time for any algorithm to determine this adversary has an imperfect tree.

That being said, you could find algorithms with a better expected time. For example, you could try non-deterministic algorithms such as random walks of the tree, then compare the lengths of these random walks to give a probability of perfectness. Although in any case, you won't do better than $O(n)$.


Hint:  Imagine the formula in some (prenex) normal form and consider the order of quantifiers: $\exists x_1 \forall x_2 \exists x_3 \exists x_4 \dots Q x_t \phi(\overline{x})$.  Let the player corresponding to the first quantifier choose its valuation (true or false) and then continue the game with that variable $x \mapsto v$ where $v$ is the value chosen for $x$, and with the first quantifier removed from the formula, i.e., in the example, if $\exists$ chooses true, let $x_1 \mapsto \mathtt{true}$ and continue the game on $\forall x_2 \exists x_3 \exists x_4 \dots Q x_t \phi(\overline{x'})$.

Let $\exists$ be the winner (as usual) if and only if the end result is a quantifier-free true formula.


How can I use the NP complexity Venn diagram to quickly see which class of NP problem can be poly reducible to another class?

As Raphael said the definitions are important, especially if you try to create proofs. These definitions are not always captured in the Venn diagram.

The definition of NP-complete is not made clear from the diagram and will not help you to reason about

  "If A is an NP-complete problem, $B$ is reducible to $A$, then $B$ is...".

You cannot see from the diagram that this must mean that $B$ is NP.

To answer your question if it is not possible how you will be able to drill it into your head is much more complicated. But again the first step needs to be the definitions.

If you know that NP-completeness implies two properties of $A$ by definition, then you can take the next step.

  What does $B$ reducible to $A$ means when regarding these two properties. Do the properties of $A$ tell anything about $B$?

The second property says that any problem in NP reduces to $A$ in polynomial time. So if $B$ reduce to $A$ in polynomial time then $B$ is in NP.


Will MST find the shortest path for each pair $(r,v)$?

No, the MST may not find the shortest path for each pair of nodes $(r,v)$.

For example, consider a graph of three vertices $A,B,C$ with edge weight $AB\mapsto 2, AC\mapsto 2, BC\mapsto 3$. Its MST is edges AB and AC. However, the shortest path between $B$ and $C$ is the edge BC.


While I'm unaware that your suggested rule has a name and couldn't find it in any texts on my shelf, it's a consequence of reflexivity and transitivity, as you probably know already. Here's how:
$$
\begin{align}
ACDE &\rightarrow A &\text{(reflexivity)}\\
A &\rightarrow B &\text{(hypothesis)} \\
ACDE&\rightarrow B &\text{(transitivity)}
\end{align}$$


Efficient way to count number of intersections of line segments

Let's first assume there is no common boundaries between all segments.
Create the list of tuples ($pos$, $ind$) with a value ($pos$) for each boundary of every segment (thus $2n$ values) and $ind$ the index of the segment, sorted by $pos$. Sorting is achieved in $O(n \log(n)).$
Keep two counters, $open$, the number of opened segments and $close$, the number of closed segments. Both are initially at 0.
$E[i]$ will be an array of the segment $i$ state, where 0 means not opened yet, 1 otherwise.
$A[i]$ will be the $n$-element array to output, which are 0s initially.
Then loop through the list,
for tuple (pos, i),
    if E[i] == 0, then A[i] = close, open += 1, E[i] = 1
    else A[i] = open-A[i]-1, close += 1

The "-1" stands for a segment not counting himself.
This achieves $O(n)$, then still driven by the sorting $O(n \log(n))$.
Now, how to treat common boundaries ? In your exemple, I understand that segments are closed and for example [2, 7] does intersect [7, 8]. A simple way to do it (clearly not the most efficient but still $O(n)$), is to loop 3 times on the tuples at the same position:

first, you only count the opening segments in $open$
then, you only update $E[i]$ and $A[i]$ for both opening and closing segments
finally, you only count the closing segments in $close$ (that now have $E[i] = 2$)


A connected acyclic graph has $n-1$ edges

Proving 2,3 implies 1:
We have an acyclic graph $G=(V, E)$ with $n-1$ edges. We want to prove that $G$ is a connected graph.
Assume for the sake of contradiction that $G$ is not connected. This means we have $d>1$ connected components, $G=\{\bigcup_{i=1}^{d}G_i\}$.
Since $G$ is acyclic, each connected component is a tree by definition. Let $V_i$ be the set of vertices of graph $G_i$. Then, the number of edges in $G_i$ is $\mid E_i \mid = \mid V_i \mid - 1$. Thus, the total number of edges in $G$ is
$\mid\ E \mid\ =\sum_{i=1}^{d}\mid E_i \mid =\sum_{i=1}^{d} (\mid V_i \mid-1)=\sum_{i=1}^{d}(\mid V_i \mid)- d = n - d < n -1$.
The last inequality follows because $d > 1$. This is a contradiction that $\mid\ E \mid\ = n-1$.
Proving that 1,3 implies 2: We have a connected graph $G=(V, E)$ with with $n-1$ edges. We want to prove that $G$ is acyclic. I will not write the proof, but I will hint that (one of many possible proofs) you can use induction on the number of vertices. And let your assumption be that given $G$ with $n-1$ vertices and at most $n-2$ edges, then $G$ is acyclic.


Can any non-halting Turing Machines with blank tape input print out any irrational number?

I choose to represent numbers in base $\pi$. My machine prints $10$ and terminates, that's exactly $\pi$.

A Turing machine performs meaningless operations on meaningless objects, you provide the semantics, you find meaning in the computation. The answer to your question is a direct consequence of how you decide to represent numbers with the finite alphabet of the machine. It is certainly true that not all real numbers can be exactly computed under an unified semantics by Turing machines: there are uncountably many real numbers but countably many Turing machines.

But you might be able to represent some of them. For instance, with enough symbols to write integers, fractions, square roots and the imaginary unit, you can represent exactly the segments constructible with straightedge and compass, each of them in a finite amount of space.


Is the Post Correspondence Problem with more than two rows harder than the standard two-row variant?

$\text{n-PCP}$ can be reduced to $\text{2-PCP}$ as follows.
Let $M$ be a nondeterministic Turing machine that accepts an $\text{n-PCP}$ instance as input, guesses a solution for that instance, and then checks that it is correct. Clearly, $M$ accepts if and only if there is a solution to the input instance.
Now, let $p$ be an instance of $\text{n-PCP}$. The reduction encodes $M(p)$ as a $\text{2-PCP}$ instance in the standard fashion.


Proof that quicksort's running time is ∼1.39 n log n

it's claimed that the running time of QuickSort is $∼1.39\,n\log_2n$

I don't have the book handy, but it it most certainly does not claim this. That figure is the result of a close analysis of a very specific cost measure (which "time" is not); expected number of comparisons, if I remember correctly.

The proof is given in the book, if I recall correctly.

  quicksort's average case is about $2n\log_e n$.

This is basically the same figure since $1.39 \approx \frac{2}{\log_2 e}$, the difference probably being a rounding artifact.

From your comment, quoting Sedgewick/Wayne:

  In summary, you can be sure that the running time of algorithm 2.5 (quicksort) will be within a constant factor of $1.39n \lg n$ whenever it it used to sort n items.

This only states that the (expected) running time is in $\Theta(n \lg n)$; this follows from the (expected) number of comparisons being what it is, plus that comparison is a dominant operation in Quicksort.

For what it's worth, the formulation "you can be sure" without context is misleading since it seems to ignore the worst-case, and the asymptotic nature of the result.


How do we know for sure that EXPTIME ≠ P?

The time hierarchy theorem says that, for any reasonable function $f$, there are problems that can be decided in time $O(f(n))$ that cannot be decided in time, say, $O(f(n)/n)$. (There are various versions of the time hierarchy theorem. The one I've just quoted isn't standard but it's strong enough to prove what we need, here.) In particular, then, there are problems that can be solved in time $O(2^n)$ that cannot be solved in time $O(2^n/n)$ so, in particular, cannot be solved in time $O(n^k)$ for any $k$.  These problems are in EXP but not in P.
Correct: we conjecture that P$\,\neq\,$NP and NP$\,\neq\,$EXP but we don't have a proof of either of those things.


Let $T_n$ be the the column of disks $1:2:…:n$.

Let's start by the end:

$(T_n)()()$ is the final configuration. The only mean to get there is by moving the disk $n-1$ on the stack $(n)$, so the remaining $T_{n-2}$ should be on another stick. So we should get to:
$(n)(n-1)(T_{n-2})$ in $2^{n-2}$ steps: first move the $n-1$ disk then use $2^{n-2}-1$ steps with Hanoi maneuvers to move the $T_{n-2}$. This again is accessible from
$(n-2:n)(T_{n-3}:n-1)()$ in $2^{n-3}$ steps, which again is reachable from
$(n-4:n-2:n)(n-3:n-1)(T_{n-5})$ in $2^{n-5}$ steps, from
$(T_{n-6}:n-4:n-2:n)(n-5:n-3:n-1)()$ in $2^{n-6}$ steps...

At the end we get $2^{n-2}+2^{n-3}+2^{n-5}+2^{n-6}+… +2^{n-3i+1}+2^{n-3i}+…+c$.

Which is about $3(8^{n/3-1}+8^{n/3-2}+…)= \frac378^{n/3}$ modulo some constant depending on the remaining modulo $6$ of $n$. Testing in practice to determine the constant gives the exact formula for $n$ disks which happens to be surprisingly simple:

$$ \left\lfloor  \frac37 2^n \right\rfloor \enspace .$$

For $n∈\{1,2,3,4,5,6,7,8\}$ we get $\{0,1,3,6,13,27,54,109\}$ (the first five terms verified by hand) which happens to be OEIS's sequence A033129 which confirms that this is the fastest way.


Is this “cut condition" sufficient for unique minimum spanning tree?

Answer my own question: The answer is from here.

For every cut of $G$, the unique light edge crossing the cut must be part of every MST of $G$. Consider the set $T$ of edges, containing the unique light edge crossing each cut $C$ of $G$. Then, we know that $T$ is a subset of every MST.

Now we can show that $T$ must be equal to every MST.

Because there is exactly one edge of $T$ crossing every cut of $G$, the graph $(V, T)$ must have exactly one connected component: if there were two unconnected components $V_1$ and $V − V_1$, then the cut $(V_1, V − V_1)$ would not be crossed by any edge of $T$, which contradicts the definition of $T$.
In addition, $T$ cannot contain any cycles: the heaviest edge on a cycle in $T$ cannot be the unique lightest edge in any cut. Then $T$ itself must be a spanning tree of $G$. Because $T$ is a subset of all minimum spanning trees of $G$, it must be the unique MST of $G$, as any additional edge added to $T$ would form a cycle, making it no longer
be a tree.


I don't see how using the select algorithm, or indeed any algorithm, is useful here. Instead, try to use the following observation:

  Let $I = \{ i : x_i < x_p \}$ and $J = \{ j : x_j > x_p \}$. Then the derivative of your objective function with respect to $x_p$ is $$\sum_{i \in I} w_i - \sum_{j \in J} w_j. $$


What is the exact algorithm to find maximum clique of a given unit disk graph?

First note that the algorithm is expressed in the so-called proximity model (see preliminaries), so in what follows the points considered will be the centers of your circles, and $d$ will be their common diameter.

It may be confusing, as the circles drawn in the observations are not directly related to the circles from the intersection model (the radius is $d(a,b)$).

With the notations of the article, $H_{A,B}$ is finite because $V$ itself is finite ($H_{A,B}$ is a subset of the $n$ input points).

Input: d, G = (V, E) with V set of points in the plane, and E is the set
       of {u, v} s.t. d(u, v) <= d
best clique = empty
for all pair of points (u, v) from V:
    let V' = set of vertices w of V s.t. d(u, w) <= d and d(v, w) <= d
    let E' = set of {x, y} s.t. x and y are in V' and d(x, y) > d
    // G' = (V', E') is bipartite
    candidate clique = MaxIndependentSet(G')
    best clique = max(best clique, candidate clique)
return best clique

If you want to use Hopcroft-Karp, you may need to have an explicit partition $V'=A\cup B$ s.t. all edges of $E'$ are connecting a vertex of $A$ and a vertex of $B$. This can be done by checking the sign of the cross product $(\textbf{w}-\textbf{u})\times(\textbf{v}-\textbf{u})$.


Help with a dynamic programming solution to a pipe cutting problem

For me, it makes more sense to think about this problem in reverse.  The problem is posed as a destructive process - you have 1 pipe, and you split it into many.  However, in terms of the cost calculation, the reverse process results in the same answer.  That is, if you take the resulting pipe segments and start gluing them back together, using the sum of the length of the two pieces you're gluing as the cost of the operation, you end up with the same cost.

So then the question becomes the following:

given a set of pipe segments, what is the cheapest order of gluing segments together until you  have only one segment?  This assumes a cost function where c(x1,x2) = len(x1) + len(x2).

This is trivial when you have two segments.  There's only one way to glue them together, so that has to be the cheapest way.

With three segments, it starts to be a bit more interesting.

Lets say we have lengths x1, x2, and x3.  We have three options for our first operation:
x1 + x2, x2 + x3, and x1 + x3.  No matter what values are in x1, x2, and x3, the operation after this one will cost the same.  That is to say the following:

(x1 + x2) + x3 == (x2 + x3) + x1 == (x1 + x3) + x2

As a result, the cheapest way of putting the three pieces of pipe back together is going to be the way that has the cheapest first step.

Then the question becomes, which of the first steps is the cheapest?

That depends on what the values in x1, x2, and x3 are.  Lets assume the three values are in ascending order.  So x1 <= x2 <= x3.  Now you can determine which starting pair is the cheapest, right?  Its the pair containing the smallest values, or x1 and x2.  Note that there is the possibility that two or more of the three values are the same.  I'll leave it up to you to convince yourself that such a scenario is not a problem.

So we've got a solution for either 2 or 3 pieces.  This should give you some insight towards a general solution.


Transforming undirected maximum spanning tree into directed augmented network

Given an undirected tree, pick any node (it doesn't matter which one).  Call that the root.  Now do depth-first search (or breadth-first search, or any other kind of search) starting from the root, traversing only the edges of the tree.  That will visit all the vertices and edges.  When you visit an edge for the first time, it will always be in an "outward" direction, so now you know how to orient it (how to set its direction).

Work through a small example if this is still unclear.


Which memory holds the copy of the program that is to be executed?

It's the RAM.

But further, in order to enhance speed, the CACHE stores a shadow of the RAM content, so it may hold a copy of the program as well (similarly, the RAM has a copy of the program that previously was stored on the hard-drive).

Eventually, parts of the code goes into the CPU and gets stored in one of its registers (not the general purpose ones, but rather some designated registers you have no access to; just think about them as flip-flops). From that point, the program is being executed, one instruction at a time, by the CPU hardware.


DPDA - a language that contains the same number of A and B

Your language:

L = {v1w | v, w in {a, b, c}* and #a(v) = #c(w)}

The first thing to notice is that bs and cs in the first part of the string can be ignored, whereas as and bs in the second part of the string can be ignored. In the first part of the string, push onto the stack; and in the second part of the string, pop off. You know you've moved from the first part of the string to the second when you read a 1. Reject if you (a) run out of stack before you're done seeing cs in the second part of the string or (b) if you still have stuff on the stack when you're done reading the second part of the string. If you run out of input with an empty stack, accept. Something like this:

Q    s    S    |    Q'    S'
---------------+---------------
// first part of the string
---------------+---------------
q0   a    Z/a  |    q0    aZ/aa
q0   b    Z/a  |    q0    Z/a
q0   c    Z/a  |    q0    Z/a
---------------+---------------
// transition to 2nd part
---------------+---------------
q0   1    Z/a  |    q1    Z/a
---------------+---------------
// second part of the string
---------------+---------------
q1   a    Z/a  |    q1    Z/a
q1   b    Z/a  |    q1    Z/a
q1   c    a    |    q1    -

We can define acceptance to be by empty stack in state q1. If you want a separate accepting state you can add a new one and an empty transition for that purpose, although that results in a non-deterministic PDA. We can get a DPDA with a separate accepting state if we really want to as follows:

read bs and cs in a loop on the initial state (accepting).
if you read an a, go to state A. In state A, read bs and cs in a loop, and if you read as, push as onto the stack.
from the initial, upon seeing 1, go to state E, which is accepting, and loop on bs and cs. Crash on an a, or transition to a dead state.
from A, upon seeing 1, go to state C read as and bs in a loop, and if you read c with an a on the stack, pop the a. If you read a c with Z on top of the stack, transition to B.
state B loops to itself on a and b and crashes, or transitions to a dead state, on c.


Function application is not associative. It may seem at first that this is valid because function composition is associative, but according to Wikipedia,

  Bracketing may be used and may be needed to disambiguate terms. For example, ${\lambda x.((\lambda x.x)x)}$ and ${(\lambda x.(\lambda x.x))x}$ denote different terms (although they coincidentally reduce to the same value). Here the first example defines a function that defines a function and returns the result of applying $x$ to the child-function (apply function then return), while the second example defines a function that returns a function for any input and then returns it on application of $x$ (return function then apply).

$\lambda f.\lambda x.((ff)f)x$ is a distinct lambda term from $\lambda f.\lambda x.(f(ff))x$.


Why there's a single accepting state in G-NFA's?

A GNFA (generalized NFA) can have any number of accepting states, just like an ordinary DFA/NFA.

But, as you suspect, the conversion of NFAs to regular expressions is easier if there's only one accepting state.  At each step of the conversion algorithm, you remove one state that isn't the start state and isn't the accepting state, and you modify the regular expressions that label the edges of the remaining transitions. The point is that, eventually, you end up with an automaton that has a start state, an accepting state, a single transition between the two and nothing else. The transition is labelled with a regular expression $R$ and the only possible transition from the start state is to reach the accepting state by reading some input that matches $R$.  Therefore, $R$ matches exactly the language of the machine.

If you had multiple accepting states, you'd end up with an automaton that had one start state and multiple accepting states.  In particular, there could be transitions between different accepting states.  That means there's no unique way of reaching an accepting state so it's not at all obvious how to produce a single regular expression that corresponds to the automaton.  You'd probably need to use a modified version of the standard algorithm to "crunch" those accepting states down to a single one. But that seems much more complicated than just having a single accepting state and dealing with a few harmless epsilon-transitions.


The quantity $\phi(n)$ grows like $\Theta(n)$.

For the lower bound, consider the following graph: a clique on $m$ vertices connected to a path of length $k = C\log m$ for an appropriate $C$ (so $n = m + k \approx m$), in which each vertex of the path is also connected to the first vertex of the path (the one incident to the clique). The maximal hitting time is some large number $M = \exp(k)$. The hitting time of two vertices in the clique is around $m \ll M$. The hitting time of a vertex on the path and any other vertex is at most $M$. So the average hitting time is at most roughly $m + \frac{2kn}{n^2} M = O(kM/n)$. In fact, the hitting time of a vertex at distance $t$ from the clique is roughly $\exp(t)$ (for $t \gg \log m$), and if we take this into account then we get an average hitting time of roughly $m + \sum_{t=1}^k \frac{2n}{n^2} \exp(t) = O(M/n)$. This shows that $\phi(n) = \Omega(n)$.

For the upper bound, let $H_{ij}$ be the maximum hitting time. The triangle inequality shows that for each $k$, either $H_{ik} \geq H_{ij}/2$ or $H_{kj} \geq H_{ij}/2$. So at least $n/2$ of the hitting times are at least $H_{ij}$, showing that the average hitting time is at least $H_{ij}/n$. This shows that $\phi(n) = O(n)$.


Regular expressions can be turned into (nondeterministic) finite automata very easily. What your automata are missing are start- and final states.

Once you have marked those, its very simple: If you have the automaton $A_1$ for $(a|ba)$ and $A_2$ for $(a|ba)^*$, to get an automaton for $(a|ba)(a|ba)^*$, just add $\varepsilon$-transitions from all finite states of $A_1$ to the start state of $A_2$. (This is btw part of the Thompson-construction, in case you want to look it up :) ) If needed, you can then remove all $\varepsilon$-transitions.

If you directly want to construct a $\varepsilon$-free NFA, you can use Glushkovs construction.


Is it known whether the MD5 algorithm is surjective?

Q: Does MD5 map to all possible 128 bit numbers?

Taking into account the facts that MD5 accepts input of the arbitrary length, the output is "only" 128 bits, and the algorithm itself which behaves similarly to random functions, I would expect that the all outputs are possible. However, without any strong mathematical evidence, this is merely a speculation, or in the best case, the hunch.

  Q: The answer probably is yes, for arbitrary x, and probably no proof exists.

Exactly, there is no proof (currently). Proving that MD5 is surjective would require either one of these:

Brute force check - taking into account coupon's collector problem, it takes something like 10^40 inputs to hit all 128-bit outputs. Assuming again that MD5 behaves similarly to random function, that should be enough to verify in the case that MD5 is surjective.
Concrete mathematical proof - eventual proof of surjectivity should be able for arbitrary 128-bit number y prove that there exists some input x such that MD5(x) = y. That should require deep mathematical analysis of MD5 function and it would probably shed some light on reversing this hash function. Even though MD5 is far from desirable hash function, it is still not known how to predict the input based on the given output.


Relocation means moving stuff from one place to another. In your case, there is a program which contains some absolute addresses, which make sense if the program is located at a certain address A. If the program is loaded to a different address B, we need to update all of these addresses, translating them by B−A. This is address relocation. A loader (a program loading another program to memory) which does this is called a relocating loader.


How can I translate this quantified logical expression into english

The negation is that every woman has an airline that she has never flown with. This is equivalent to saying that, for every woman there's an airline with the following property:

for every flight in the whole world, either the woman was not on that flight (regardless of what airline operated it) or the flight was not operated by that airline (regardless of whether the woman was on it or not).

That is, there was no flight by the airline in question that the woman was on.

This is not quite the same as what you have.


The Wikipedia article defines a null links as "absent children of the nodes", presumably "absent" in the sense of what nodes are missing to obtain a perfect binary tree (i.e., "a binary tree in which all interior nodes have two children and all leaves have the same depth or same level"). Under this definition, leaves (i.e., the nodes in the last level of the tree) do not have links. Hence, because all other levels are filled, to determine the number of null links you need only look at the previous to last level of the tree. This also explains the maximum case (i.e., "where only 1 node exists in bottom-most level")


CFG of all regular expressions over a binary alphabet

You are quite close to the solution. We will use a few variables, each corresponding (intuitively) to some other "thing". Specifically, we will use the variables $S,E,A,B$.
$S$ is the starting variable. $E$ is a variable that will produce a valid regular expression (its called $E$ as short for "expression"). $A$ will be some valid string over the alphabet $\{0, 1\}$, and $B$ will be a non-empty string over that same alphabet.
The CFG will now be:
$S\rightarrow E$
$E \rightarrow (E)(E) \space | \space E+E \space|\space E^* \space | \space (E) \space|\space A$
$A\rightarrow B\space |\space e$
$B \rightarrow 0B \space | \space 1B \space | \space 0 \space | \space 1$
I hope this CFG is what you are looking for! (I don't know if it is, since you didn't state the definition of the syntax of a regular expression using this alphabet, so I have only tried to go by the examples)


What kinds of problems are modeled by a recursive definition of a set of strings?

The definition you quote is a formal definition of strings which is particularly conducive to induction. There are many other ways to define strings, for example as sequences of letters, or more exactly as mappings $f\colon \{1,\ldots,n\} \to \Sigma$ for some $n \in \mathbb{N}$.

There are several different ways of understanding your definition, which is stated rather informally. The usual interpretation is as a least fixed point: $\Sigma^*$ is the least set which contains $\lambda$, and for each $w \in \Sigma^*$ and $\sigma \in \Sigma$, also $w\sigma \in \Sigma^*$; here you should think of concatenation as some formal operation, which is perhaps more appropriate to write as (say) $(w.\sigma)$.

What is a least fixed point? In this case, it is the intersection of all sets satisfying the two conditions stated above. One can prove that in general, such sets can be constructed just in the way that you describe: start with the empty set, and repeatedly a closure operation $C$, which in this case is
$$ S \to S \cup \{\lambda\} \cup \{w\sigma : w \in S, \sigma \in \Sigma\}. $$
Form a sequence $S_0 = \emptyset$, $S_1 = C(S_0)$, $S_2 = C(S_1)$, and so on, and take ${\cal S} = \bigcup_{n=0}^\infty S_n$. It is not too hard to show that ${\cal S} = C({\cal S})$, and moreover ${\cal S}$ is the least fixed point.

Another way of thinking of these rules is as a proof system for demonstrating that a certain expression is in $\Sigma^*$. We have an axiom $\begin{array}{c}\\\hline \lambda\end{array}$ and an inference rule $\begin{array}{c} w \\\hline w\sigma \end{array}$ valid for all $\sigma \in \Sigma$.

A third way is through induction: a property $P$ holds for all $\Sigma^*$ if $P(\lambda)$ and for all $\sigma \in \Sigma$, $P(w) \longrightarrow P(w\sigma)$. This is how we usually use this definition.

Given this definition, it is possible to define operations on strings and to prove theorems on strings. For example, length is defined by $|\lambda| = 0$ and $|w\sigma| = |w| + 1$, and concatenation by $x::\lambda = x$ and $x::(w\sigma) = (x::w)\sigma$; it is straightforward to prove by induction (on $y$) that $|x::y| = |x| + |y|$.

This sort of definition is common in the more formal parts of computer science. Other parts will prefer the informal definition "$\Sigma^*$ is the set of all words over $\Sigma$", or more explicitly, "$\Sigma^*$ is the set of all finite sequences of elements of $\Sigma$".


Is Turing Reduction always in context to decidable languages?

Absolutely not. In fact, these are most useful when $B$ is undecidable.

Diagonalization was used to show the Halting problem undecidable, but most other problems were shown to be undecidable through a reduction:

Suppose we have a subroutine solving $B$
Show that we can use that subroutine to solve $A$.
If $A$ is undecidable, then we have a contradiction, so we know $B$ must also be undecidable.

That said, the a proper Turing reduction should always halt. It's cheating if you say "I can use $B$ to make a program that either solves $A$ or runs forever". That's not useful in general.

(Although if you used $B$ to find a recognizer for $A$ where $A$ is not recursively-enumerable, you could show that $B$ is not decidable/recursively-enumerable, depending on your initial assumption about $B$.)

If $B$ is decidable, and you reduce $A$ to $B$, all you've done is create an algorithm deciding $A$. Which is useful, but you don't need a formal notion of reduction to do that.


Can someone explain the logic diagram for the Boolean expression NOT A OR B AND C

The question is assuming that the operators precedence goes $NOT \rightarrow AND \rightarrow OR$, which is pretty standard for boolean logic.

Hence the proper parathensization would be $\text{((NOT A) OR (B AND C))}$, which correspods to the correct diagram, whereas the partial credits corresponds to $\text{(((NOT A) OR B) AND C)}$, which would just be a left to right evaluation of the operators.


Finding pair of sum in sorted array in time complexity less than $O(n)$

Your interviewer is wrong.
Suppose that you had an algorithm which gets as input a sorted integer array $A_1,\ldots,A_n$, outputs Yes iff $A_i + A_j = 0$ for some $i \neq j$, and always accesses at most $n-1$ inputs.
Suppose first that $n = 2m$ is even, and consider the following sorted integer array $B$:
$$ -2m, -2(m-1), \ldots, -4, -2, 1, 3, \ldots, 2(m-1)-1, 2m-1. $$
This array contains no solution to $B_i + B_j = 0$. For any index $i$, we can create a sorted integer array $B^{(k)}$, differing only in the $k$'th entry, which does have a solution to $B^{(k)}_i + B^{(k)}_j = 0$.
Now run the given algorithm. Whenever it tries to access a position $A_i$, answer the value $B_i$. By assumption, the array terminates without querying some position, say $A_k$. Therefore the algorithm behaves the same when given as input the arrays $B$ and $B^{(k)}$, although the answer is No for the first one and Yes for the second one.
When $n=2m+1$ is odd, a similar argument works with the following sorted integer array:
$$ -2m, -2(m-1), \ldots, -4, -2, 1, 3, \ldots, 2(m-1)-1, 2m-1, 2m+1. $$


Confused about NP-Complete Proof Using Reduction

Your solution is a far way off from being correct. It seems that you are trying to use different transformations for both directions of the proof, while you should actually be using a single transformation from subset sum to the scheduling problem.

  I try to show that this problem [scheduling] is at least as hard as SubsetSum problem.

Subset Sum is a hard problem; we don't think it's likely that it can be solved in polynomial time. If you want to show that scheduling is hard, then you need to show that if we could solve scheduling in polynomial time, then we can also solve subset sum in polynomial time.

What you are given is an instance of subset sum $\{a_1,a_2,\ldots, a_n; T\}$ and a magic machine that somehow solves the scheduling problem in polynomial time. We want to show that it is unlikely that this magic machine could exist, therefore we will show that using this magic machine we can solve subset sum in polynomial time (which we think is probably not possible).

For this, you need a transformation that takes an instance $A$ of subset sum as input, and gives as output an instance $B$ of the scheduling problem, such that $A$ has a feasible solution if and only if $B$ does. That is, being able to find a solution for $B$ (in polynomial time) will also let you find one for $A$ (in polynomial time).

  Assume that $∃ I⊆\{1,2,..n\}$
  such that $∑_{i∈I}a_i=T$; then we can design a transformation such that assigns a subset $\{r_i,p_i,d_i\}$ some value, and show that taking this set as input to schedule problem will also return True. For example, assign start value to each of job to be 0, process time for each job to be $a_i$, deadline for each job to be $\sum_{i\in I} a_i$.

You can't do this. You can't base the transformation on the assumption that the subset sum instance is solvable. You don't know $I$ (because this is the hard-to-compute thing you're trying to compute), so you can't use it to construct the transformation. You can only use $I$ to show that, the transformed instance - which you constructed without knowledge of $I$ - has a solution.

Hint: you need to design an instance of the scheduling problem that is forced to split the jobs into two groups (one summing up to $T$, one to $\Sigma a_i - T$). For this, it might be useful to have one or two additional jobs that must be scheduled at a fixed point in time (by setting $r_i+p_i=d_i$).

To summarize: a correct NP-hardness proof consists of the following steps:

Take an NP-hard problem (e.g., subset sum) and design a transformation $f$ that maps an instance $A$ of this problem to an instance $B=f(A)$ of the problem you want to show NP-hard (e.g., scheduling).
Show that, if $A$ has a solution (is a yes-instance), then $B$ is a yes-instance
Show that, if $B$ is a yes-instance, then $A$ is a yes-instance (or show the converse: if $A$ is a no-instance (has no solution) then $B$ is a no-instance as well.


Is SGD used in machine learning libraries?

Big yes.

In fact, gradient descent is one of the fundamental tools used by many supervised learning models.

You can check out a very nice docs page about how it is used in scikit-learn.


Wave overlaps need not cause just 1-bits with a too high amplitude. They could also flip bits around, or nullify each other. Thus error correction is not as easy as you describe and one actually has to use some kind of checksumming like CRC to detect errors reliably.


Take $k=1$. No need to go further, any more $a$ can be absorbed by $u$ without risk.

So you need $u$ to have at least 1 $a$ and only $a$'s or $b$'s. Therefore, $L_1$ is described by $a(a|b)^*a(a|b)^*$ and is regular.

For the side question (at most $k$ $a$'s, let's call that language $L_2$), you can reason in a similar fashion to get $u$ as small as possible. For simplicity let's consider $L_3$ the intersection of $L_2$ with the one denoted by $a^*ba^*$. You have $L_3=\{a^k b a^j, k \geq j\}$. Intersection with its reverse yields $\{a^kba^k\}$ which is not regular, therefore $L_2$ is not regular either since regular languages are closed under intersection and reversal.


What's the error-correcting capacity (randomly errors, or burst errors) of polar code?

I am not an expert but I think you may be asking the wrong question. Polar codes don't have a meaningful "error correction capability" obtainable as in algebraic codes by (d-1)/2. Alternatively, this is not the meaningful parameter of significance.

For finite lengths their performance is usually analyzed in BEC (Binary Erasure Channel) and AWGN channels (Additive White Gaussian Noise). The well-cited paper On Finite-Length Performance of Polar Codes: Stopping Sets, Error Floor, and Concatenated Design by A. Eslami and H. Pishro-Niki on arxiv here as well as some more recent papers confirm this.


Prove np-hardness of dividing items from the lists

To prove that a problem is NP-hard, we need to reduce an NP-hard problem to it (which in this case as you mentioned would be 3-coloring).

So what we are trying to do, is to map every graph $G(V,E)$ to an instance of your problem, where every node $v_i$ will be mapped with an element $el(v_i)$ and every edge $\epsilon\{v_1, v_2\}$ would be represented with a two-element list $\{el(v_1), el(v_2)\}$.

So now a coloring $f:V\rightarrow C$ would be reduced to a coloring on the set of elements in your problem which means, if we found a coloring on the elements of the proposed problem, we can use the same coloring on our graph and it would be a proper coloring.

Proof.
If $f:V\rightarrow C$ isn't a proper coloring, that means there is an edge with both nodes having the same color, which means there is a set with two elements and both of them have the same color which contradicts the statement of your problem.


A Formula For Generalized Josephus problem

In "Concrete Mathematics" by Graham, Knuth, Patashnik. Look in Chapter 3: Integer functions.


On asymptotic complexity class notation?

The time hierarchy theorem shows that there are problems which can be solved in time $O(n^{\log n})$ but not in time $O(n^{\log\log n})$. These problems can be solved in time $O(n^{n^\epsilon})$ for any $\epsilon > 0$, but not in polynomial time.


Checking my understanding of right quotient

If $L_1=ab^*c$ and $L_2$ is $b^*c$ then $L_1/L_2$ is $ab^*$.

Note that the $b$'s are not forced to disappear.
For instance (as part of these languages) $\{ab^{10}c\}/\{b^3c\} = \{ab^7\}$.