DCEL operations on quad-edges, Twin, Next, and Prev

It looks like you took these diagrams from this CMU publication. This publication also refers to the C++ header cell/edge.hh, describing basic and derived operations on edges.

So, according to this header, operations Rot, InvRot, Sym and Onext are considered basic ones, and all the other operations - derived ones. The DCEL operations next and prev are equivalent to quad-edge operations Lnext and Lprev, which are defined in this header as inline functions (I'm dropping the C++ syntax and keeping the meaning):

e.Lnext = e.InvRot.Onext.Rot
e.Lprev = e.Onext.Sym

So, your formulas look correct, with slightly overused operation Rot.


Bottom-Up Evaluation of Inherited Attributes

Using a top-down translation scheme, we can implement any $LL$-attributed definition based on $LL(1)$ grammar.
Using a bottom-up translation scheme, we can also implement any $LL$-attributed definition based on $LL(1)$ grammar (each $LL(1)$ grammar is also an $LR(1)$ grammar).  Using bottom-up translation scheme, we implement $LR$ grammar actually but since $LL(1) \subset LR(1)$ we can safely implement $LL(1)$ grammar as well.


Generating a random path in a grid without deadlock

You have a solid grid graph, and want to generate a random Hamiltonian path in it.  The following paper describes a polynomial-time algorithm to generate such a path, randomly (from a distribution that is close to uniform):

Self-testing algorithms for self-avoiding walks. Dana Randall, Alistair Sinclair. Journal of Mathematical Physics, vol 41 no 3, pp. 1570–1584, 2000.

Be warned that the algorithm is fairly complex.

Here is a more recent paper that also proposes an algorithm to solve this problem:

Secondary Structures in Long Compact Polymers.  Richard Oberdorf, Allison Ferguson, Jesper L. Jacobsen, Jane' Kondev.  arxiv.org:cond-mat/0508094

On cursory inspection, it looks like it might be easier to implement.

Other related work that might possibly be of interest:

The following paper proposes an algorithm to count the number of such Hamiltonian paths:

A matrix method for counting hamiltonian cycles on grid graphs.  Y. H. Harris Kwong, D. G. Rogers.  European Journal of Combinatorics, vol 15 no 3, pp.277-283, 1994.

I found a reference that claims that the following paper describes

Enumeration of tours in Hamiltonian rectangular lattice graphs.  Basil R. Myers.  Mathematics Magazine, vol 54, no 1, Jan 1981.

Often, if you can count the number of objects of a particular type, you can sample uniformly at random from the set of such objects.  So, that would be a good starting point to look, if you don't like either of the two papers mentioned above.

The following paper describes how to find a Hamiltonian path of such a solid grid graph (but with no guarantees of any particular random distribution on the output):

Hamiltonian Cycles in Solid Grid Graphs.  Christopher Umans, William Lenhart.  FOCS 1997.

See also https://mathoverflow.net/q/1592/37212, https://stackoverflow.com/q/7371227/781723, Hamiltonian path in grid graph.


I want to figure out whether my problem described below is reducible to the set cover problem

Hint: For each element $x \in U$, let $A_x = \{i : x \in S_i\}$. Then $T$ is a solution to your problem iff $\{A_x : x \in T\}$ covers all of $\{1,\ldots,n\}$. This problem is known as minimum hitting set.


How can I mathematically show the largest possible value of a 64-bit double?

Assuming IEEE754 64 bit format:
You have an 11 bit exponent field, a 1 bit sign field, and a 52 bit mantissa field.
The exponent field can have values from 0 to 2047. An exponent field of 0 is reserved for denormalized numbers, and an exponent field of 2047 is reserved for infinity and Not-a-number. You could say that +Infinity is the largest value, but I assume you are looking for the largest finite value. The largest exponent field for a finite value is 2046.
This format has an "exponent bias" of 1023, that is the numbers 1.0 ≤ x < 2.0 have an exponent field of 1023. So the largest value has an unbiased exponent of 2046 - 1023 = 1023, and numbers with an exponent field of 2046 are in the range $2^{1023} ≤ x < 2 \cdot 2^{1023}$.
The mantissa field is 52 bit, with an implicit leading 1 bit. So a mantissa field with a value m, 0 ≤ m ≤ $2^{52}$, means the actual mantissa is 1 + $m \cdot 2^{-52}$. The largest possible mantissa field is all bits 1 or $2^{52}-1$, this makes the largest possible mantissa $2-2^{-52}$.
Multiply with the exponent, and the largest possible number is $2^{1023} \cdot (2-2^{-52})$ or $2^{1024} \cdot (1-2^{-53})$ or $2^{1024} - 2^{971}$


How can OS schedule disk requests efficiently without knowing the LBN to PBN mapping ?

Modern disks interfaces provide an approximation of position called the logical base address.  This is just a linear integer indexing scheme where each block gets a unique integer assigned to it.

While you can't calculate an exact "distance" (in terms of arm movement latency and rotational latency) between two blocks it is approximately the case that if the difference between address $a$ and address $b$ is smaller than the distance between address $a$ and address $c$ then block $a$ will be closer to block $b$ than it is to block $c$.

Disk scheduling algorithms try to improve average latency or average throughput without being significantly unfair or causing starvation.  They also don't know about requests that are going to arrive in the future, so whatever they do needs to be an approximation based only on the requests they've already seen.

Since the algorithms are approximate anyway, the fact that we don't know the exact distance between two requests is not particularly a problem.


fastest way to identify "singular row" of a matrix

This is not an answer, but a response to this comment.
Assume that $A$ is the matrix which columns are the rows that we want to test for linear independence. I am putting them are columns for no other reason than personal comfort.
Doing the row transformations required in Gaussian elimination correspond to multiplying $A$ from the left by some elementary matrices. Assume that $T$ is the product of all elementary matrices corresponding to the row transformations needed to put $A$ in echelon form. So, $TA$ is is echelon form.
If each column has an echelon then the system $TAx=0$, with $x$ a column vector of the right size, has only the solution $x=0$. Since $T$ is invertible, we have that $Ax=0$ has only the solution $x=0$. Since $Ax$ is nothing else than a linear combination of the columns of $A$ using the components of $x$ as coefficients, what we got is that the columns of $A$ are linearly independent.
Now assume that some columns of $TA$ don't have echelons. Let's call these the dependent columns. You can give any values you want to the components of $x$ corresponding to the positions of the dependent columns and then solve the resulting system $TAx=0$ for the remaining components, by backward substitution. In particular we can put non-zero values to the components of $x$ corresponding to the dependent columns of $TA$. This gives you a solution of $TAx=0$. Since $T$ is invertible, it is also a solution of $Ax=0$. For this $x$ the expression $Ax$ is a linear combination of the columns of $A$ that is equal to zero and the coefficients of the dependent columns are non-zero. So, the equation $Ax=0$ expresses each of the dependent columns in terms of all the other columns.
So, the dependent columns are linearly dependent of the columns with echelon in them (independent columns).


Write down all accepting paths, that is paths from the starting state to final states. These are all the words the given automaton can accept; if the set is the desired one, q.e.d.

This is only possible and a rigorous proof for (co-)finite languages. Once you have cycles you have to apply induction. See here for an in-depth explanation on how to do this for grammars; it's similar for automata.


In Bankers Algorithm, with three processes, in the question of need <= work(aka available). Is the need of 1 0 1 <= 0 0 2 work?

In Banker's Algorithm,

Every processes are compared individually.

So, In your question

If the Need is 1 0 1 and available matrix is 0 0 2, then this need can't be satisfied. Because there is no resource available for Process A.


Difference between regular expression and grammar in automata

Regular expressions, regular grammars and finite automata are simply three different formalisms for the same thing. There are algorithms to convert from any of them to any other.

The basic reason that we have all three is that they were created independently, with the first set of equivalences (there are several other formalisms as well) proven by Kleene (this result, or part thereof is called Kleene's Theorem).

So in that context, depending on which way round you want to run the models, they all recognise or generate strings of a regular language, and mathematically, there is, in that sense, no difference.

Of course sometimes one model is easier to use than another for a particular task, due to the details of the formalism. Furthermore the way they work in a human's head is often a little different, finite automata "feel" like computers, regular expressions "feel" like you're constructing a string out of smaller substrings and regular grammars "feel" like a more traditional grammatical derivation or classification of a sentence in a language (unsurprisingly when you look at the history).

So to compare the two, let's define them:

Regular Expressions

So regular expressions are recursively defined as follows:

$\emptyset$ is a regular expression
$\varepsilon$ is a regular expression
$a$ is a regular expression for every $a \in \Sigma$
if $A$ and $B$ are regular expressions then

$A\cdot B$ is a regular expression (concatentation)
$A \mid B$ is a regular expression (alternation)
$A^{\ast}$ is a regular expression (Kleene star)

Along with some semantics (i.e. how we interpret the operators to get a string), we get a way of generating strings from a regular language.

Regular Grammars

Regular grammars consist of a four tuple $(N,\Sigma, P, S \in N)$ where $N$ is the set of non-terminals, $\Sigma$ is the set of terminals, $S$ is the start non-terminal and $P$ is the set of productions which tell us how to change the start symbol, step by step, into a string in $\Sigma^{\ast}$. $P$ can have its productions drawn from one of two types (not both though):

Right Linear Grammars

For non-terminals $B$, $C$, terminal $a$ and the empty string $\varepsilon$, all rules are of the form:

$B \rightarrow a$
$B \rightarrow aC$
$B \rightarrow \varepsilon$

Left Linear Grammars

Left linear grammars are the same, but rule #2 is $B \rightarrow Ca$.

Things to Ponder

So looking at these definitions and playing with them, we can see that regular expressions look like matching rules, or ways of dealing with strings a bit at a time.

Grammars seem to "label" sections of the string, and group labels under new labels to validate the string (i.e. if we can get from $S$ to the string, or vice versa, we're happy).

However these are really doing the same fundamental thing, and how you view the metaphor of their function is really up to you.


Theoretical precision needed to get $n$-bits of the evaluation of some sum

I may be misunderstanding the question, but I don't think we have enough information to tell.

Consider, for example:

$$A = \left\{ \frac{1}{4}, \frac{1}{2}, \frac{3}{4} \right\}$$

and:

$$P(x) = \left( x - \frac{1}{4} - \varepsilon \right) \left( x - \frac{1}{2} + \varepsilon \right) \left( x - \frac{3}{4} - \varepsilon \right)$$
$$Q(x) = 1$$

for some small $\varepsilon$.

Assuming that $\varepsilon$ is small enough, both polynomials are height-bounded by 1.

The sum is:

$$S = - \frac{5}{16}\varepsilon + \varepsilon^3$$

The question is how you would evaluate $P$.

$$P(x) = \left(-\frac{3}{32} - \frac{5}{16}\varepsilon + \frac{1}{2}\varepsilon^2 + \varepsilon^3\right) + \left( \frac{11}{16} + \varepsilon - \varepsilon^2\right) x + \left(-\frac{3}{2} - \varepsilon\right) x^2 + x^3$$

The number of bits of precision on the elements of $A$ are not relevant here; they are precisely representable with two significant bits. It seems to me that the precision you need to do the intermediate computation is more important.

For a small enough $\varepsilon$, you are going to get catastrophic cancellation whether you use the factorised form of $P$ or you use a method such as Horner's rule. At the very least, you need enough bits to represent $-\frac{3}{32} - \frac{5}{16}\varepsilon$ such that you have $n$ significant bits in the $\varepsilon$ term, so you can subtract $-\frac{3}{32}$ to get a good enough answer.


The term class here has absolutely nothing to do with OOP classes. Rather, a class determines which possibility in a C union an object takes.

For example, one definition of a binary tree is: a binary tree is either a leaf or a pair of binary trees. Leaves form one (boring) class, pairs of binary trees form another.

Mathematical terminology often uses words which have other meanings in common usage. You should get used to that.


Regular set corresponding to regular language

A regular language $L$, is a set over the alphabet $\Sigma$ (that is, $L\subseteq \Sigma^*$) that has a regular expression that generates it. Therefore, by definition - any language of a regular expression is a regular language.
Regarding the language in question, $01$ for example is not generated by $(0+10^*)$, since it is not $0$ and also is not generated by $10^*$ (since it doesn't start with $1$). The same goes for any string starting with $0$, and has more than one letter in it.


The usual distinction is that strong AI, also known as artificial general intelligence, refers to systems that can perform arbitrary tasks requiring intellect, whereas a weak AI is only able to perform specific intellectual tasks.  So, for example, a computer chess program or a system that was able to compose interesting music would be a weak AI, since it only does one thing.

Passing the Turing test would indicate something close a strong AI. Although one could argue that it only requires performing a specific intellectual task (i.e., conversation), that conversation could range over just about anything that humans can intellectualize about.  Indeed, the Wikipedia page I linked above mentions the ability to pass the Turing test as a component of an operational definition of strong AI.


How the operating system allocated to dual-channels memory?

You are completely misunderstanding what dual channel memory means; it is an implementation detail that is supposed to make memory access faster but completely invisible during operation.

Let's say you have (simplified) a computer with two RAM chips. The computer could have one connection to both chips, or two connections, one to each chip. The CPU issues a command to read say 256 bit. With single channel memory, one command to transfer 256 bit is sent to the two RAM chips, and it takes some time to transfer 256 bit. With dual channel memory, the CPU automatically (without the OS doing _anything) sends two commands, one to each RAM chip, and each chip transmits 128 bits through its channel. Both commands run in parallel, so the time for memory transfer will be half the time.


Is there a useful algorithm with a decreasing asymptotic time?

No. If the running time is approaching zero as the input size grows, then the algorithm can’t even perform a single step.

If you mean that the running time approaches some positive constant, then this is just $O(1)$, because $\Omega(1)$ is a lower bound for any algorithm.


how can i find the Maximum Degree of Concurrency?

Graph a:

Phase 1: Task 1, Task 2, Task 3 and Task 4 can be executed parallelly (if you have more than 3 processors). So the degree of concurrency in this phase is the sum of the weights of those four nodes: 10+10+10+10 = 40.

Phase 2:  Task 6 and Task 5 can be executed parallelly (if you have more than 1 processor). So the degree of concurrency in this phase is: 9+6 = 15.

Phase 3: You can execute only Task 7, so the degree of concurrency here is 8.

The maximum number of concurrency is max(40, 15, 8) = 40.
The average degree of concurrency is (40+15+8)/(10+9+8) = 63/27.

Graph b:

Phase 1: Task 1, Task 2, Task 3 and Task 4 can be executed parallelly (if you have more than 3 processors). So the degree of concurrency in this phase is: 10+10+10+10 = 40.

Phase 2:  You can execute only Task 5, so the degree of concurrency here is 6.

Phase 3: You can execute only Task 6, so the degree of concurrency here is 11.

Phase 4: You can execute only Task 7, so the degree of concurrency here is 7.

The maximum number of concurrency is max(40, 6, 11, 7) = 40.
The average degree of concurrency is (40+6+11+7)/(10+6+11+7) = 64/34.


How to write a custom editor for a new programming language?

There has been a shift during the last 5-15 years in how editors and IDEs are built. It was recognized that IDEs have to perform a lot of the same tasks that compilers do.

In fact, in order to support things like lexical highlighting, syntax highlighting, semantic highlighting, refactoring, warnings ("yellow squigglies"), errors ("red squigglies"), intelligent code completion, and all the other things that we have come to expect from a modern development environment, the IDE pretty much is a compiler. It needs to do almost all the things, except for optimization and the actual code generation. But, lexing, parsing, semantic analysis, type inference, type checking, symbol resolution, overload resolution, implicit resolution, control flow analysis, data flow analysis, etc., they all need to be performed. Modern IDEs are actually even expected to do more work than the compiler does, such as NULL checking and tracking for C-like languages, finding unreachable code or unused variables and parameters, finding redundant checks, etc. (For example, I recently found a bug in some of my JavaScript code by the editor telling me based on type information in the documentation comments that the then branch of an if statement was unreachable because the condition I was checking for was impossible.)

So, the change that I alluded to above, is that editors and IDEs are starting to use the actual compiler to perform all this analysis. This leads to some interesting requirements for the compilers, because the way they are used in IDEs and the way they are used as batch compilers is fairly different:

Batch compilers deal with complete programs, IDEs deal with incomplete programs. (Analysis while you type.)
Batch compilers deal with working programs, IDEs deal with broken programs. (Most of the time, while you write the program, it will not be in a working state.)
Batch compilers can take as much time and as much memory as they want, IDEs must ideally give feedback within milliseconds after each keypress, and the "IDE compiler" must share its memory with the editor and the IDE.
A batch compiler's job ends as soon as it hits an error, an IDE only gets started. (E.g. giving hints about how to fix the error, or analyzing the rest of the file.)

This pretty much requires a high degree of re-entrancy, asynchrony, concurrency, and parallelism in the compiler. It requires it to be built in a modular design so that you can separate the optimizer and code generator. It requires it to be built as a library, not just a command line tool. It requires it to be built with open access to the parse tree, AST, flow graphs, etc.

So, not only are modern editors and IDEs built to take advantage of compilers, but modern compilers are built to be embeddable into IDEs.

One of the most high-profile compilers that were explicitly built to be able to be embedded into IDEs is Microsoft's Roslyn compiler for C# and VisualBasic.NET. (Actually, it was built to be even more than that: it was built to be a general platform for language analysis of and language tooling around C# and VB.NET that is easy enough to use that non-compiler writers can write e.g. their own static analysis rules.) Anything you see in Visual Studio, from IntelliSense to highlighting to squigglies to hints to errors to warnings … is built on top of Roslyn.

One of the reasons for creating Clang was that most existing C compilers were not designed to be used as anything but a command line batch compiler. Clang is explicitly designed to be embedded into IDEs and editors. As the documentation says, Clang is designed to Support Diverse Clients.

The Scala Compiler has long had a mode called the Presentation Compiler, which is an asynchronous version of the first 4 (of 27) phases of the compiler. The new compiler for Scala 3 is built from the ground up to support IDEs.

Going further, Microsoft has defined the Language Server Protocol originally for the TypeScript plugin in Visual Studio Code. The LSP is a JSON-RPC protocol that allows a language analyzer and an IDE to communicate with each other using a standard protocol. This turns the m×n problem of providing high-quality plugins for m languages for each of a set of n IDEs into an m+n problem of providing language servers for m languages and LSP clients for n IDEs.

If you implement a language server for your language, it will instantly work with any editor or IDE for which an LSP client is available (e.g. Eclipse, Atom, Sublime Text, Brackets, Emacs, Vim/Neovim, Visual Studio, Visual Studio Code, IDEA, …) And when you implement an LSP client for your IDE or editor, it will instantly work with any language for which a language server is available (e.g. Idris, C, D, Go, ECMAScript, TypeScript, ActionScript, Lua, PHP, Python, Ruby, Haskell, Erlang, Haxe, Elm, Elixir, even some not-so-obvious ones such as IBM Enterprise COBOL for z/OS maintained by IBM itself).

So, coming back to your question

  Let's say I've finished my compiler for my new language. Next step is write a custom editor with syntax highlighting (type checking and semantic can wait), is there a cookbook or any kind of guidance to accomplish this project?

The first piece of guidance on how to build a custom editor with syntax highlighting is to not build a custom editor with syntax highlighting. Build a language server.

The second piece of guidance is to not finish your compiler and then start working on the editing experience. Instead, build the compiler from the ground up to support the editing experience.


Why is the inapproximability $2^{n^\epsilon}$?

The two theorems are equivalent. You can write
$$
3^{n^\delta} = 2^{\log_2 3 \cdot n^\delta} = 2^{n^{\delta + \frac{\log \log_2 3}{\log n}}} = 2^{n^{\delta + o(1)}}.
$$
In particular, for any $\delta' > \delta$ there exists $N$ such that $3^{n^\delta} \leq 2^{n^{\delta'}}$ for all $n \geq N$. Conversely, $3^{n^\delta} \geq 2^{n^\delta}$.

Hardness of approximation results are only about "large enough $n$". Every problem can be solved exactly in polynomial time (even constant time) for all inputs of size at most $N$, for any fixed $N$.


Split-Find: maintaining dynamic graph connectivity information, under edge deletion

It sounds like you're looking for "decremental connectivity". The fastest result I could find was Wulff-Nilson's "Faster deterministic fully-dynamic graph connectivity", which "supports updates (edge insertions/deletions) in $O(\log^2 n/ \log \log n)$ amortized time and connectivity queries in $O(\log n/ \log \log n)$ worst-case time, where $n$ is the number of vertices of the graph."


Turing-completeness of Goto language with limited constants

No, that is not a proof.  "It seems obvious to me" is not a proof.
To obtain a formal proof, describe an algorithm that, given a Goto program $P$, outputs a Goto$_{17}$ program $P'$, and prove that $P'$ simulates $P$.  Basically, you need to construct a compiler that compiles from Goto to Goto$_{17}$, and then prove it correct.


This problem is known as Independent Set (and not two-coloring). Your intuition is quite correct though.

As a hint, I'd like to offer the following definitions:

Let $n$ be a node of the binary tree. Let $P(n)$ be the maximum profit that can be attained from the subtree rooted at $n$ given that $n$ itself may not be included. Similarly, let $Q(n)$ be the maximum profit that can be attained from the subtree rooted at $n$ given that $n$ itself may be included.


Does this context-free grammar generate a regular language?

The grammar can be transformed to

$\quad$ $S \to SBB \mid b $
$\quad$ $B \to SBS \mid a$

Let $L_S$ be the language generated by the rules above (with $S$ as the start symbol). $L_S$ is context-free by definition.

We will prove it is not regular. The idea comes from the rule, $B\to SBS$.

Let $L_B$ be the language generated by the two rules above with $B$ as the start symbol.

Claim: We have the following inclusions of languages.
$\quad\{b\}\cup\{b^{i+1}ab^ia\mid i\ge0\}\subseteq L_S$
$\quad\{b^iab^i\mid i\ge0\}\subseteq L_B$

Proof: Use mathematical induction on $n$, the upper bound for $i$.

The base case when $n=0$. $S\Rightarrow SBB \Rightarrow^*  baa$ and $B\Rightarrow a$.
Suppose it is true for $n$. Then $B\Rightarrow SBS\Rightarrow^* b(b^nab^n)b=b^{n+1}ab^{n+1}$. $S\Rightarrow SBB\Rightarrow^* b(b^{n+1}ab^{n+1})a=b^{(n+1)+1}ab^{n+1}a$. So it is true for $n+1$ as well.

Claim: We have following inclusions of languages.
$\quad L_S\subseteq E_S :=\{ba^{2i}\mid i\ge0\}\cup\{b^{i+1}ab^ia\mid i>0\}\cup\{\text{words that have at least three } a\text{'s}\}$
$\quad L_B\subseteq E_B:=\{a\}\cup\{\text{words that have at least two } a\text{'s}\}$

Proof: It is easy to check that $E_SE_BE_B\subseteq E_S$, $a\in E_S$, $E_BE_SE_B\subseteq E_B$ and $b\in E_B$.

The above two claims implies that $L_S\cap L(b^*ab^*a) = \{b^{i+1}ab^ia\mid i\ge0\}$, which is not a regular language. Since $L(b^*ab^*a)$ is regular, $L_S$ cannot be regular.

Exercise 1. Show that the following grammar generates a regular language.
$\quad$ $S \to SAS \mid b $
$\quad$ $A \to ASA \mid a$

Exercise 2. Show that the following grammar generates a non-regular language.
$\quad$ $S \to AB \mid b $
$\quad$ $B \to SA $
$\quad$ $A \to BS \mid a$


negative weight cycle detection using dijkstra's algorithm

No. In a graph with $n$ nodes, Dijkstra's algorithm never updates a node more than $n-1$ times, so your test will never change anything. More fundamentally, negative-weight edges or cycles don't cause Dijkstra to get into infinite loops; they just make it give wrong answers in some cases.

This answer on Stack Overflow gives more detail.


Movement on Labyrinth with Best First Search

It doens't matter which one you take, because they both have exactly the same value. Which one actually gets taken will depend on unimportant details of the implementation, such as the order the nodes were added to the tree.


Eliminate non-local references from closure

I think what you want is essentially conversion to static single assignment (SSA) form, followed by closure conversion, followed by conversion to continuation passing style.

Static single assignment form guarantees that each variable is written exactly once in the program text.  That this is the key step in converting imperative to functional programs is argued by

  Andrew W. Appel. SSA is functional programming.
  SIGPLAN Notices, 33(4), 1998.

  Richard A. Kelsey. A correspondence between continuation
  passing style and static single assignment form.
  Proc ACM SIGPLAN Workshop on Intermediate
  Representations, January 1995.

  Peter J. Landin. The mechanical evaluation of expressions.
  Computer Journal, 6(4):308–320, 1964.

This starts to get really interesting for programs with loops. You need to convert the loops into recursive calls, and make a unique copy for the variables written in each iteration of the loop.  In the traditional loop optimization community this technique is called scalar expansion or (sometimes) dynamic renaming.

  David J. Kuck, R. H. Kuhn, David A. Padua, B. Leasure,
  and Michael Wolfe. Dependence graphs and compiler
  optimizations. In Conference Record of the Eighth
  Annual ACM Symposium on Principles of Programming
  Languages, pages 207–218, Williamsburg, VA, January
  1981.

  Ron Cytron and Jeanne Ferrante. What’s in a name?
  The value of renaming for parallelism detection and
  storage allocation. In Proceedings of the 16th Annual International
  Conference on Parallel Processing, pages 19–27,
  St. Charles, IL, August 1987.

In the functional programming community this involves making closures and continuations explicit:

  Andrew W. Appel and Trevor Jim. Continuation passing,
  closure-passing style. Proc. Symp. on Principles of Programming Languages (POPL),
  1989.

  Guy Lewis Steele. RABBIT: A compiler for Scheme.
  Technical Report AITR-474, MIT Artificial Intelligence
  Laboratory, May 1978.

I needed to do these conversions, for the automatic parallelization techniques described in my dissertation.  Chapters 3, and 9.1.

  Matthew Frank, SUDS: Automatic Parallelization for Raw Processors, Ph.D. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, May 23, 2003.


How can a computer run an infinite loop?

In a contemporary processor there is, among many other things, a register (digital electronic component to hold some bits) called the Program Counter (PC). It holds the memory address to the current machine instruction.

During normal flow of the program, the PC will always be updated to address the next instruction. However, any loop will be implemented with so called branch or jump type instructions which will cause the PC to address some other instruction, rather than the next one.

One, if not the, simplest infinite loop, is one in which the PC is updated again to the same instruction.

An assembly (MIPS) code example (beq stands for Branch on Equal):

LABEL: beq $0, $0, LABEL # Comment: If 0 == 0,then goto LABEL.


Triangulating a simple polygon via its trapezoidal map

Yes, "it's easy to derive from such a decomposition of $P$ in linear time a triangulation of $P$."

Take a look at lemma 1. here.


Algorithm for compressing binary data that can efficiently be partially decompressed

Eliminate timestamps

If the data is sampled at regular intervals (e.g. three times per second), it is sufficient to store the timestamp of the first point and the interval. This enables you to calulate the offset from a timestamp and vice versa and grants you access to any datapoint in constant time.

Compression schemes

As others have already laid out, you will always lose the ability to seek when using a compression scheme. Compress blockwise and search within the blocks.

Lempel-Ziv-like algorithms

The Lempel-Ziv family and similar algorithms provide good compression for data with many/long reoccurring strings, but fail to recognize the relationship between integers in noisy or slowly changing sequences. Below are three sequences of integers: the first consists of constant values, the second counts upward and somehow resembles timestamps, and the third is noisy and represents a sensor reading.

$$[900, 900, 900, 900, 900, 900, 900, 900, 900, 900]$$
$$[890, 892, 894, 896, 898, 900, 902, 904, 906, 908]$$
$$[900, 890, 905, 901, 918, 892, 919, 916, 904, 920]$$

Zip will greatly reduce the size of the first sequence, have a hard time on the second and won't provide any compression on the third.

Delta encoding

To reduce the number of bits per number, the range of possible numbers must get smaller. If we incorporate the knowledge that values change slowly, we conclude that storing only the difference to the previous value yields values close to zero. The three example sequences above become:

$$[900, 0, 0, 0, 0, 0, 0, 0, 0, 0]$$
$$[890, 2, 2, 2, 2, 2, 2, 2, 2, 2]$$
$$[900, -10, 15, -4, 17, -26, 27, -3, -12, 16]$$

If we know the rate of change is approximately constant, as in case of timestamps, we can apply delta encoding twice. Below is a sequence of timestamps in original form and after applying delta encoding once/twice.

$$[96, 296, 497, 701, 904, 1102]$$
$$[96, 200, 201, 204, 203, 198]$$
$$[96, 104, 1, 3, -1, -5]$$

All we need now is a way to make the (on average) smaller numbers into less disk space.

Variable width integers

We can reduce the number of bits by using variable width integers that use less bits for smaller (by magnitude) numbers. The usual encoding is:

For numbers that fit into 7-bit signed integers, use one byte.
For larger numbers

store the 7 least significant bits in one byte.
set the MSB (continue-flag).
encode the remainder in the following bytes, using the same encoding.

This way 32-bit integers are encoded in 1-5 bytes, dependent on the actual value.

Conclusion

If possible, don't store timestamps at all (independent of compression).
Compress in blocks. Trade-off between access time and compression.
If the sensor readings are exactly constant for some periods of time, zip is the way to go.
If the sensor readings are approximately constant, use delta encoding.
If the timestamps are changing at approximately constant rate, use delta encoding twice.


Maximizing the boolean combination of given real numbers

Maybe there is something I do not understand in your question, but the way it is formulated it seems that the set of solutions is:

set $b_i=1$ if $x_i > 0$
set $b_i=0$ if $x_i < 0$
all others $b_i$ can either be zero or one

It is clear that any other assignment will give you a lower value (either by adding a positive value or not adding a positive one). If $|\{i:x_i=0\}|=K$, then you have $2^K$ solutions. This can be settled in $O(n)$ by a simple linear scanning of $x_i$ values (even less if they are ordered).


How do calculators convert from decimal to fraction?

I don't know what calculators actually use, but there are definitely better algorithms than your brute force search.

There are several notions of “best approximation” of a real number by a rational. Depending on how you rate the benefit of a good approximation compared to the cost of a large denominator, you get different notions.

One of these is the best approximation with a bounded denominator: given $x \in \mathbb{R}$ (real to approximate) and $n \in \mathbb{N}^*$ (denominator bound), find $p/q$ with $p \in \mathbb{Z}$, $q \in \mathbb{N} \cap [1,n]$ that minimizes $x-p/q$. The sequence of best approximations for increasing values of $n$ turns out to be relatively easy to calculate and to have other nice mathematical properties: it's the continued fraction expansion of $x$. The continued fraction expansion is a way to construct an infinite sequence of rationals that converges to $x$, and its terms are exactly¹ the best bounded-denominator approximations of $x$. The series is easy to calculate incrementally.

In a calculator, you don't necessarily want the best approximation in that sense: what denominator bound would you pick? If you pick one that's too low, you'll miss some “interesting” rationals. If you pick one that's too large, you end up treating basically everything as some large integer divided by a power of ten.

¹  Except for some boundary effects when $x$ is rational, see a reference for details.


Applying Expectation Maximization to coin toss examples

(This answer uses the second link you gave.)

$\newcommand{\Like}{\text{L}}\newcommand{\E}{\text{E}}$Recall the definition of likelihood: $$\Like[\theta | X] = \Pr[X| \theta] = \sum_Z \Pr[X, Z | \theta]$$
where in our case $\theta = (\theta_A, \theta_B)$ are the estimators for the probability
that coins A and B respectively land heads, $X = (X_1, \dotsc, X_5)$ being the outcomes
of our experiments, each $X_i$ consisting of 10 flips, and $Z = (Z_1, \dotsc, Z_5)$
being the coin used in each experiment.

We want to find maximum likelihood estimator $\hat{\theta}$. The Expectation-Maximization
(EM) algorithm is one such method to find (at least local) $\hat{\theta}$. It works
by finding the conditional expectation, which is then used to maximize $\theta$.
The idea is that by continually finding a more likely (i.e. more probable) $\theta$
in each iteration we will continually increase $\Pr[X,Z|\theta]$ which in turn, increases
the likelihood function. There are three things that need to be done before going forward
designing an EM-based algorithm.

Construct the model
Compute Conditional Expectation under the model (E-Step)
Maximize our likelihood by updating our current estimate of $\theta$ (M-Step)

Construct the Model

Before we go further with EM we need to figure out what exactly it is we are computing.
In the E-step we are computing exactly the expected value for $\log \Pr[X,Z|\theta]$.
So what is this value, really? Observe that
$$\begin{align*}
\log \Pr[X,Z|\theta] &= \sum_{i=1}^5 \log\sum_{C\in \{A,B\}}\Pr[X_i, Z_i=C| \theta]\\
&=\sum_{i=1}^5 \log\sum_{C\in \{A,B\}} \Pr[Z_i=C | X_i, \theta] \cdot \frac{\Pr[X_i, Z_i=C| \theta]}{\Pr[Z_i=C | X_i, \theta]}\\
&\geq \sum_{i=1}^5 \sum_{C\in \{A,B\}} \Pr[Z_i=C | X_i, \theta] \cdot \log\frac{\Pr[X_i, Z_i=C| \theta]}{\Pr[Z_i=C | X_i, \theta]}.
\end{align*}$$
The reason is that we have 5 experiments to account for, and we don't know what coin
was used in each. The inequality is due to $\log$ being concave and applying Jensen's inequality. The reason we need that lower bound is that we cannot directly compute the arg max to the original equation. However we can compute it for the final lower bound.

Now what is $\Pr[Z_i=C|X_i,\theta]$? It is the probability
that we see coin $C$ given experiment $X_i$ and $\theta$. Using conditional probabilities
we have, $$\Pr[Z_i=C| X_i, \theta] = \frac{\Pr[X_i, Z_i = C|\theta]}{\Pr[X_i|\theta]}.$$

While we've made some progress, we're not done with the model just yet.
What is the probability that a given coin flipped the sequence $X_i$?
Letting $h_i = \#\text{heads in } X_i$
$$\Pr[X_i, Z_i = C| \theta] =
\frac{1}{2} \cdot \theta_C^{h_i} (1 - \theta_C)^{10 - h_i},\ \text{ for } \ C \in \{A, B\}.$$
Now $\Pr[X_i|\theta]$ is clearly just the probability under both possibilities of $Z_i=A$ or $Z_i=B$.
Since $\Pr[Z_i = A] = \Pr[Z_i = B] = 1/2$ we have,
$$\Pr[X_i|\theta] = 1/2 \cdot (\Pr[X_i |Z_i = A, \theta] + \Pr[X_i |Z_i = B, \theta]).$$

E-Step

Okay... that wasn't so fun but we can start doing some EM work now. The EM algorithm
begins by making some random guess for $\theta$. In this example we have $\theta^0 = (0.6,0.5)$.
We compute
$$\Pr[Z_1=A|X_1,\theta] = \frac{1/2 \cdot (0.6^5 \cdot 0.4^5)}{1/2 \cdot ((0.6^5 \cdot 0.4^5) + (0.5^5 \cdot 0.5^5))} \approx 0.45.$$
This value lines up with what is in the paper. Now we can compute the expected number of heads
in $X_1 = (H,T,T,T,H,H,T,H,T,H)$ from coin $A$,
$$\E[\# \text{heads by coin }A | X_1, \theta] = h_1 \cdot \Pr[Z_1=A|X_1,\theta] = 5 \cdot 0.45 \approx 2.2.$$
Doing the same thing for coin $B$ we get,
$$\E[\# \text{heads by coin }B | X_1, \theta] = h_1 \cdot \Pr[Z_1=B|X_1,\theta] = 5 \cdot 0.55 \approx 2.8.$$
We can compute the same for the number of tails by substituting $h_1$ for $10 - h_1$.
This continues for all other values of $X_i$ and $h_i$ $1 \leq i \leq 5$.
Thanks to linearity of expectation we can figure out
$$\E[\#\text{heads by coin } A|X ,\theta] = \sum_{i=1}^5 \E[\# \text{heads by coin }A | X_i, \theta]$$

M-Step

With our expected values in hand, now comes the M step where we want to maximize
$\theta$ given our expected values. This is done by simple normalization!
$$\theta_A^1 = \frac{E[\#\text{heads over } X \text{ by coin } A|X ,\theta]}{E[\#\text{heads and tails over } X \text{ by coin } A|X ,\theta]} = \frac{21.3}{21.3 + 9.6} \approx 0.71.$$
Likewise for $B$. This process begins again with the E-Step and $\theta^1$ and continues until the values
for $\theta$ converge (or to some alloweable threshold). In this example we have 10 iterations
and $\hat{\theta} = \theta^{10} = (0.8, 0.52)$. In each iteration the value of
$\Pr[X,Z|\theta]$ increases, due to the better estimate of $\theta$.

Now in this case the model was fairly simplistic. Things can get much more complicated
pretty quickly, however the EM algorithm will always converge, and will always produce
a maxmimum likelihood estimator $\hat{\theta}$. It may be a local estimator, but to
get around this we can just restart the EM process with a different initialization. We
can do this a constant amount of times and retain the best results (i.e., those with the
highest final likelihood).


Write down a DFA for the regular expression (000* + 111*)* and explain why it cannot have lesser number of states

You state two questions.

(1) You are convinced that all the strings decribed by the RegEx are accepted by the DFA. In order to conclude equality you want to know the converse. Is every string accepted by the DFA also described by the RegEx? To do this, try to argue that every string accepted by the DFA consists of "blocks" of each time at least two the same letter. This is not very dificult: the states of the DFA here "count" symbols $0$ and $1$.

(2) In the title of the question you ask whether the number of states is minimal. This can be done by arguing the no states can be merged. This can be shown by giving for each pair of states a string that "distinguishes" the states: states $p$ and $q$ are distinguished if there is a string $w$ such that $w$ from one of $p$ and $q$ reaches an accepting state, while it does not reach an accepting state from the other.
Here this can be done by looking at most one letter ahead: can be reach an accepting state by $\lambda$, $0$ or $1$? For each of the six staes the answers are different.


Get term type during evaluation using Hindley-Milner type system

Hashing of terms to types sounds like a hack to me (or possibly premature optimization and a hell created by stateful programming). During type inference you should tag every subterm with its computed type. Then during evaluation typeof simply projects the type.

The hell is in the deatils, of course. Here are some initial thoughts about how this would go (I did not actually implement this, but if I did, I would start from Poly in PLZoo).

We define the following datatypes:

a datatype ty of polymoprhic types
a datatype preterm of raw terms (the parser gives you these)
a datatype term of tyepchecked terms (type inference converts preterms to these)
a datatype value of values

Maybe like this, using OCaml syntax:

(* the result of parsing is a preterm *)
type preterm =
  | PreType
  | PreNumeral of int
  | PreTypeof of preterm
  | PreVar of string
  | PreLet of string * preterm * preterm
  | PreApp of preterm * preterm
  | PreLambda of string * preterm

type ty =
  | Type (* the type of all types *)
  | Number
  | Parameter of int
  | Arrow of ty * ty

(* after type inference every term is tagged with its type *)
type term = term' * ty
and term' =
  | Type
  | Numeral of int
  | Typeof of term
  | Var of int (* using de Bruijn indices *)
  | Let of term * term (* using de Bruijn indices *)
  | App of term * term
  | Lambda of term (* using de Bruijn indices *)

(* a typing context *)
type ctx = ty list

(* a runtime environment *)
type env = value list

(* values are explicitly tagged with their types *)
and value = value' * ty
and value' =
  | ValType of ty
  | ValNumeral of int
  | ValLambda of env * term

The parser gives us a preterm. Then we define

infer : ctx -> preterm -> term

and an evaluator

eval : env -> term -> value

The evaluator now has an easy time evaluating typeof e as

let rec eval env = function
  ...
  | Typeof e ->
    let (_, t) = eval env e in
      (ValType t, Type)
  ...

Let us work through your example

let _typeof = (λ x . typeof x) in _typeof 123

First, infer would find out that _typeof has type α -> Type. In the application _typeof 123 it would try to match (a fresh instance of) α against the type Number and would succeed with setting α = Number. It would then conclude that the type of _typeof 123 is Type.

Second, when eval gets to evaluation of _typeof 123 it actually sees something like

(App ((Var 0, Arrow (Parameter 0, Type)), (Numeral 123, Number)), Type)

which is an application of bound variable 0 to the numeral 123, together with typing information: the bound variable 0 has type Arrow (Parameter 0, Type) which corresponds to α -> Type, the numeral has type Number, and the entire expression has type Type. The evaluator first evaluates

(Var 0, Arrow (Parameter 0, Type))

which involves looking up the 0-th variable in the environment. It gets back a pair ((env', e), Arrow (Parameter 0, Type)) where (env', e) is a closure representing λ x . typeof x. Then it evaluates the argument and gets (ValNumeral 123, Number). It remains to evaluate e applied to (ValNumeral 123, Number) which is done the usual way with a recursive call to eval in env' extended with (ValNumeral 123, Number). Here e is going to be something like

(Typeof (Var 0, Parameter 0), Type)

which corresponds to the expression typeof x, except that x is replaced by de Bruijn index 0 and is tagged to have "any type". Now we need to pay attention (here is where you have a mistake that gives you α instead of Number): we first evaluate (Var 0, Parameter 0) by looking up the 0-th elemenent of (ValNumeral 123, Number) :: env', so we get (ValNumeral 123, Number). Now we evaluate Typeof by taking the second component, which is Number. It would be wrong to evaluate Typeof by simply returning Parameter 0, we actually have to evaluate its argument and then take the type of that). The final value therefore is

(Type Number, Type)

as expected.


this seems to be known as the "Lowest Common Ancestor" problem of graphs. see eg

Faster algorithms for ﬁnding lowest common ancestors
in directed acyclic graphs Czumaj et al
LCA Queries in Directed Acyclic Graphs Kowaluk, Lingas
Lowest Common Ancestors in Trees and Directed Acyclic Graphs Bender et al
algorithm to find LCA in DAG, so.se


Show the problem of a machine visiting infinitely many tape cells on some input is undecidable

Based on my comments, I might as well make this an answer, and let the community decide whether it's right or not.

Suppose you could decide whether a TM visits an infinite number of cells on an input. Here's how to solve the Halting problem given this information:

Halts(TM, input)
1. if the TM visits an infinite number of cells for the input then return false
2. configurations = {}
3. while(true)
4.     configurations.add(non-blank tape area, TM head position, state)
5.     let the TM execute one step
6.     if state is halt accept or halt reject, return true
7.     if configurations.contains(non-blank tape area, TM head position, state) then return false
8. loop

This works because, if the TM doesn't visit an infinite number of cells, it visits some finite number of cells, $n$. The number of distinct configurations is therefore $|\Sigma|^n \times n \times |Q|$, and configurations.size() will never be bigger than this. By the pigeonhole principle, we must satisfy at least condition #7 in a finite number of moves. If none of the reached configurations enters a halting state, we never will; so we have to halt before we see the same configuration twice.


Elimination rule for the equality type aka J axiom

A complete understanding of what J was actually saying and why has only come fairly recently.  This blog post discusses it.  While thinking in terms of homotopy and continuous functions provides a lot of intuition and connects to a very rich area of mathematics, I'm going to try to keep the discussion below at the logical level.

Let's say you axiomatized equality types directly (these are groupoid operations and laws):
$$\frac{\Gamma\vdash x:A}{\Gamma\vdash \mathbf{refl}_x : x=_A x} \qquad \frac{\Gamma, x:A, y:A\vdash p : x=_A y}{\Gamma, x:A, y:A\vdash p^{-1} : y =_A x} \qquad \frac{\Gamma, x:A, y:A\vdash p : x=_A y \quad \Gamma,y:A, z:A\vdash q : y=_A z}{\Gamma, x:A, y:A, z:A\vdash p\cdot q : x =_A z}$$
$$(p^{-1})^{-1} \equiv p \qquad p\cdot p^{-1} \equiv \mathbf{refl} \qquad (p\cdot q)^{-1} \equiv q^{-1}\cdot p^{-1} \\ \mathbf{refl} \cdot p \equiv p \equiv p \cdot \mathbf{refl} \qquad (p \cdot q) \cdot r \equiv p \cdot (q \cdot r)$$
We have substitution which is functorial.
$$\frac{\Gamma, z : A\vdash F(z) : \mathbb{U}\qquad\Gamma,x:A,y:A\vdash p : x=_A y}{\Gamma, x:A,y:A\vdash \text{subst}(F,p) : F(x) \to F(y)}$$
$$\text{subst}(F,\mathbf{refl}) = \text{id} \quad \text{subst}(F,p\cdot q) = \text{subst}(F,q)\circ\text{subst}(F,p)\\\text{subst}(\lambda x.c=_A x,p)(q) = q\cdot p$$
Finally, we would have congruence rules for everything, saying everything respects this equality.  Here is one of the most important congruences.
$$\frac{\Gamma, x:A, y:A\vdash p : x=_Ay \quad \Gamma,z:A\vdash B(z) : \mathbb{U}}{\Gamma, x:A, y:A, b : B(x)\vdash \text{lift}_B(b,p) : \langle x,b\rangle =_{\Sigma x:A.B(x)}\langle y,\text{subst}(B,p)(b)\rangle}$$

Now let's consider a special case of substitution.
$$\frac{\Gamma\vdash c:A \quad \Gamma,t:\Sigma x\!:\!A.c=_Ax\vdash C(t):\mathbb{U} \quad \Gamma\vdash b : C(\langle c,\mathbf{refl}_c\rangle)}{\Gamma,y:A,p:c=_Ay\vdash\text{subst}(C,\text{lift}_{\lambda z.c = z}(\mathbf{refl}_c,p))(b) : C(\langle y,p\rangle)}$$

This is J.  We can use currying to get the nicer looking form:

$$\frac{\Gamma\vdash c:A \quad \Gamma, y:A, p : c=_A y \vdash C(y,p): \mathbb{U}  \quad \Gamma\vdash b : C(c,\mathbf{refl}_c)}{\Gamma, y:A,p : c=_A y\vdash J_{A,c}(C,b,y , p) : C(y,p)}$$

Of course, if we start with J we can rederive all the other structure I defined.

Now if we have $p : x =_A y$ and $q : y =_A y'$ then $\text{lift}_{\lambda z.x=z}(p, q) : \langle y,p\rangle = \langle y',p\cdot q\rangle$.  So if we have $\langle y', p' \rangle$, there's no way to get to it from $\langle y,p\rangle$ via a pre-selected $q$ in general unless $p \cdot q = p'$. (From the homotopy perspective, $p \cdot q = p'$ says we can fill in the triangle with edges $p$, $q$, and $p'$.)  To make it more blunt, set $p = \mathbf{refl}_x$ (and $y=x$) and we get $q = p'$ being the required equality which is not true in general (because a value of type $x =_A y'$ can represent an arbitrary equivalence and there's nothing saying two equivalences have to be the same, or, equivalently, because we know groupoids can be non-trivial). The point of this is to demonstrate that things can be equal in more than one way, i.e. one value of $y = y'$ is not as good as another in general.

A key thing to understand is that J says the type $\Sigma y\!:\!A.x=_Ay$ is inductively defined, and says little about the type $x=_Ay$ for fixed $x$ and $y$.  One way to see this, and why J is the way it is, is to look at what congruence at equality types with matching endpoints looks like.  We have the following rule (ignoring the proof term, it's expressible with $\text{subst}$ or J):
$$\frac{\Gamma, x:A\vdash p : x=_Ax}{\Gamma, x:A, q : x =_A x\vdash \_ : q =_{x=_Ax} p \cdot q \cdot p^{-1}}$$  With $\text{lift}_{\lambda z.x=z}$ we have the option of doing $\text{lift}_{\lambda z.x=z}(p, p^{-1}\cdot p') : \langle y,p\rangle = \langle y',p'\rangle$ so every point was equivalent to every other point (though not necessarily trivially).  With both endpoints matched, we don't have the flexibility of choosing the equalities to first cancel out the input equality and then performing an arbitrary equality.

While J carefully respects the non-trivial groupoid structure of equality types, in typical dependently typed languages there's no way to actually define a non-trivial element of an equality type.  At this point you hit a fork in the road.  One route is to add Axiom K which says that the groupoid is actually trivial which makes many proofs much simpler.  The other route is to add axioms that allow you to articulate the non-trivial groupoid structure.  The most dramatic instance of this is the Univalence Axiom which leads to Homotopy Type Theory.


This already exists, but might not be what you are looking for.

While this might not be a problem for your application, notice that this is a more general problem than the (already NP-hard) bin packing problem, so for a large amount of crates finding the optimal solution will be hard.

On the other hand, for a small enough number of crates, brute force might be sufficient. For example, you could round all dimensions to multiples of 10cm and look at the trucks in terms of 10x10 tiles that crates can occupy, giving you a finite (hopefully small enough) number of potential solutions.


Are programming languages ultimately procedural?

I imagine that by "procedural" you mean languages whose statements refer to changes of state in one ore more objects, but these references are implicit, not explicit (they follow a fixed pattern, for instance, the state change made by the execution of a statement is delivered to the next, resembling a procedure).

You may be referring to the fact that our computers, at a low level of abstraction, are usually state machines - so to speak - so all programming languages would have to be procedural languages disguised as something else.

This has happened for technical and economical reasons, it's not a theoretical imperative. It doesn't have to be that way. Inside your head there is a computational device that isn't like that, and we've been experimenting with all kinds of different models for low level implementation of general-purpose computers for decades. It is not unlikely that, at some point, one of these alternative models becomes commercially viable.


denotional semantic for while - fixed points

Your proposed alternate definition is no good.  It tries to define $[[\text{while b do S}]]$ in terms of $[[\text{while b do S}]]$.  That's a circular definition: you can't define something in terms of itself.

"FIX" typically refers to the least fixpoint, and is a way of avoiding circularity.  See your textbook for background on fixpoints and the precise definition of the "FIX" operator.


Prove that A* is the smallest reflexive and transitive set containing A

Hint: Try the usual approach to show set inclusion! That is, pick $w \in A^*$ and show that $w \in B$.

Next hint:

   Apply transitivity of $B$ repeatedly.

More elaborately:

   If $w \in A^*$ then either $w = \varepsilon \in B$ or there are $w_1, \dots, w_k \in A \subseteq B$ with $w = w_1 \cdot \dots \cdot w_k$. Now, because $BB \subseteq B$ we have $w_2' = w_1 w_2 \in B$. For the same reason, $w_2' w_3 \in B$. And so on. Perform induction for the general proof.


Proof of $f(n) + ο(f(n)) = \Theta(f(n))$

Obviously, $f(n)+o(f(n))=\Omega(f(n))$ (clearly, I'm assuming all functions being positive), so you need only to prove that $f(n)+o(f(n))=O(f(n))$. But a function in $o(f(n))$ is definitevely smaller than $f(n)$, so for sufficient large $n$ you have $f(n)+o(f(n))\leq 2f(n)=O(f(n))$.
Actually, in the same way you can easily prove also this stronger claim: $f(n)+O(f(n))=\Theta(f(n))$.

If $h(n)=o(f(n))$, then $\lim_{n\to+\infty} \frac{h(n)}{f(n)}=0$, so there exists $n_0$ such that for all $n\geq n_0$ you have $h(n)\leq f(n)$ (actually, we can prove a stronger statemen, namely that for all $\varepsilon>0$, we have $h(n)< f(n)$, but here we not need it). This means that for all $n\geq n_0$ you also have $f(n)+h(n)\leq 2f(n)$, and then $f(n)+h(n)=O(f(n))$.

If you don't want to explicitely assume positiveness of the functions involved; I suggest to use limits (I like limits).
Remember that $f(n)=O(g(n))$ means
$$
\limsup_{n\to+\infty} \frac{|f(n)|}{g(n)}<+\infty
$$
while
$f(n)=\Omega(g(n))$ means
$$
\liminf_{n\to+\infty} \frac{|f(n)|}{g(n)}>0
$$
(use $|g(n)|$ instead of $g(n)$ if you want to take into account also negative functions). Notice that I'm not assuming that $\lim_{n\to+\infty} \frac{f(n)}{g(n)}$ exists, indeed $\liminf$ and $\limsup$ are used to deal with this case.
Now, as above, let $h(n)$ be an $o(f(n))$, e.g. $\lim_{n\to+\infty} \frac{h(n)}{f(n)}=0$.
Finally
$$
\limsup_{n\to+\infty} \frac{|f(n)+h(n)|}{|f(n)|}<\limsup_{n\to+\infty} \frac{|f(n)|+|h(n)|}{|f(n)|}=\limsup_{n\to+\infty}\left( 1+\frac{|h(n)|}{|f(n)|}\right)=1<\infty
$$
while
$$
\liminf_{n\to+\infty} \frac{|f(n)+h(n)|}{|f(n)|}=\liminf_{n\to+\infty} |f(n)|\cdot\frac{\left|1+\frac{|h(n)|}{|f(n)|}\right|}{|f(n)|}\geq 1>0.
$$
Also observe that in the first limit, we only need $\limsup_{n\to+\infty} \frac{|h(n)|}{|f(n)|}$ to be finite, so $h(n)$ can be also a $O(f(n))$.


Stack inspection is necessary because programs on the JVM and CLR have default access to dangerous operations, so something must be done to prevent disasters. For example an untrusted program can reference an I/O library and call it:

using IO;
...
IO.DeleteFile("/home/foo/bla");

So on each dangerous operation made, we need to check whether it is allowed. With stack inspection it is generally complicated to understand who gets access to what. It also makes optimizations such as inlining and tail calls difficult.

A superior mechanism is to not give each program automatic access to dangerous operations in the first place. In this model there is no way to import an IO library. The only way to get access to an IO library is if somebody else gave it to you. This is called capability security. An introduction can be found here.

Instead, we would write the previous program like this:

Main(IOLibrary IO){
  IO.DeleteFile("/home/foo/bla");
}

The IO library is a parameter to the entry point of the program, and this is called a capability (because it gives use some capability, in this case to do IO). To be able to run this program, we must have access to an IO capability ourselves, and run the program by calling Main(ourIOlibrary). If we are running an untrusted program, we simply do not pass our IO library to it, since it might use that library to delete our files. In some cases we want to give an untrusted program limited access to the filesystem. In that case we create a wrapper around our own IO library that only allows access to a certain directory, and pass that one to the untrusted program instead of the full IO library

So if we need an IO capability to invoke a program that needs an IO capability, that also means that whatever invoked our program needed to have access to an IO capability to be able to give it to us. So where did its IO capability come from? Well, eventually there is a point where the human operating the computer invoked a program. This human has access to all the system capabilities, so he was able to pass the IO capability on. If this human does not trust the program he is running, then he simply will not pass his IO capability to it.

You can probably easily imagine other kinds of capabilities: internet access, access to draw stuff on your screen, etc. For example a secure browser plugin system might give a graphics capability to an untrusted plugin that only allows it to paint graphics in a predefined rectangle on the page.


Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete

Given $G = (V,E)$, define $\tilde{G} = (\tilde{V},\tilde{E})$ by adding vertices $i^+$ and $i^-$ to $\tilde{V}$ for each $i\in V$ and edges $i^-j^+$ and $i^+j^-$ for each edge $ij\in E$.

It's not too hard to check that if $|V|$ is odd, $G$ has a Hamiltonian cycle if and only if $\tilde{G}$ is.  If $|V|$ is even, just add one new vertex of degree 2 with neighbors that have an edge between them.

So far, we've seen that Hamiltonian Cycle in bipartite graphs is hard.  To reduce this to Hamiltonian Path, just continue in the way you normally would to reduce Hamiltonian Cycle to Hamiltonian Path.


How can I implement a data structure which calculates the number of nested intervals in sub-linear time?

Expanding on Dmitry's comment, you can maintain a balanced tree with the left endpoints of the intervals as the keys, and at each node store a balanced tree with the right endpoints as keys, and at each node of each of those trees store a count of intervals.
This requires $O(n\log n)$ space. Lookups are $O(\log^2 n)$. Insertions are tricky because when rebalancing the outer tree you have to rebuild the inner trees, but I think it can be made amortized polylog(n) if you rebalance sufficiently rarely, using a scapegoat tree for example.
If you know that the endpoints will belong to a set of size $k$, and you don't mind factors of $\log k$ in the insertion and lookup times, then you could use a radix tree for the outer tree and avoid the rebalancing logic.


Algorithm complexity similar to Selection Sort

You have to count. Intuition is necessary, but you must calculate.

$$ 1+2+\cdots+N-1 = N(N-1)/2 \in \mathcal{O}(N^2)$$ by Gaussian summation rules.

In asymptotic notation, the constants are removed. For example.

$\mathcal{O}(N/k) = \mathcal{O}(N)$ as long as $k$ is a constant.


Changing preference in Gale-Shapley algorithm?

The property your wish to prove is known as strategy proofness: Is it possible for an agent to report a preference $P'$ such that it gets matched to a strictly better result w.r.t. its true preference $P$ than reporting truthfully?

Note that while the GS algorithm is strategy proof for the men, it is not for the women: they can use misrepresenting the preference to their advantage, as you can see with a simple example. In fact, there exists no stable matching mechanism that is strategy proof for all agents.

The proof of strategy proofness for men in the GS matching algorithm is, although it seems an obvious statement, rather involved. The clearest presentation I've been able to find is in the paper Machiavelli and the Gale-Shapely algorithm by Dubins and Freedman. In this paper, after proving strategy proofness, the authors proceed to prove the even stronger property of coalition strategy proofness:

  (17) THEOREM Suppose several students collude in a Gale-Shapley algorithm, each using a false
  rank ordering. They cannot all get better universities. "Better" is relative to each student's true rank
  ordering, and indicates strict inequality.

If you want a simple proof of strategy proofness of some matching mechanism, you can look at the Serial Dictatorship mechanism (also known under the perhaps less ominous name of Deferred Acceptance (DA) with single tie-breaks).

This is perhaps the simplest matching mechanism for the case with one-sides preferences and can relatively simply be shown to be both Pareto efficient and strategy proof.


Add edges to undirected graph to make connected and minimize longest path

Clearly, the number of added edges is one less than the number of connected components in the graph, since we can decrease this number by one by adding an edge and we seek the minimum number of added edges.

The trick is to add the edges between central vertices of the connected components. A central vertex of a connected  component is a vertex that has minimum distance to the farthest vertex to this vertex in the component (we call this distance the eccentricity). So it is a vertex that minimises the eccentricity.

Here goes the algorithm. In each step we find the connected components of the graph and we handle them as different graphs say $G_1, \dots, G_l$. Note that the task is to add $l-1$ edges between these graphs in a way that makes them connected. Each time we add an edge we will combine two graphs and decrease $l$ by one until it gets to the value 1.

After we found the connected component we find a central vertex in each of them (central vertices might not be unique but we can choose any of them). We keep for each component a central vertex and the value of its eccentricity. Now in each step we combine to graphs, we distinct two cases.
- The minimum eccentricities are equal, then any of the two central vertices can be chosen as a central for the new graph and the new eccentricity is the previous one plus one. (Try to prove the correctness and optimality of this statement).
- The minimum eccentricities differ. Keep the central with the greater eccentricitiy. Its eccentricity does not change. (Also try to prove this).

The eccentricity of each component can be built using a BFS from each vertex in total quadratic time in the size of the input graph. Each iteration can be implemented in constant ime (for example keep a stack of pairs (central, eccentricity) and in each step pop two elements, unify them and push thr new pair back to thr stack. each step decreases the size of the stack by one and hence we end after $l-1$ steps.

The correctness of the previous two cases implies the correctness of the algorithm and that it does not matter in which order you process the components. Hence we get a total quadratic running time. There are some heuristics to improve the running time of computing central vertices if connected components (which is the only quadratic factor in our algorithm and gence the bottleneck) including pruned BFS. However, as far as I know, this is the best achievable asymptotic running time.


Proof that bin packing is strongly NP-complete?

Such a proof is outlined in Garey and Johnson, 'Strong' NP-Completeness Results: Motivation, Examples, and Implications, mentioned in the Wikipedia article. The proof is by a straightforward reduction from 3-PARTITION. The problem 3-PARTITION one is given $3n$ numbers, and the task is to decide whether they can be split into triples of equal sum. There is a straightforward reduction from 3-PARTITION to BIN-PACKING: if the sum of the numbers is $nB$, ask whether the $3n$ numbers can be packed into $n$ bins of size $B$.

The strong NP-completeness of 3-PARTITION was proved in a different paper of Garey and Johnson, Complexity results for multiprocessor scheduling under resource constraints. The proof is quite long, ultimately a reduction from 3DM (3-dimensional matching), but going through many intermediate steps.


Hint: Following up on Hendrik Jan's hint, here is another way to view this language:
$$
\{ x1y@1z : x,y \in \{0,1\}^*, z \in \{1\}^*, |x| = |z| \}.
$$


Undecidability and Unrecognizability of Language with two Turing Machines

You are going to want to use a many-one reduction for this problem. Note that $ii \implies i$ so it is sufficient to prove statement $ii$. We know that the complement to the halting problem $$ \bar{H}=\{\langle M, w \rangle \mid M \text{ does not halt on }w\}$$ is not recursively enumerable. We can reduce $\bar{H}$ to $Language1$
$S$ = "
$\quad$on input $\langle M,w \rangle$
$\quad$construct $M_1$ = "
$\quad\quad$on input $x$
$\quad\quad$if $x\neq $<$M_2$>, $Reject$
$\quad\quad$run $M$ on $w$
$\quad\quad$$Accept$ "
$\quad$construct $M_2$ = "
$\quad\quad$on input $x$
$\quad\quad$if $x\neq $<$M_1$>, $Reject$
$\quad\quad$run $M$ on $w$
$\quad\quad$$Accept$ "
$\quad$Output $\langle M_1, M_2 \rangle$ "
Notice that if $M$ does not halt on $w$, then $M_1$ accepts string $\langle M_2 \rangle$ and $M_2$ accepts string $\langle M_1 \rangle$, and both reject all other strings, that is $L(M_1)=\{\langle M_2 \rangle \}$ and $L(M_2) = \{\langle M_1 \rangle \}$. On the other hand if $M$ does halt on $w$, $L(M_1)=L(M_2)=\emptyset$. Then $\bar{H} \leq_m Language1$, since $\bar{H}$ is not recursively enumerable, neither is $Language1$.


Detailed step of Dijkstra's algorithm performance analysis

Since makequeue takes at most as long as $|V|$ insert operations, we get a total of $|V|$ deletemin and $|V | + |E|$ insert/decreasekey operations.
  First of of all, why one algorithm has TWO kinds of insert operations, if they are the same kind, then where can we learn more about what decreasekey actually does?

No, there is only one kind of insert operation. We got

$|V|$ deletemin operations.
a total of at most $|V|+|E|$ operations, where each operation is either an insert operation or a decreasekey operation. We count these two kinds of operations together because it takes the same asymptotic time to do either one of them, $O(\log |V|)$.  More specifically. we have

|V| insert operations during makequeue.
at most |E| decreasekey operations as each edge may or may not lead to a decreasekey operation.


Computing morphic word produced by uniform morphism

Denote $f^{(\infty)}(a)$ by $w$. Thus $f(w) = w$. Let $w_0,w_1,w_2,\ldots \in \{a,b,c\}$ be the individual symbols of $w$. The crucial observation is that if $n = 3m + r$ for $r \in \{0,1,2\}$ then
$$
w_n = f(w_m)_r.
$$
Indeed, since $w = f(w)$, we have
$$
w_0 w_1 w_2 w_3 w_4 w_5 w_6 w_7 w_8 \ldots = f(w_0 w_1 w_2 \ldots) = f(w_0) f(w_1) f(w_2) \ldots,
$$
from which this formula can be recovered.
This gives a very simple recursive formula for computing $w_n$:
$$
w_n = f(w_{\lfloor n/3 \rfloor})_{n \bmod 3},
$$
with base case $w_0 = a$.
A similar approach works for every morphic word produced by a uniform morphism (one in which $|f(\sigma)|$ is the same for all $\sigma \in \Sigma$).


Mean number of edges between two equal partitions

Your thinking is correct. To verify your claim you can check this lecture notes on the probabilistic method by Matousek and Vondrak. More specifically check the proof of Theorem 3.3.1 stating that any graph with $m$ edges contains a bipartite subgraph with $\frac{m}{2}$ edges.


Assume 256 symbols, each with probability 1/256. The Huffman code words will be all 256 possible eight-bit sequences, and there is no synchronisation at all.

To find if a Huffman code is self-synchronising:

Let S = {}
For each code c:
    For 1 ≤ m < length (c)
        Let s be the last m bits of c
        As long as s has a code c' as prefix
            Remove prefix c' from s
        If s is not empty and not in S
            Add s to S.

Loop:
    If S is empty the the code is self-synchronising.
    Let T = {}
    For each s' in S, and code c:
        Let s be s' concatenated with c
        As long as s has a code c' as prefix
            Remove prefix c' from s
        If s is not empty and not in T
            Add s to T.
    If T = S then the code is not self-synchronising
    Let S = T and loop.


What is the simplest way to understand Turing machines and the busy beaver problem?

From quora.com:

A Turing machine is a computer (PC, Mac, iPhone or Conway's Game of Life - pick whichever is most familiar) with unlimited storage (memory, hard disk, doesn't matter). Assume you can program the computer in some programming language, and that you're interested in what it can and cannot compute. "Compute" means "read some input, do stuff, write some output".
This is not the usual description of a Turing machine, of course, but for the study of computability - which is mostly what Turing machines are good for - it's completely equivalent.
The Busy Beaver problem is this: suppose I challenge you to write a computer program (again, pick your favorite programming language) whose sole purpose in life is to print a long string of dots and then stop. If the length of your program is limited to k characters, how long of a string can you make?
It should be clear that this question has an answer, for any choice of programming language and any given limit k. After all, there are only finitely many possible computer programs of length, say, 10,000 characters in, say, C++; some of them print finite strings of dots, and of all the ones that do, we can pick the one (or ones) that print the absolutely longest string.
If you happen to know something about programming, it should also be clear that as soon as k becomes reasonably large to accommodate some non-trivial programs, the answer will be incredibly humungous. It's quite easy, for example, to write a computer program that prints 100^{100} dots and then stops, and in most reasonable programming languages this shouldn't take up more than a few hundred characters to implement. With some cleverness you can get much higher numbers.
The Busy Beaver function is a table that lists, for any given k, the answer to this problem - the length of the longest string of dots you can achieve with a program of length k that prints such a string and stops. This function, or table, is pretty wild: it can be shown that it grows faster than any computable function. Therefore it is itself non-computable. It's unknowable in a pretty strong sense.
If you don't know what "programming language" means or what programming languages can do, you can just imagine that you're giving a friend a notebook with very precise instructions such that, if your friend follows those instructions, she will end up writing a great number of dots on a very large piece of paper. You needn't assume the friend is a math genius, but you may assume she's immortal, very patient and capable of following simple instructions like "write the number 6 on the yellow sticky note" or "read the number on the orange sticky note, erase it and replace it with the next counting number". It's fine if she can't count beyond a billion herself: with enough sticky notes we can help her overcome that.


Is there any algorithm for 3SAT problem that is fast and relatively easy to implement?

If you're determined not to use the standard deterministic algorithm, the usual alternative is what's known as local search or stochastic search.  The basic idea is that you start with a random bit pattern as a variable assignment, observe what's wrong with it in terms of unsatisfied clauses and try to improve it by flipping one or more variable assignments.  Observe how this new assignment fails, try to improve it, and repeat.
Local search typically outperforms deterministic search for satisfiable random SAT instances, but performs poorly on more structured instances.  It also offers no way to prove unsatisfiability unless some proof system is layered atop it.
There are various local search algorithms on offer, from Uwe Schöning's scheme to PPSZ and its variants.  None of them outperform DPLL-based solvers on all instances.


What is the difference between a microoperation, microinstruction and control word?

In traditional horizontal microcode,

a micro-operation is the most basic operation achievable by a processor;
a micro-instruction is a set of micro-operations which are executable simultaneously;
control words are the bit patterns used to encode the micro-instructions.

Micro-operation is also used in current pipelined processors where an instruction is decomposed in a few (included zero) micro-operations or even a few instructions merged in one micro-operation which are then processed independently.

Control word is a far more general term and can refer to any bit patterns used to control any circuit.  Its use for the encoding of micro-instructions come from the fact that horizontal micro-code is usually lightly encoded if at all, and thus fields in the encoding control directly parts of the processor.  From there it went to be used for the encoding of any kind of micro-instructions.  BTW, the area where the micro-program is stored is often called the control store.


Solving the recurrence $T(n) = n^{3/4}(^{1/4})+ n $

You can just expand it:
$$
\begin{align*}
T(n) &= n + n^{3/4} T(n^{1/4}) \\ &=
n + n^{3/4}\cdot [n^{1/4}+ n^{3/16}\cdot T(n^{1/16})]  \\ &=
n + n + n^{3/4} \cdot n^{3/16} T(n^{1/16}) \\ &=
n + n + n + n^{3/4} \cdot n^{3/16} \cdot n^{3/64} T(n^{1/64}) \\ &=
\cdots
\end{align*}
$$
We see that $T(n) = C(n) n$, where $C(n)$ is the number of times we need to apply $n \mapsto n^{1/4}$ until the answer drops below some constant.

I'll let you figure out $C(n)$, and so complete this exercise.


Reasoning about resources: "resource logics"?

Do you mean a resource-aware logic?
If so, yes, there's linear logic [Girard, 1987] (as was already noted in the comments). It has had a big influence on the study of concurrency and implicit computational complexity. You might be interested in the latter, where reasoning is focused on the efficiency of programs.

What do you mean exactly by "actor models"?
If you mean concurrency, please have a look at: What is the Curry-Howard analogue for linear logics?
If you mean identifying who/what uses/implements resources at the level of propositions, we explored an extension of linear logic for that [Carbone et al., 2016], but mainly for the notion of communication protocol (who performs which communications). Useful inspiration might also come from hybrid logics that support notions of "worlds", like this one: https://www.cs.cmu.edu/~rwh/theses/reed.pdf


Argument in proving that function is not polynomial time in bit length of input seems faulty

You should measure the length of the output in the same way you measure the length of the input.

For example, when computing the identity function $f(m) = m$, an input $m$ has input length $n = \Theta(\log m)$ and output length also $n$, which is polynomial in $n$.

The factorial function, in contrast, has much too long output length. Indeed, if the input is $n$, then by Stirling's formula, the length of the output is $\Theta(n\log n)$, which is exponential in the input length $\Theta(\log n)$.


Can every linear grammar be converted to Greibach form?

The more general answer is:

Blum and Koch showed a polynomial time transformation such that any context-free grammar can be converted to Greibach form.

Since a linear grammar is a special case of Context-free grammar, the answer is yes.

A simpler transformation:

Any rule $X \rightarrow a_1 a_2 \cdot a_k Y$ you transform them in $k$ rules:

$X\rightarrow a_1 X_1Y$.
$\cdots$
$X_{i-1}\rightarrow a_{i}X_i$
$X_{k-1}\rightarrow a_{k}Y$

Any rule $X \rightarrow a Y b$ should be transformed in two rules

$X \rightarrow a Y Y_1$.
$Y_1 \rightarrow b$

where the capital letters belong to $V$ and the small letters to the alphabet (terminals).


Most probable value of randomized procedure output

The question sounds a bit difficult. I was able to calculate the expectation of $x$ when $m = 2$. The most probable value of $x$ should be very close to its expectation. Perhaps this will give you some ideas.

The idea is to construct an infinite Markov chain whose states are $|W[0]-W[1]|$, and whose transitions are labeled by whether $\max(W(0),W(1))$ increases or not. Here are the transitions (explained below):

At state 0, we transition to state 1 w.p. 1, increasing the maximum.
At state $n > 0$, we transition to state $n-1$ w.p. 1/4; to state $n+1$ w.p. 1/2, increasing the maximum; and to state 1 w.p. 1/4, increasing the maximum.

The first case is trivial.
For the second case, consider the array $a+n,a$. There are four options, each occurring w.p. 1/4:

When $x=y=0$, the new array is $a+n+1,a$ (the maximum increases).
When $x=y=1$, the new array is $a+n,a+1$ (the maximum doesn't increase).
When $x=0,y=1$, the new array is $a+n,a+n+1$ (the maximum increases).
When $x=1,y=0$, the new array is $a+n+1,a$ (the maximum increases).

The next step is to calculate the stationary probability (it is easy to check that the chain is ergodic). Denoting it by $p_n$, we have

$p_0 = \frac{p_1}{4}$.
$p_1 = p_0 + \frac{p_1 + \cdots}{4} + \frac{p_2}{4} = p_0 + \frac{1-p_0}{4} + \frac{p_2}{4}$.
$p_n = \frac{p_{n-1}}{2} + \frac{p_{n+1}}{4}$ for $n \geq 2$.

The sequence $p_1,p_2,\ldots$ satisfies the recurrence
$$
p_n = 4p_{n-1} - 2p_{n-2}.
$$
The roots of $x^2 - 4x + 2$ are $2 \pm \sqrt{2}$, and since the series $\sum_{n \geq 1} p_n$ converges, we must have $p_n = C (2-\sqrt{2})^n$. In particular, $p_2 = (2-\sqrt{2})p_1$. Substituting this in the formulas for $p_0,p_1$, we can calculate
$$
p_0 = \frac{4\sqrt{2}-5}{7}, \qquad
p_1 = \frac{16\sqrt{2}-20}{7}.
$$
Notice now that when at state $n>0$, the maximum increases with probability 3/4, and when at state 0, it always increases. Hence the probability that it increases at the stationarity is
$$
\frac{3}{4} + \frac{p_0}{4} = \frac{4+\sqrt{2}}{7}.
$$
Denoting by $X_n$ the expected value of $x$ when $m=2$ and $n$ is given, we deduce that
$$
\lim_{n\to\infty} \frac{\mathbb{E}[X_n]}{n} = \frac{4+\sqrt{2}}{7} \approx 0.773459.
$$
This is corroborated by experiment. When $n=1000$, the empirical average of $10^6$ trials is $0.773733$ (the expected error is of order $10^{-3}$).

The expected gap between $\max(W)$ and $\min(W)$ is
$$
\sum_{n=1}^\infty np_n =
p_1 \sum_{n=1}^\infty n(2-\sqrt{2})^{n-1} =
\frac{p_1}{(\sqrt{2}-1)^2} = \frac{4+8\sqrt{2}}{7} \approx 2.18767.
$$
In particular, the limits of $\mathbb{E}[\max(W)]/n$ and $\mathbb{E}[\min(W)]/n$ (after $n$ steps) are the same.

In a similar way, it should be possible to compute $\lim_{n\to\infty} \mathbb{E}[\max(W)]/n$ for any fixed $m$, though I don't know if there is a nice formula for this limit in general.

Other limits could also be interesting. For example, one could ask what happens if $n$ is fixed and $m\to\infty$ (this should be easy to answer), or when $n=m \to \infty$ (seems more difficult).

Calculating the exact expectation for given $n,m$ is possible using the same ideas, but there isn't probably any nice formula.


Can a Minimum Possible Efficiency be proven?

There are certainly ways to show that certain algorithms must take a certain amount of time or certain data structures require a certain amount of space. One common way is to use information theory.

An unsorted array is a permutation of the sorted array. There are $n!$ possible permutations. The job of sorting, in an information theoretic sense, is to discover precisely which permutation it is.

To transmit a number between $1$ and $m$ requires transmitting $\log_2 m$ bits of information. To transmit a permutation of $n$ elements, therefore, requires $\log_2 n!$ bits of information. By Stirling's approximation, this turns out to be $n \log_2 n + O(\hbox{low order})$ bits.

A binary comparison operation discovers one bit of information. It follows that any sorting algorithm which only uses a binary comparison operation must perform at least $n \log_2 n + o(n \log n)$ comparisons. If we assume that a comparison takes a constant amount of time, that means that the sort must take at least $\Omega(n \log n)$ time.

A radix sort could beat this by discovering more than one bit of information per query.

A similar argument shows that binary search is optimal. You are trying to find a number between $1$ and $n$, which means discovering $\log_2 n$ bits of information. If your query operation returns one bit of information, you need at least $\log_2 n$ queries to find an element.

It's a similar story with space usage. Suppose that you need to store a permutation in memory. By an identical argument, this requires at least $n \log_2 n + o(n \log n)$ bits of storage. Since you need $\log_2 n$ bits to store an integer between $1$ and $n$, you essentially can't do any better than storing $n$ integers.


How to interpret plot of cost function in gradient descend algorithm?

I don't know what to make out of the rising and falling in the cost in the beginning. Is that something that we can expect? If so, why? Shouldn't the gradient descend algorithm decrease the cost after every step?

Gradient descent only minimizes the cost if the learning rate is low enough. Also, in practice most of the time you don't use gradient descent on the whole dataset, but on a mini-batch. This means you don't get an guarantee that the global cost is falling for a single step.

An analogy which is often used is that of a landscape with hills. The landscape is your cost. Each point in the landscape is a specific configuration of weights. The gradient shows in the direction of steepest descent. That might be a rabbit hole on a hill, but it might also be downwards to the valley. Now, imagine it shows to the rabbit hole. Instead of going down the rabbit hole, you make a bigger step and so you go up the hill. But then you are on a different position. For your next step, you come away from the rabbit hole and get towards a better (local) minimum.

As always when it comes to training, I would like to point out the awesome gifs by Alec Redford: Gifs 1, and Gifs 2


Understanding the definition of endless sets

Defining endless sets, you probably assume that you don't have the Axiom of regularity.

A set is endless when it doesn't contain only simple elements, it has to contain an other set among his elements, and this other set has again to contain an other set and this third set has to contain an other set, etc..

For example, a set verifying $M = \{M\}$ is endless because it contains an other set ($M$) which contains an other set (still $M$) which contains an other set ($M$), etc.. You can take $X=X_0= X_1= ... = M$ as infinite family.

A counter example is $M = \{42\}$; $M$ doesn't contain any set. $M= \{42, \{12\}\}$ is also a counter example because $M$ contains a set ($\{12\}$) but this set doesn't contain any set.


Any set of strings is a (formal) language. That's probably not what you mean since you have quite specific restrictions in mind.

Many standardised string formates are defined by regular expressions what makes the respective sets of strings they admit regular languages. Note that some examples are actually finite languages (IPs).

In then end, it depends on what you mean by "well defined". Any set of strings is well-defined. Anything more will depend on the kind of specification you give, and then the language will (sort of) inherit the specification's "name".


The complement is the set of all strings over alphabet $\{a,b,c\}$ that are not of the form $a^i b^i c^i$ for some $i\geq 0$.  That includes all strings $a^ib^jc^k$ where $i\neq j$, $i\neq k$ and/or $j\neq k$, as you say, but also some other strings.  Mouse-over the box below for a hint.

   For example, $bacbabc$ is in the complement.


Identifying a starting point for maximum coverage

It sounds like you want to select a set of 50 lists whose union contains as many elements as possible.  This is the maximum coverage problem, which is NP-complete, but there are standard techniques that can be used to get decent-quality solutions (there is an approximation algorithm using a greedy algorithm, and a formulation as ILP).


What is the solution of $T(n, m) = T(n, m-1) + T(n-1, m) + c$?

The function $f(n,m) = \binom{n+m}{n}$ satisfies the recurrence
$$
f(n,m) = f(n-1,m) + f(n,m-1),
$$
with base cases $f(n,0) = f(0,m) = 1$. This already gives you the solution when $c = 0$, assuming that the base cases are $f(n,0) = f(0,m) = 1$.

One function which satisfies the recurrence, though (in general) not the base case, is $g(n,m) = -c$:
$$ g(n,m) = g(n,m-1) + g(n-1,m) + c. $$
This gives the solution when $c = -1$.

Finally, note that any function of the form $\alpha f(n,m) + g(n,m)$ is also a solution of the recurrence. Since
$$
\alpha f(n,0) + g(n,0) = \alpha f(0,m) + g(0,m) = \alpha - c,
$$
we see that
$$
T(n,m) = (c + 1) f(n,m) + g(n,m) = (c+1) \binom{n+m}{n} - c.
$$


A procedure for Topological sort, proof for its correctness

b. As operation $1$ cannot be performed, $H$ must be a DAG. Consider a topological sort of $H$. As $3$ cannot be performed, if $u$ precedes $v$ in the topological sort, there is a path from $u$ to $v$. Start at the initial vertex in the sort and keep moving forward until we find a vertex which has more than one outgoing edges (if each vertex has only one outgoing, then it is a line graph). Let $u$ have edges to $v$ and $w$ and let $v$ precede $w$. Then there is path from $v$ to $w$, which gives a path from $u$ to $w$ that doesn't include $u \rightarrow w$, a contradiction as operation $2$ can be performed here.

c. As deleting edges will not alter DAG property, we only need to check $3$. A cycle is formed only when we add an edge $u \rightarrow v$, when there was a path from $v$ to $u$ already. As $3$ doesn't add such edges, DAG is maintained.

d. Let $H$ be obtained from $G$ by a single operation. We show that any topological sort of $H$ is also valid for $G$ (note that the converse need not be true). For this we need to show that if there was a path from $u$ to $v$ in $G$, then there is path from $u$ to $v$ in $H$ too. Some path can be broken only when we are removing edges. So clearly operation $3$ will not cause any problem here. Also, in $2$, we are only removing those edges $u \rightarrow v$ where there is already a path from $u$ to $v$. So for any path from $w$ to $z$, containing that edge, we can just replace that edge by the path from $u$ to $v$, maintaining a path from $w$ to $z$ in $H$. And $G$ is DAG, so $1$ never happens.

e. First observe how each of $s$, $e$ and $p$ change with each operation. With operation $1$, $s$ reduces by at least $1$, $e$ reduces by $1$ and $p$ can decrease by close to $n^2$ (almost all paths might be broken). With $2$, $s$ might reduce by $1$ (not necessary though), $e$ reduces by $1$ and $p$ is unchanged. With $3$, $s$ doesn't change, $e$ increases by $1$ and $p$ increases by at least $1$. Notice that as we are going towards line graph, we are trying to reduce number of edges ($e$), remove cycles ($s$) while increasing $p$. So in $as+bp+de+c$, we expect $a$ and $d$ to be positive and $b$ to be negative. The worst case changes in $s,e,p$ for each operation are

$$
\begin{array}{cccc}
 & s & e & p \\
1. & -1 & -1 & -n^2 \\
2. & 0 & -1 & 0 \\
3. & 0 & 1 & 1
\end{array}
$$

As $s$ never increases, we can make $a$ as large as we want. As we can scale $a,b,d$ by a constant, lets keep $d=1$. With these observations we can get one possible set of values for $a,b,d$ as $2n^2$, $-2$ and $1$ respectively. And pick $c$ as negative of the value at line graph.


Hoare's monitor - what happens after a "signal"

Here's the picture of a Hoare-style monitor from wikipedia user Theodore.norvell:

The circles are threads, the rooms off to the sides are various queues.  Think of the monitor as being protected by a mutex.  Only one thread gets the mutex at a time.  Once a thread has the mutex it keeps the mutex until it releases the mutex by (1) waiting (in which case it goes to sleep on a condition variable), (2) signalling (in which case it goes into the queue labeled s in the picture or (3) exiting the monitor completely.  The scheduling algorithm is given in the wikipedia article.  At any point in time the relative priorities to get into the monitor are: (1) the single thread that was most recently signalled, (2) threads in queue s (usually s is FIFO), (3) threads in queue e (the entry queue).
If the consumer sends the signal before the producer waits then the producer will be stuck forever.  This is sometimes called "the missed wakeup problem."  It is avoided by recognizing that you should really be waiting for some condition to become true (e.g., "the queue is no longer full"), not waiting for some condition variable to get signaled.  When the producer is in the monitor (has acquired the mutex) it only waits on the condition variable if it sees that the condition is not currently true.  The consumer signals the condition variable every time the condition (state) "queue is full" changes to "queue is not full", whether there is anyone waiting on the condition variable or not.
If there is a context switch the mutex of the monitor will not be released.


Minimum hamming distance of multiple binary words

You are correct.

Here's what's going on.  There are two subtly different questions here.  The Stack Overflow question is asking: "given a set of bitvectors that form a Hamming code, how do I find the minimum distance?".  In contrast, it sounds like you might be asking "given an arbitrary set of bitvectors, how do I find the minimum distance?".  Those aren't the same question.  Unsurprisingly, they have two different answers.

The answer on Stack Overflow you're referring to isn't 100% clear, but I suspect it is making the following claim: if you have a set of bitvectors that form a Hamming code, then the minimum distance can be obtained by computing the Hamming weight of the xor of all the bitvectors.  I don't know whether that claim is true, but let's suppose it is.  That still doesn't help you with (what I think is) your question, because in your problem you have an arbitrary set of bitvectors -- they might not form a Hamming code.

It is easy to find counterexamples to demonstrate that the claim doesn't hold in general, for an arbitrary set of bitvectors.  For instance, your example is a perfectly good disproof of that.

There are techniques for finding the minimum distance of a set of arbitrary bitvectors (at least, there are heuristics), but hopefully this is enough to answer the question you asked.


Let us interpret for i:=1 to n inclusively. That is, i will take values $1, 2, \cdots, n$.

Let us check how many operations are done in pesky(n).

r:=0: 1 assignment.

for i:=1 to n do:
$n$ assignments of i.

for j:=1 to i do:
$\sum_{i=1}^ni=\dfrac{n(n+1)}2$ assignments of j.

for k:= j to i + j do: $\Sigma_{i=1}^n\Sigma_{j=1}^i(i+1)=\dfrac{n(n+1)(n+2)}3$ assignments of k.

r := r + 1:
$\Sigma_{i=1}^n\Sigma_{j=1}^i(i+1)=\dfrac{n(n+1)(n+2)}3$ additions by 1.  $\dfrac{n(n+1)(n+2)}3$ assignments of $r$.

There are $1+n+\dfrac{n(n+1)}2+\dfrac{n(n+1)(n+2)}3\cdot2=\dfrac{(n+1)(n+2)(4n+3)}6$ assignments in total.

There are $\dfrac{n(n+1)(n+2)}3$ additions in total.

If we treat the computation cost of one assignment as that of one addition, we have $\dfrac{(n+1)(n+2)(4n+3)}6+\dfrac{n(n+1)(n+2)}3=\dfrac{n(n+1)(2n+1)}2$ operations.

That is answer. Note that it is a fixed number given $n$. That is, there is no distinction of best-case, worse-case or average-case.

Or is it? If we ignore over many important details, yes. However, let us take a close look. Does for i:=1 to n do involve assignment only? Mostly like not. We have to produce 1, 2, 3, $\cdots$, n in the first place. If we produce them by addition by 1, we have $n-1$ more additions. How do we make sure we will stop when $i$ reach $n$? Probably we have to compare i with n for about $n$ times. Comparison takes time of course. We should include that cost. Wait, there is more. It is unreasonable to expect that $n$ is in the right position to be compared with $i$; We have to fetch $n$ from somewhere so that we can compare it with $i$. Now, we are not even sure how to describe that fetching and its computational cost. There are, in fact, many more important details that could be taken into consideration.

You might be wondering now. Do we have an answer or not? Yes and no.

Yes, we have an answer, assuming some assumptions. I will not be surprised that your instructor might come up with a different number of operations under a different set of assumptions, though.
No, the answer cannot stand up to scrutiny in many situations. That is one of the reasons why we use the big $O$-notations. We can say the computation cost is $\Theta(n^3)$ under a set of very general assumptions (a.k.a. model of computation).

By the way, if you check what I had written before, you will notice and understand that I have been rather careful, saying that I am only computing how many times the innermost iteration are executed. In general, the asymptotic time complexity of a nested loop is determined by the product of that number with the average cost of one innermost iteration.

Here is a similar exercise for you to practice.

Exercise. Express the best-time complexity of the following function in terms of $n$ instead of in big $O$-notation. Only the operation r := r + 1 is counted.

function pesky2(n)
  r := 0
  for i := 1 to n do
    for j := 1 to i do
      for k := 1 to j do
        r := r + 1

  return r


Runtime bounds on algorithms of NP complete problems assuming P≠NP

My interpretation of the question is that is asks about the possibilities in relativized worlds. Suppose that in some relativized world, $P \neq NP$. Can we deduce anything non-trivial about the time complexity of NP-complete problems? The Baker–Gill–Solovay argument shows that we can "force" some NP problem to require exponential time, so the upper bound given in the question is essentially optimal.

Regarding the lower bound, we sketch below a proof that relative to some oracle, $NP = \mathrm{TIME}(2^{O(\log^2 n)})$. Assuming that the sketched proof is correct, we can also apply it to functions smaller than $2^{O(\log^2 n)}$, and this shows that the lower bound given in the question is also essentially tight.

Proof sketch. We construct two oracles $O_1,O_2$: the first behaves like a $\mathrm{TIME}(2^{O(\log^2 n)})$-complete problem, and the second implements the Baker–Gill–Solovay diagonalization. It is straightforward to pack both oracles into a single oracle.

The oracle $O_1$ consists of all pairs $\langle M, x \rangle$ such that $M$ is an oracle Turing machine that accepts $x$ in running time $2^{2^{\sqrt{\log |x|}}}$ when given access to the oracles $O_1,O_2$ restricted to inputs of length at most $2^{\sqrt{\log |x|}}$. (This is not a circular definition.)

The oracle $O_2$ is defined in the same way that the oracle is defined in Baker–Gill–Solovay: for each clocked oracle Turing machine $M$ running in time $T = 2^{o(\log^2 n)}$, we find some input length $n$ which is "untouched", run $M$ on $1^n$ for $T$ steps, and for each query to $O_2$ of size $n$, we mark that this input is not in $O_2$ (for other queries we also mark that the input is not there, unless we had already decided that it is in $O_2$). Queries to $O_1$ are handled similarly (as implicit queries to $O_1,O_2$ of smaller size, handled recursively); notice that such queries never mention strings of length $n$ in $O_2$, since $2^{\sqrt{\log T}} < n$. If the machine accepts, we mark all other strings of length $n$ in $O_2$ as missing, otherwise we pick some string of length $n$ and put it in $O_2$.

The class $P^{O_1,O_2}$ consists of all programs running in time $2^{2^{O(\sqrt{\log n})}}$, making queries to $O_1,O_2$ of size $2^{O(\sqrt{\log n})}$. The class $NP^{O_1,O_2}$ is of the form $x \mapsto \exists |y|<n^C \varphi(x,y)$, where $\varphi \in P^{O_1,O_2}$, and so it is contained in the class of all programs running in time $2^{n^C}$ and making oracle queries of size
$2^{O(\sqrt{\log n})}$. The latter is contained in $\mathrm{TIME}(2^{\log^2 n^C})^{O_1,O_2}$, since we can use $O_1$ to decide it. This shows that $NP^{O_1,O_2} \subseteq \mathrm{TIME}(2^{O(\log^2 n)})^{O_1,O_2}$.

For the other direction, let $L$ be the language which consists of $1^n$ for each $n$ such that $O_2$ contains some string of length $n$. By construction of $O_2$, $L \notin \mathrm{TIME}(2^{o(\log^2 n)})^{O_1,O_2}$, while clearly $L \in NP^{O_1,O_2}$. This shows that $NP^{O_1,O_2} = \mathrm{TIME}(2^{O(\log^2 n)})^{O_1,O_2}$.


Proof by restriction: when is it valid to restrict to a special case?

Think about the set of all possible instances of DHC. A subset of these instances are those where, for every directed edge $(u, v)$, there is always a matching directed edge $(v, u)$. (In general, this doesn't have to be the case, but it CAN be the case, which is why this is a valid restriction.)

Now think about the set of all possible instances of SubsetSum. For each such instance, you're supposed to answer with a set of 0/1-valued $x_i$. By your first definition, there are NO valid answers that include a real number in the $x_i$. So, when you suddenly allow real-valued solutions in the second version of SubsetSum, you're relaxing the problem, not restricting it. (You're giving yourself more leeway by allowing more possible solutions.)