Does a pushdown automata exists for the following language? I have came across a question stating that language $L = a^n b^n c^{2n}$ is not a context free language and hence, no PDA can be constructed for it. But what I am wondering is that, if I add another alphabetical comparison to the above language as

$L_1= a^n b^n c^{2n} d^n$
$L_2= a^n b^{2n} c^n d^{2n}$

And a mixture of above will lead to cfg. Because now we have two comparison so not only we can push the symbol but with the help of other symbol we can pop it so as to empty the stack implies to acceptance of the strings.
my question is I do not know that whether my assertion to the modification of the language is right or wrong so please if you can tell me where iam wrong or right it would be helpful.
One more thing if iam right, then please show the  cfg production to derive them as I can make PDA for them( if iam right) but finding hard to assign production the accepts the above cgl language ( if its then)
Thanks

Your languages are still not context-free.

A string homomorphism is a function $f\colon \Sigma \to \Sigma^*$ that replaces each character in a string with a (possibly empty) string over the same alphabet.  For a string $w=w_1\dots w_\ell$, we define $f(w)= f(w_1)\cdots f(w_\ell)$.  Context-free languages are closed under string homomorphisms.  That is, if a language $X$ is context free, so is the language $\{f(w)\mid w\in X\}$ for any string homomorphism $f$.

So, suppose that either of your languages were context-free, and consider the homomorphism defined by $f(a)=a$, $f(b)=b$, $f(c)=c$, $f(d)=\varepsilon$. We have $f(L_1)=\{a^nb^nc^{2n}\mid n\geq 0\}$ and $f(L_2) = \{a^nb^{2n}c^n\mid n\geq 0\}$. Neither of these is context free, which contradicts the assumption that $L_1$ and $L_2$ are context-free.

Also "a mixture" is not a well-defined context-free operation. In general, you should be suspicious of arguments where the main step is just some hand-wave along the lines of "And, yeah, then surely we can just combine them." If it's easy to explain how to "just combine them", then the argument can easily state that; if it's not easy to explain how, then it certainly needs to be explained!


Multiple of Hamiltonian Cycles I'm currently confused whether a graph should contain strictly one distinct Hamiltonian Cycle. (given that [1,2,3,4,1] and [2,3,4,1,2] are the same).

I was wondering if, by definition, there can be multiple distinct Hamiltonian Cycles in a graph? something like H1 = [1,2,3,1] and H2 = [6,7,8,6]

can someone kindly confirm?

(addt'l sources and references would really be great so I can dive in deeper)

Cheers!

Recall a Hamiltonian cycle visits each vertex of a graph exactly once. Thus, the cycles H1 and H2 in your second example can't be Hamiltonian cycles in the same graph.

In your first example, the two cycles could be distinct Hamiltonian cycles in e.g. the complete graph on 4 vertices. That is to say, there can definitely be multiple Hamiltonian cycles in a graph.

If you care about naming conventions, you can call two cycles that don't share any vertices vertex-disjoint cycles. Similarly, two cycles can be edge-disjoint if they don't share edges.


Why is the transform in Schönhage–Strassen's multiplication algorithm cheap? The Schönhage–Strassen multiplication algorithm works by turning multiplications of size $N$ into many multiplications of size $lg(N)$ with a number-theoretic transform, and recursing. At least I think that's what it does because there's some other cleverness and I really don't understand it well enough to summarize accurately. It finishes in $O(N \cdot  lg(N) \cdot lg(lg(N)))$ time.

A number-theoretic transform is exactly like a Discrete Fourier Transform, except it's done in the finite field $F_{2^N+1}$ of integers modulo $2^N+1$. This makes the operations a lot cheaper, since the Fourier transform has a lot of multiplying by roots of unity, and $F_{2^N+1}$'s roots of unity are all powers of 2 so we can just shift! Also, integers are a lot easier to work with than floating point complex numbers.

Anyways, the thing that confuses me is that $F_{2^N+1}$ is very large. If I give you a random element from $F_{2^N+1}$, it takes $O(N)$ bits to specify it. So adding two elements should take $O(N)$ time. And the DFT does a lot of adding.

Schönhage–Strassen splits the input into $\frac{N}{lg(N)}$ groups with $lg(N)$ bits. These groups are the values of $F_{2^N+1}$ that it will transform. Each pass of the DFT will have $O(\frac{N}{lg(N)})$ additions/subtractions, and there are $O(lg(\frac{N}{lg(N)}))$ passes. So based on addition taking $O(N)$ time it seems like the cost of all those additions should be $O(N \frac{N}{lg(N)} lg(\frac{N}{lg(N)}))$, which is asymptotically the same as $O(N^2)$.

We can do a bit better than that... because the values start out so small, the additions are quite sparse. The first pass' additions really only cost $O(lg(N))$ each, and the second pass' cost $2^1 O(lg(N))$ each, and the i'th pass' cost $O(min(N, 2^i \cdot lg(N)))$ each, but that still all totals out to a terrible $\frac{N^2}{lg(N)}$.

How is Schönhage–Strassen making the additions cheap? How much do they cost overall?

Is it because the algorithm actually uses $F_{N+1}$ (with $N$ guaranteed to be a power of 2)? There's enough stacked $2^{2^{n}}$ and german in the paper that I'm really not sure. On the other hand, I don't think that guarantees enough roots of unity for things to work out.

According to the Wikipedia article, at each step the length of the integers is reduced from $N$ to (roughly) $\sqrt{N}$, and there are (roughly) $\sqrt{N}$ of them, and so the additions only cost $O(N)$. There is a detailed analysis of the running time in the final paragraph of the linked section, copied here in case it changes:

In the recursive step, the observation is used that:

Each element of the input vectors has at most $N/2^k$ bits;
The product of any two input vector elements has at most $2N/2^k$ bits;
Each element of the convolution is the sum of at most $2^k$ such products, and so cannot exceed $2N/2^k + k$ bits.

Here $N$ is current input length and $k = \Theta(\sqrt{N})$. Arithmetic is done modulo $2^n+1$, where $n$ is some multiple of $2^k$ which is larger than $2N/2^k + k$; note that $n = \Theta(\sqrt{N})$.


Finding constants C and k for big-O of fraction of polynomials I am a teaching assistant on a course for computer science students where we recently talked about big-O notation. For this course I would like to teach the students a general method for  finding the constants $C$ and $k$ in the definition of big-O
$$
|f(x)| \leq C|g(x)|, x > k,
$$
when the function $f(x)$ is a fraction of polynomials.

I have tried to concoct my own method, but I am unsure of its correctness. I was inspired by the easy method of finding $C$ and $k$ for a polynomial where for example we can show that $x^3+2x+3$ is $O(x^3)$ by
$$
x^3+2x+3 \leq x^3+2x^3+3x^3 = 6x^3
$$
to find $C = 6$ and $k = 1$.

Now, for a fraction of polynomials I am unsure what to do with the denominator. My attempt at a general method is as follows. I would like to show that $\frac{x^4+x^2x1}{x^3+1}$ is $O(x)$. First I divide by the highest term in the denominator to get a $1$ in the denominator:
$$
\frac{(x^4+x^2+1)/x^3}{(x^3+1)/x^3} = \frac{x+\frac{1}{x}+\frac{1}{x^2}}{1+\frac{1}{x^3}}
$$
Now I argue, somewhat analogously to the previous example, that the fractions in the numerator must be less than (when x > 0) x, and since a smaller denominator makes the expression smaller, setting all the terms in denominator except the $1$ to $0$, I obtain the inequality
$$
\frac{x+\frac{1}{x}+\frac{1}{x^2}}{1+\frac{1}{x^3}} \leq \frac{x+x+x}{1+0} = 3x
$$
and I find $C = 3$ and $k = 1$.

Now my question is, does this homebrewed method actually work or is it complete nonsense? And if it is nonsense, does anybody know of another general method for finding $C$ and $k$ in instances like this?

Note that I need to find the constants $C$ and $k$, not just show that a given function is big-O of some other function, and the students have had no course in calculus, so I can use no concepts from there, such as limits.

It works if the denominator doesn't have negative coefficients. Consider, however,
$$ \frac{x}{x-1}. $$
As $x$ tends to infinity, this is $O(1)$. However, your method would give
$$ \frac{x}{x-1} = \frac{1}{1-\tfrac{1}{x}} \leq \frac{1}{1-1} = \infty, $$
which is not very helpful. The problem is that when $x = 1$, the denominator is not positive. In this case it is zero, but for an example like
$$ \frac{x}{x-2} = \frac{1}{1-\tfrac{2}{x}} \leq \frac{1}{-1} = -1, $$
the inequality is in fact wrong.

Often when considering $O(f(x))$, we assume that $f(x)$ is always positive. But sometimes it isn't, and then the assumption that we're making is that $f(x)$ is eventually positive. This is not usually explained when big O notation is defined, but it's the reason behind the extra quantifier "for large enough $x$" which appears in the full definition of big O; this quantifier is only needed when $f(x)$ is not always positive but only eventually positive.

The way to fix the argument is now clear. If $f(x)$ is eventually positive, then take some $y$ such that $f(x) > 0$ for all $y \geq x$, and now apply the method. For example, if $f(x) = x/(x-1)$ then any $y > 1$ would do, say $y = 2$. In that case we have
$$ f(x) = \frac{1}{1-\tfrac{1}{x}} \leq \frac{1}{1-\frac{1}{2}} = 2 $$
for $x \geq 2$.

More generally, suppose that $f(x) = C p(x)/q(x)$, where $p,q$ are monic polynomials (leading coefficient is $1$) and are eventually positive, and $C > 0$. Then for all $\epsilon > 0$ there is $y$ such that for all $x \geq y$,
$$ (C-\epsilon) x^{\deg p - \deg q} < f(x) < (C+\epsilon) x^{\deg p - \deg q}. $$
(Exercise.)


Why is the initial state of Zobrist hashing random? When generating a board for Zobrist hashing, why are the initial elements random? How can you detect changes to elements later if the initial values are random?

The initial elements are chosen randomly to minimize hash collisions. You can think of the Zobrist hash as a random hash function $h$, mapping board positions to bit vectors of length $N$, chosen from some collection of hash functions. What we are trying to accomplish is this: given any choice of positions $p_1,\ldots,p_n$ arising in the program, we want that with high probability over the choice of $h$, $h(p_i) \neq h(p_j)$.

The Zobrist hash family is 3-wise independent: for any 3 distinct positions $p_1,p_2,p_3$, the hashes $h(p_1),h(p_2),h(p_3)$ are uniformly distributed over all triplets of binary vectors of length $N$. In particular, the probability that $h(p_i) = h(p_j)$ is $2^{-N}$ (we actually only need 2-wise independence for this), and so the expected number of collisions is $\binom{n}{2} 2^{-N}$, which is the same as the expected number of collisions for a completely random hash function.

The Zobrist hash function has an important advantage over a completely random hash function: it is easy to compute. Moreover, it is easy to update after a move of a single piece on the board. It is this last property which makes it especially attractive for hashing board positions.

By choosing the initial elements at random, we guarantee that whatever the board positions $p_1,\ldots,p_n$ are, the probability of collision is small (assuming that the positions are chosen independently of the hash function). There could also be some intelligent choice for the initial elements satisfying that, but it is not clear what this choice should be, and how to analyze it. On the other hand, a random choice succeeds with high probability, which is why we choose the Zobrist table randomly.


Shortest path that visits maximum number of strongly connected components Consider a directed graph. I need to find a path that visits maximum number of strongly connected components in that graph. If there are several such paths the desired path is the path that visits minimum number of nodes (shortest path).

I have created a DAG from the directed graph and performed a topological sort on it. Now I can easily find paths that passes maximum number of components by traversing the DAG, but I have problem finding the shortest one of them. Of course you can brute-force over all of these paths and find the shortest one of them but this is not acceptable because my graph has 1000 nodes.

For ease of writing, I'm going to say "component" instead of "strongly connected component."  This should cause no confusion, since it's the only kind of component we're interested in.

Let $G$ be your directed graph.  Let $H$ be the DAG made by contracting every component of $G$ to a single vertex. That is, the vertices of $H$ are the components of $G$ and there's an edge from $x$ to $y$ in $H$ if, and only if, there's an edge in $G$ from the component corresponding to $x$ from the one corresponding to $y$.  Write $h(C)$ for the vertex in $H$ that corresponds to the component $C$ in $G$.

Observe that any path in $G$ that visits the maximum possible number of components must correspond to a maximum-length path in $H$, which must run from some source to some sink.  So, we need to find the longest paths in $H$.  We can't just produce a list of them because there might be exponentially many.  So, instead, we assign a label $\ell(x)$ to every $x\in V(H)$ using the following procedure.

Topologically sort the vertices.
Set $\ell(x) = 0$ for each sink $x$.
Working back from the leaves in the topological ordering, set $\ell(x) = 1 + \max\,\{\ell(y_1), \dots, \ell(y_k)\}$ for each vertex $x$ with out-neighbours $y_1, \dots, y_k$.

Note that the topological ordering guarantees that we've already computed $\ell(y_i)$ for each out-neighbour $y_i$.  When the labelling is computed, it has the property that, for every vertex $x\in H$, $\ell(x)$ is the length of the longest path from $x$ to a sink in $H$.

Now, produce a graph $H'$ from $H$ as follows.

Delete every edge $(x,y)$ such that $\ell(x)\neq\ell(y)+1$.
Let $m = \max\,\{\ell(x)\mid x\text{ is a source in }H\}$ (this is the length of the longest path in $H$).
Iteratively delete every source $y$ with $\ell(y)<m$.

$H'$ contains exactly the vertices and edges of $H$ that appear in longest paths in $H$ (put another way, $H'$ is the union of all longest paths in $H$).  In particular, every path from a source to a sink in $H'$ has length exactly $m$, which is the greatest length of any path in $H$.

Now, produce a graph $G'$ from $G$ as follows.

Delete from $G$ any component $C$ such that $h(C)\notin H'$.
Delete from $G$ any edge from component $C_1$ to component $C_2$ if there is no edge $(h(C_1),h(C_2))$ in $H'$.

Finally, let $S\subseteq V(G')$ be the set of all vertices whose components are sources in $H'$ and let $T\subseteq V(G')$ be the vertices in components that are sinks in $H'$.  The $S$ $T$ paths in $G'$ are exactly the paths in $G$ that visit the maximum possible number of components. Use your favourite shortest path algorithm to find a shortest one.

Thanks to Bakuriu for suggesting topological sort instead of my ad-hoc algorithm.


Is IP masquerade and Network Address Port Translation(NAPT) the same? Is IP masquerade and Network Address Port Translation(NAPT) the same? I'm not sure whether it is the same thing or not but I realized the mechanism is almost the same where both IP masquerade and NAPT changes TCP/UDP port and many-to-one relation is allowed:multiple private addresses share one global IP address.
If it is different which part is IP masquerade and NAPT is different?

IP masquerade is the same as NAPT and the only difference is that when NAPT is used in Linux, it is called IP masquerade. The mechanism is the same, it's just the place where the technology is implemented is different.


Circuits and Closure Under Reductions Suppose that $A$ and $B$ are languages such that $A\leq_P B$ (many-to-one Karp reduction), and $B\in \mathbf{P/poly}$. How do we prove that $A\in\mathbf{P/poly}$?
Using similar ideas like Cook-Levin (or $P\subseteq \mathbf{P/poly}$), I can show that given $x\in\{0,1\}^n$, there exists a (easily computable) poly-sized circuit that can compute each bit of the reduction, say $R(x)$. The issue for me is that the size of $R(x)$ may depend on $x$ and not only $n$ (since we only require it to be bounded by $\mathrm{poly}(n)$). In such a case, it is not clear how to what input length circuit for the language $B$ to use.

If $A \leq_P B$ then since $P \subseteq P/\mathit{poly}$, also $A \leq_{P/\mathit{poly}} B$. This means that there is a function $f \in P/\mathit{poly}$ such that $x \in A \leftrightarrow f(x) \in B$. Since $f \in P/\mathit{poly}$, for every $n$ there is a polynomial size circuit $C$ that computes $f(x)$ for $x$ of length $n$. The circuit needs to have some mechanism for indicating the output length, which might depend on $x$.
Since $C$ has polynomial size, in particular, there are only polynomially many options for the output length, and so if $B \in P/\mathit{poly}$, these circuits can be connected to the outputs of $C$ in order to compute $A$.


Could a standardized ternary system be more efficient than the binary system? Could a standardized ternary (base-3) system be more efficient than the binary (base-2) system? Binary is efficient for processing using logic gates, but can be bulky when using for file storage or file transfer. I am interested in the feasibility of a ternary system both for file storage, file transfer, and computational processing.

The following three examples show an ASCII word converted to both binary and ternary, along with the length of the sequence:

ASCII Example 1: Hello

Binary: 0100100001100101011011000110110001101111 (40 characters)

Ternary: 210011101002200222 (18 characters)

ASCII Example 2: Test

Binary: 01010100011001010111001101110100 (32 characters)

Ternary: 220200002020100202 (18 characters)

ASCII Example 3: Cat

Binary: 010000110110000101110100 (24 characters)

Ternary: 22022100102101 (14 characters)

As denoted by the character count, the length of the ternary sequence can sometimes be less than half the length of the binary sequence. Having shorter sequences would be beneficial for file transfer, file storage, and computational processing speeds. On the surface this seems preferable, but perhaps there are disadvantages or implementation flaws which I am overlooking. The following contains additional observations (which may or may not be feasible), for implementation.

File Storage

Ternary would be highly beneficial for file storage but would require hardware changes. For example, manufacturers of flash memory storage devices such as flash drives or solid state drives would have to re-architect the transistors in order to store the representation of a 0, 1, or 2. If these transistors could maintain the same size dimensions as the current transistors that store the representation of a 0 or 1, the storage capacity has the potential to double.

File Transfer (Focus on wireless transmission)

File transfer speeds appear to have potential to increase with a ternary system. In the case of wireless transmissions, binary is generally preferred over analog due to its increased ability to maintain information integrity and is easier to distinguish when interference is present. The following diagram demonstrates this principle.

Image source: https://www.predig.com/whitepaper/reducing-signal-noise-practice

I imagine the implementation of ternary in wireless systems to appear like the following diagram (drawn quickly), having the peak and trough like a binary signal along with an ‘in-between’ to represent a 2. Having an ‘in-between’ might make the signal become less interference-tolerant than binary, which could be a disadvantage.

Thanks in advance for responses. Feel free to address unconsidered factors of why ternary may or may not be feasible and/or a beneficial alternative to the binary system.

EDIT: This question was flagged as a possible duplicate question. Keep in mind that an important aspect of this question is file transmission, which has been unaddressed in previous related ternary questions.

Whether this is more efficient depends on the physical properties of the medium, not on any fundamental principle of computer science.  And of course there's no reason to limit yourself to ternary systems; we can consider systems with $k$ levels, where $k$ is any integer with $k \ge 2$ (it doesn't have to be limited to $k=2$ or $k=3$).

For instance, Wifi apparently uses BSK (a binary system, $k=2$), QPSK (a quad-level system, $k=4$), 16-QAM (a 16-level system), or 64-QAM (a 64-level system).
Cable TV apparently uses 64-QAM and 256-QAM, which is a modulation scheme that uses $k=64$ or $k=256$ different levels.  Why?  Because this is more efficient than using a binary ($k=2$) system.  There are many other examples like this in the communications world.

On the other hand, digital circuits -- as typically used in a CPU -- seem to be most effective with two-level modulation (i.e., binary, $k=2$).  Why?  The physics are different.

So, yes, sometimes this is more efficient, and sometimes it is not.  It all depends on the specific properties of the hardware you're working with.  Those properties are a matter of electrical engineering and physics, rather than of computer science.

There's lots more on this subject at Ternary processing instead of Binary, Why Do Computers Use the Binary Number System (0,1)?, and Could computer architecture be reworked to support switching from binary to ternary, for example?, for starters.


If A is mapping reducible to B and A is recognizable, then is B recognizable too? I learned the proof for the theorem:
If A $\leq_m$ B and B is recognizable, then A is recognizable
and was provided with the theorem:
If A $\leq_m$ B and A is unrecognizable, then B is unrecognizable

So does this work both ways? i.e. does this also hold?

If A $\leq_m$ B and A is recognizable, then B is recognizable
If A $\leq_m$ B and B is unrecognizable, then A is unrecognizable

Answer for Corrected Question

Short answer, no.

You can think of reductions as "making problems harder" (somewhat inline with using $\leq$ as the base symbol for reductions of).

In this case we only have two levels of "hardness", a problem/language is either recognizable ("easy") or unrecognizable ("hard") (but this obviously extends to other degrees of computability and complexity).

So if $A \leq B$, and $B$ is "easy", $A$ must be "easy" too (because it's "less than" $B$). Contrapositively, if $A \leq B$ and $A$ is "hard, then $B$ must also be "hard" (because it's "greater than" $A$).

Using this intuition, it may be a bit easier to see why the latter two are wrong:

If $A \leq B$ and $A$ is "easy", this doesn't tell us much about $B$ (it could be "easy" or "hard").
Similarly, if $B$ is "hard", it doesn't tell us much about $A$.

Note that as with the first pair, the second are really the same statement, just logically inverted.

Old Answer, Just Here for Posterity

I think you may have misread something. The second (provided) theorem is not correct, it should be if $A \leq_{m} B$ and $A$ is unrecognizable, then $B$ is unrecognizable.

This is just the contrapositive of the first statement.

Following from this, the final two are mistaken.


Complexity of transposing matrices represented as list of row or column vectors Given [[1,4,7],[2,5,8],[3,6,9]] which is a list of the column vectors of matrix

|1, 2, 3|
|4, 5, 6|
|7, 8, 9|

is $ \Omega(n^2) $ a lower bound for transposing? Assume the matrix is not always square. I have to touch each element at least once, because going from 2 x 5 to 5 x 2 matrix for example, will mean going from a list of 5 lists to a list of 2 lists, so I can't really do any tricks with the array indices, right?

Is there a faster way to transpose matrices?

If the matrices are stored in the usual way, that is as long vectors, then the complexity is $\Theta(n^2)$. The reason is that if all the off-diagonal entries in the matrix are different, you will need to change all of them, and there are $n^2-n$ of them.


Which language is used to construct a type system? Typically, OCaml and Scala seem to be used for designing any programming languages tool. But what features offer them an edge over other languages.
A related question, is a type system for a language always written in the native language itself?

OCaml and Scala are popular choices for types systems, but they are by no means the only languages you can write a compiler, interpreter, typechecker, or type system in.
Type-checking involves traversing syntax trees representing terms and types. Languages with some form of algebraic data type make this easy, since these traversals can be defined using pattern-matching . In an object oriented language, these traversals have to be done using a Vistor pattern, which ends up using much more boilerplate. Languages like Haskell can use techniques like monads or  datatype-generic programming to abstract away even more of the boilerplate of these traversals.
Also, functional programming languages tend to be closer to the lambda calculus and the other formalizations of programming languages. Since programming language researchers are often the ones developing both these formalizations and the implementations, so it makes sense that they'll be more comfortable in languages like these.
It's worth mentioning that a some work has been put into developing other ways to declaratively specify type systems for languages. For example:

Turnstile is a Racket DSL that lets you develop type systems in a form that looks a lot like formal inference rules.
Spoofax is a toolkit for writing programming languages, that can generate a typechecker with IDE integration from a specification.

A related question, is a type system for a language always written in the native language itself?

Certainly not! It's popular for writers to implement a language in the language  itself, (often called "self hosting"). If you're writing a programming language, then there's a good chance that it's  been designed to solve problems that whoever was writing the language had. So whoever is designing the language probably finds it a pleasant language to use.
But for performance reasons, often languages are implemented lower-level languages like C or Rust. This is particularly important for interpreted languages: if you write your interpreted language in another interpreted language, then interpreting code involves running your interpreter in yet another interpreter, which is a lot of indirection that hurts performance.


Theory of message complexity analysis of distributed systems Inspired by this post, I thought it would be a good idea to ask an analogous question in the context of distributed systems -

While most of us are familiar with the notion of Time Complexity as a measure of efficiency of algorithms, In the world of distributed systems, another important measure of efficiency plays a preeminent role namely that of Message Complexity.

Specifically, when working in terms of the graph network model(i.e., algorithm instances executing on each node of a network pursuant of a network-level goal), it is the total number of bits of information that are cumulatively sent through each edge/connection of the system over the course of execution of the distributed system. My question is as follows:

What are the usual techniques applied to calculating/bounding the message complexity cost of distributed algorithms?
What is the generalised structure/theory behind these techniques?

S. Arora, B. Barak, Computational Complexity Modern Approach, Chapter 13 is a good introductory resource to this topic:

  Communication complexity concerns the following scenario. There are two players with unlimited computational power, each of whom holds an $n$ bit input, say $x$ and $y$. Neither knows the other’s input, and they wish to collaboratively compute $f(x, y)$ where the function $f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}$ is known to both. Furthermore, they had foreseen this situation (e.g., one of the parties could be a spacecraft and the other could be the base station on earth), so they had already — before they knew their inputs $x, y$ — agreed upon a protocol for communication. The cost of this protocol is the number of bits communicated by the players for the worst-case choice of inputs $x, y$.

This chapter also covers lower bound methods: the fooling set method, the tiling method, the rank method, the discrepancy method. It gives also a brief overview of other communication models: randomized protocols, nondeterministic protocols, average case protocols, and asymmetric communication. At the end of the chapter it provides detailed reference to papers relating this topic.


Is there a generalization of Huffman Coding to Arithmetic coding? In trying to understand the relationships between Huffman Coding, Arithmetic Coding, and Range Coding, I began to think of the shortcomings of Huffman coding to be related to the problem of fractional bit-packing.

That is, suppose you have 240 possible values for a symbol, and needed to encode this into bits, you would be stuck with 8 bits per symbol, even though you do not need a "full" 8, as 8 can express 256 possible values per symbol. A solution to this problem is something I've seen referred to as "fractional bit packing", where you are able "bitshift" by a non-power of two using multiplication. Just like multiplication of powers-of-two are shifting x * 2 == x << 1 and x * 4 == x << 2 and so on for all powers of two, so too you can "shift" with a non-power-of-2 by multiplying instead, and pack in fractional-bit-sized symbols.

The problem is similar with Huffman coding: you end up with codes that must be non-fractionally-bit-sized in length, and therefore it has this packing inefficiency. However, you can't just use the solution of fracitonal-bit-packing, because this solution assumes fixed sized symbols.

The question is, are there any papers or solutions to improve on huffman coding with a similar idea to fractional-bit-packing to achieve something similar to arithmetic coding? (or any results to the contrary).

Let's look at a slightly different way of thinking about Huffman coding.

Suppose you have an alphabet of three symbols, A, B, and C, with probabilities 0.5, 0.25, and 0.25. Because the probabilities are all inverse powers of two, this has a Huffman code which is optimal (i.e. it's identical to arithmetic coding). We will use the canonical code 0, 10, 11 for this example.

Suppose our state is a large integer, which we will call $s$. You can think of encoding as a function which takes the current state, and a symbol to encode, and returns the new state:

$$\begin{align*}
\hbox{encode}(s, A) &= 2s\\
\hbox{encode}(s, B) &= 4s + 2\\
\hbox{encode}(s, C) &= 4s + 3\\
\end{align*}$$

So let's start with the state 11 (which is 1011 in binary), encode the symbol B.  The new state is 46, which is 101110 in binary. As you can see, this is the "old" state with the sequence 10 added to the end. We have essentially "output" the bit sequence 10.

So far, so good.

Now think for a moment about how arithmetic coding works. If you put the probabilities over a common denominator, the symbol A actually represents the range $[\frac{0}{4},\frac{2}{4})$, the symbol B represents the range $[\frac{2}{4},\frac{3}{4})$ and the symbol C represents the range $[\frac{3}{4},\frac{4}{4})$.

Basically what we're doing here is multiplying everything by the common denominator. Imagine that the state was actually in base 4. Encoding a symbol B is really outputting the digit 2 in that base, and encoding a symbol C is outputting the digit 3 in that base.

However, symbol A is a little different, because it isn't a whole digit in base 4.

Instead, we can think of the alphabet as the set of symbols A_0, A_1, B, C, with equal probability. This, again, has an optimal Huffman code 00, 01, 10, 11. Or, again, we can think of this in base 4. To encode a symbol, we just do:

$$\begin{align*}
\hbox{encode}(s, A_0) &= 4s + 0\\
\hbox{encode}(s, A_1) &= 4s + 1\\
\hbox{encode}(s, B) &= 4s + 2\\
\hbox{encode}(s, C) &= 4s + 3
\end{align*}$$

So now it's clear how to encode symbols B and C, but to encode a symbol A, we have a choice. Which of $A_0$ and $A_1$ should we use?

Now here's the clever idea: we steal one bit of information from the state $s$:

$$s' = \left\lfloor \frac{s}{2} \right\rfloor$$
$$i = s \bmod 2$$

and then $\hbox{encode}(s', A_i)$.

Using our previous example, $s=11$, we find that $s'=5$ and $i=1$, and then $\hbox{encode}(5, A_1) = 4\times 5+1 = 21$. The new state is 10101 in binary.

Now this doesn't produce exactly the same bit output as Huffman coding, but it does generate an output which has the same length. And what I hope you can see is that this is also uniquely decodable. To decode a symbol, we take the remainder when divided by 4. If the value is 2 or 3, then the symbol is B or C respectively. If it's 0 or 1, then the symbol is A, and then we can put the bit of information back by multiplying the state by 2 and adding either 0 or 1.

The nice thing about this approach is that it extends naturally to fractional-bit encoding, when the numerator and/or denominator of the probabilities are not powers of two. Suppose we have two symbols, A and B, where the probability of A is $\frac{3}{5}$ and the probability of B is $\frac{2}{5}$. Then we can encode a symbol with:

$$\begin{align*}
\hbox{encode}(s, A_0) &= 5s + 0\\
\hbox{encode}(s, A_1) &= 5s + 1\\
\hbox{encode}(s, A_2) &= 5s + 2\\
\hbox{encode}(s, B_0) &= 5s + 3\\
\hbox{encode}(s, B_1) &= 5s + 4
\end{align*}$$

To encode the symbol A, we take $s' = \left\lfloor \frac{s}{3} \right\rfloor$ and $i = s \bmod 3$, and then $\hbox{encode}(s', A_i)$.

This is equivalent to arithmetic coding. It's actually a family of methods known as Asymmetric Numeral Systems, and was developed over the last few years by Jarek Duda. The meaning of the name should be obvious: to encode a symbol with probability $\frac{p}{q}$, you conceptually steal a base-p digit from the state, and then add a base-q digit. The asymmetry comes from interpreting the state as a numeral in two different bases.

The reason why it's a family of coding methods is that what we've seen here is impractical by itself; it needs some modifications to deal with the fact that you probably don't have infinite-precision integers to manipulate the state variable efficiently, and there are various ways that you can achieve this. Arithmetic coding, of course, has a similar issue with precision for its state.

Practical variants include rANS (the "r" means "ratio") and tANS ("table-driven").

ANS has a few interesting advantages over arithmetic coding, both practical and theoretical:

Unlike arithmetic coding, the "state" is a single word, rather than a pair of words.
Not only that, but an ANS encoder and its corresponding decoder have identical states and their operations are completely symmetric. This raises some interesting possibilities, such as that you can interleave different streams of encoded symbols and everything synchronises perfectly.
Practical implementations need, of course, to "output" information as you go, and not just collect it in a big integer to be written at the end. However, the size of the "output" can be configured in return for (usually modest) compression loss. So where arithmetic coders must output a bit at a time, ANS can output a byte or a nybble at a time. This gives you a direct tradeoff between speed and compression.
It appears to be about as fast on current-generation hardware as binary arithmetic coding, and hence competitive with Huffman coding. This makes it much faster than large-alphabet arithmetic coding and its variants (e.g. range coding).
It appears to be patent-free.

I don't think I'm ever going to do arithmetic coding again.


Counterexample for LTL - CTL equivalence I have to find an example of a model where the LTL-formula $F G p \wedge F q$ is valid and the CTL-formula $EF AG p \wedge AF q$ is not valid. I found this example, but I'm not completely sure whether it's correct:

Consider the following model: you have 3 states, $s_0,s_1,s_2$ with the transitions: $s_0\to s_0$, $s_0\to s_1$, $s_1\to s_2$ and $s_2\to s_2$ and the labels are $L(s_0)=\{p,q\}$, $L(s_1)=\emptyset$ and $L(s_2)=p$.

Then, every computation starts with $q$, so $Fq$ holds, and every infinite computation eventually gets stuck in $s_2$, or it is $s_0^\omega$, and both satisfy $FGp$, so the LTL formula holds.

However, it never holds that $AFq$, so the CTL formula does not hold.


floating point rounding (1/x)*x I'm trying to figure out what the smallest positive integer x such that the floating point expression round(round(1/x)*x) is not equal to 1 in single precision.

I have that the answer is 41, but when I let the number 3 for example be x, isn't 1/3 = 0.333, and when rounded = 0, 0 * 3 = 0? So why is the answer 41?

That's probably not what was meant by "round".  I suspect "round" probably meant to round to the nearest single-precision float.  In particular, you can easily verify that 41 is the smallest number with this property:

>>> from numpy import *
>>> float32(float32(1.0/3.0)*3.0)
1.0
>>> float32(float32(1.0/40.0)*40.0)
1.0
>>> float32(float32(1.0/41.0)*41.0)
0.99999994

But you should double-check the definition of the function round() with whoever told you this problem.  We can't read their mind.


Why $T(n)=6T(n-1) + n^3$ has such a mess solution? I tried to solve the recurrence relation
$T(n) = 6T(n-1) + n^3$ using the tree method, and figured out that the root will be $n^3$, the second level will be $6^1(n-1)^3$, the third will be $6^2 (n-2)^3$, and so on.

The formula as I understood it is: $\sum_{i=0}^n 6^i(n-i)^3$.

After entering this in Wolfram, the result is:

$$ \sum_{i=0}^n 6^i(n-i)^3 = \frac{1}{625}(-125n^3-450n^2-630n+366(6^n-1)). $$

And it doesn't look like a valid solution. Did I miss anything?

I'm not sure why you think this solution is invalid. It implies that
$$
\sum_{i=0}^n 6^i(n-i)^3 \sim \frac{366}{625} 6^n,
$$
and in particular,
$$
\sum_{i=0}^n 6^i(n-i)^3 = \Theta(6^n).
$$
You can also check it for particular values of $n$.

For example, when $n = 0$ you clearly get zero, and for $n = 1$ you get
$$
\frac{-125-450-630+366 \cdot 5}{625} = 1 = 6^0 (1-0)^3 + 6^1 (1-1)^3.
$$


What algorithms exist for solving natural number linear systems? I'm looking at the following problem:

Given $n$-dimensional vectors of natural numbers $v_1, \ldots, v_m$ and some input vector $u$, is $u$ a linear combination of the $v_i$'s with natural number coefficients?

i.e. are there some $t_1, \ldots, t_m \in \mathbb{N}$ where $u = t_1 v_1 + \dots + t_m v_m$?

Obviously the real-number version of this problem can be solved using Gaussian elimination. I'm wondering, has the integer version of this problem been studied? What algorithms exist to solve it?

Note that this is using natural numbers, but not modular arithmetic, so this is somewhat separate from the Chinese Remainder Theorem and systems like that. Also, it seems related to Diophantine equations, but I'm wondering what has been done in the case where only non-negative integers are considered?  This is also reminiscent of a multi-dimensional subset-sum problem, generalized to allow us to take an arbitrary number of copies of each vector.  It also seems related to testing whether $u$ is an element of the lattice generated by $v_1,\dots,v_m$, except that here we only allow linear combinations with non-negative coefficients.

For anyone interested, this is motivated by looking at whether a Parikh vector is in a linear set, as in Parikh's Theorem.

In particular, I'm interested in an algorithm that could solve the problem using only natural number operations, avoiding going into the reals/floating point numbers.

Your problem is NP-complete, by reduction from Subset Sum (it is in NP since the fact that everything is non-negative bounds the coefficients of the solution sufficiently well). Given an instance $S = \{s_1,\ldots,s_n\}, T$ of Subset Sum (is there a subset of $S$ summing to $T$?), we construct an instance $v_1,\ldots,v_{2n},u$ of your problem as follows. For each $1 \leq i \leq n$, we put $v_i$ to be the vector with two non-zero entries: $v_{i,i} = 1$ and $v_{i,n+1} = s_i$, and $v_{n+i}$ to be the vector with a unique non-zero entry $v_{n+i,i} = 1$. The target vector is $u=1,\ldots,1,T$. Each natural combination of $v_1,\ldots,v_{2n}$ equal to $1,\ldots,1,\ast$ must select exactly one of each of $v_i,v_{n+i}$, and so encodes a subset of $S$ whose sum is the value of the last component.


How strong is equivalence of lambda expressions? Consider two lambda expressions $\mu$, $\nu$ representing computable functions $f_{\mu,\nu}:\mathbb{N} \rightarrow \mathbb{N}$. If $\mu$ and $\nu$ are equivalent under the combination of $\beta$-reductions, $\alpha$-conversions and $\eta$-conversions then $f_\mu=f_\nu$.

  Under what conditions does the converse hold? In particular, if it is possible to prove in Peano arithmetic that $f_\mu=f_\nu$, does it follow $\mu$, $\nu$ are equivalent in the above sense?

In general, there is always an infinite number of "computationally different" functions that are extensionally equal: take for instance the "$3n+1$-function" $g$, and for any function $f$ define $G_f$ to be:

$$ G_f(n)=\begin{cases} f(n) & \mbox{if }g(n)\mbox{ cycles at }1 \\ 0 & \mbox{otherwise}\end{cases}$$

This function is (probably) extensionally equal to $f$ for every $f$, but this is (possibly) not provable in $\mathrm{PA}$, or indeed in the weak framework of $\beta\eta\alpha$-conversion.

More pragmatically, the identity function $\lambda x.x$ and the "stupid identity"
$$ \lambda n.n\ (\lambda x\ f.x)\ (\lambda m\ x\ f.f(m\ x \ f))$$

Denote the same function $\mathrm{id}:\mathbb{N}\rightarrow \mathbb{N}$, under the usual church encoding, but are not $\beta\eta$-equal, as can easily be seen (they are both in normal form).


Hamming code -- identical parity bits for different errors (7,4) Hamming Code (HC) detects all 2-bit errors and corrects all 1-bit errors.

However, there can be 2-, 3- or 4-bit errors that come with the same parity bits as that of 1-bit errors.

Eg.: Let the data be $1011$. So - the parity bits are

$P_1=0$

$P_2=1$

$P_4=0$

, the message transmitted is $0110011$ and the message received is $1000011$.

HC, assuming a 1-bit error, $1000011$ can accurately correct this to the
transmitted data, which is $1011$.

But then, suppose the receiver received $1010101$. This has the same parity bits as
$1000011$, and HC, assuming a 1-bit error,
would "correct" this as $0101$ which is wrong.

A particular set of parity bits can also hold for 2-, 3- or 4- bit errors.

How does the algorithm handle this?

The possibilities I can think of are:

a.) Takes this as a 1-bit error and just corrects it: in this case, a corrupt bit sequence is transmitted.

b.) corrects it as a 1-bit error, as it does in (a) above, and runs another detection algorithm, say checksum, to make sure.

How does Hamming code work this?

TIA.

When we say that a Hamming code detects (up to) 2 errors and can correct 1, we mean just that:

There is an error-detection algorithm that returns NO if there are no errors and returns YES if there are one or two errors. There is absolutely no guarantee when there are more errors.
There is an error-correction algorithm that gets a possibly corrupted word and outputs the original codeword, assuming that there was at most one error. There is absolutely no guarantee when there are more errors.

In real life we cannot always guarantee that there are at most X errors in every block, and this is handled by an "outer code", for example the checksum that you mention.


Two dimensional parity check Firstly, I would like to apologize if I misplaced this topic / i think the theory of coding is close to CS /

I am little bit confused right now, in the school we were learning about Hamming's code, Block codes etc.

I was given a homework, in which I should explain how does the two dimensional parity check finds 3-bit errors. I think the two-dimensional parity check does finds 3-bit erros, but it can't (in every case) correct it.

The second thing is, we were learning about hamming distance and there is a rule, which says that block code finds t-bit error when this equation is right:

t < d (and d stands for hamming distance, its minimum distance between the 2 code words / t stands for t-bit errors).

So for example: a = 110, b = 101, c = 100

1 1 0 | 0
1 0 1 | 0
1 0 0 | 1
_ _ __
1 1 1   1

The numbers behind the 'bars/underscores' are the parity-check bits, it means that in each column/row is even count of number 1.

So the minimum distance equals to 2. That means according to the rule t < d, that this code can detect only a t-bit error, which means 1 ( but that's not true, because it can detect 3 bit erros).

How should I explain that?.

Thanks.

Firstly the $t<d$ condition, applies to either the row or the column codes on their own. So you know that a single error in each row or column can be detected since $d=2$.

Given 3 errors overall for the array, consider the decompositions of errors into distinct rows. Clearly

$3=3$,
$3=2+1$, or
$3=1+1+1$

are the only possibilities.

In case 3 the column parity checks can correct these errors separately so we're done.

In case 2 the single error can be corrected on its row, and the remaining two errors on a single row, can be corrected  by the parity check in the corresponding column.

In case 1 all 3 errors are on one row, so by definition they are on 3 distinct columns and can be corrected by the parity check in the corresponding column.

So the array code can correct 3 errors.


Why does it take so long to prove optimality when warm-starting from optimal solution So I'm solving bigger instances of some binary-linear-program using cplex.
The formulations of the problem I am using is integer friendly, meaning nearly all of my instances can be solved at the root node.
Additionally I have a pretty good heuristic for calculating solutions. The heuristic is quite fast and nearly always gives the globally optimal solution.

When combining cplex with the heuristic I do not achieve the performance gains I expected. I feed the globally optimal solution to cplex as a "warm-start-solution", but it still takes quite some time for cplex to proof its optimality (cplex chooses the dual-simplex for the relaxation).

I might lack some theoretical understanding, but why can't the dual-simplex just build a basis for the supplied optimal solution and show that there is nothing else to do?

An IP-solver can use relaxations of variants of the integer program (that is, the linear program where the integrality constraints are dropped) among other steps to compute the final solution.

For these individual relaxations, the solver can indeed efficiently verify that it has an optimal basis. However, solving a relaxation is only a subproblem of solving the original IP. Therefore, even if you give an optimal solution to the original IP, this does not (necessarily) directly correspond to a basis in a relaxed LP, and the solver has to inspect other solutions than checking a basis.

There is one case in which providing an IP solution does allow for a fast check of optimality: when the relaxation of the IP is guaranteed to have the same solution as the original IP. (This is the case when the matrix describing the IP is totally unimodular or equivalently when the solution space is an integral polyhedron)

However, it is unlikely that the solver will be able to detect when this is the case. So, you will have to do that by some other means, and if the relaxed solution indeed solves the IP, you can let the solver solve the relaxed instance, and then the LP solver can quickly verify if your solution is optimal.


Types and Types Systems concepts Given this definitions about Types and Type systems :
Types are described by means of a language of type expressions:

Basic or primitive types: Bool, Char, Int, ...

Type variables: a, b, c, ...

Type constructors: → (function), × (tuple), [ ] (list), ...

Rules to build type expressions:
τ ::= Bool | Char | Int | ··· | t | τ → τ | τ × τ | [ τ ] | ···

Types whose type expression contains no type variable are called monomorphic types or just monotypes.

Types whose type expression contains variables are called polytypes or polymorphic types (parametric polymorphism)

A polymorphic type represents an infinite number of monotypes

I'm trying to understand the last definition but i can't.
A polymorphic type represents a infinite number of monoytpes, because in his type expression has a type variable ?

Yes, exactly. Because you can instantiate the polymorphic type with an infinite amount of (mono)types.

For example, the type $a \to a$ (which is a polymrphic type) represents

Bool $\to$ Bool
Char $\to$ Char
(Char $\to$ Int) $\to$ (Char $\to$ Int)
etc...


Average Cost Threshold Protocol with Minimum Thresholds: How to find the price? The protocol is defined here, but I'll give a summary here.

Okay, so a number of agents want a certain public good to be constructed (a public good is something like a book, a program, or a statue, something that can optionally benefit everyone once constructed.) It costs $P$ to construct this good. The agents each give an interval that they are willing to pay. Agent $i$'s interval is $[m_i,M_i]$. (In the case of a rational agent, $m_i=0$, but if the agent is somewhat altruistic, $m_i>0$. It has been proven that $M_i$ will always be how much value a rational agent $i$ expects to extract from the public good.)

Now, in this protocol, each person pays the same price $p$, or $m_i$, whichever is greater, or pays nothing at all if $p > M_i$. (Those who pay get access to the good, those who don't are excluded from the good.) What I am trying to do is find the minimum $p$, such that the total amount paid (let's call it $F(p)$) is equal to or greater than $P$, efficiently.

If all $m_i$ are $0$ and there are $n$ agents, I can do it $\mathcal O(n \log n)$. I first sort the agents by $M_i$. Then starting with the agent with least $M_i$, I figure out how much funds will be available with $p=M_i$. If $F(M_i) \gt P$, than $M_i$ is the minimum $p$. Otherwise, we go to the next agent, and so on. $F(M_i)$ can be calculated in $\mathcal O (n)$, by multiplying $M_i$ by how many agents come after (or are) agent $i$ (for each agent $j$ that comes after $i$, $M_j \ge M_i$. Since $p=M_i$, not $p>M_j$, and agent $j$ pays $p=M_i$.) (Note, I've left out the analysis for when $p$ is between the $M_i$'s; it doesn't change the it too much.)

My question is, how does one solve this problem efficiently in general, when the $m_i$ may not be $0$?

Note: Sorry if I didn't phrase this clearly. Feel free to ask for clarification in the comments.

There are two standard kinds of approaches to this sort of problem.

Check out segment trees and interval trees, and see if either of them are useful here (e.g., by augmenting the data structure).
Explore a sweep line algorithm.  In this sort of algorithm, we envision $p$ increasing from 0 upward as time progresses, and at each point in time, we keep track of the set of all intervals that contain $p$.  Thus, when $p$ hits the left endpoint of an interval, we add it to the set; when it reaches the right endpoint, we remove it from the set.  You can store the set as a balanced binary tree data structure, and then make it persistent using standard path copying techniques.  Now that you have this persistent data structure that captures all points in time, often you can find a way to solve your problem fairly rapidly.  Crucially, the tree will be of size $O(n \lg n)$ and depth $O(\lg n)$, so accesses are fast.

I haven't explored either of those approaches in the context of your particular problem, but these are two general techniques that are often useful for problems of this sort.


Partial polygon matching I am looking for fast procedures for polygon matching, i.e. checking polygon similarity under different transforms

translation only,
translation + rotation,
translation + scaling,
translation + rotation + scaling (= similarity).

The matching can be partial, meaning that there can be a good match on a significant fraction of the outline (say > 70%), and complete mismatch elsewhere.

The number of vertices is reasonable (say N<50).

In a variant of the problem, you need to compare two polygons. In another variant, you compare one polygon to a series of polygons, with preprocessing of the single polygon allowed. In a third variant, preprocessing is allowed on all polygons.

Are you aware of solutions to this problem ?

There is quite a bit of work on this important problem. Some of the most
insightful work is by Helmut Alt and collaborators. He wrote a survey in 2009:

  Helmut Alt. "The computational geometry of comparing shapes." Efficient Algorithms. Springer Berlin Heidelberg, 2009. 235-248.
  (Springer link.)

Image from Helmut Alt & Leonidas J. Guibas.
"Discrete geometric shapes: Matching, interpolation, and approximation." Handbook of computational geometry 1 (1999): 121-153.).


Shortest path when allowed to reverse an edge We're given an unweighted directed graph with vertices $V$ and edges $E$. We're trying to find the shortest path from $s$ to $t$ but we're allowed to travel along up to one edge in the wrong direction.

If we insist on using all edges in the correct direction, we can solve this using BFS algorithm with $O(|V| + |E|)$ complexity.  There's a brute-force solution by reversing each edge in turn and using BFS on each resulting graph, but that takes time $O(|V|\,|E|+|E|^2)$, which is rather inefficient. Is there a faster solution?  I Googled and couldn't find something similar, thanks for your attention and help.

I cannot provide any source URL, because it seems that it is a an example of "oral folk arts".

This is one of a class of similar problems which can all be handled by deriving a graph $G' = (V', E')$ from the original graph $G = (V, E)$ and then using the standard algorithm on $G'$.

Consider that at any point in your search in $G'$ you need the path information you would have at a corresponding point in the search in $G$ plus the knowledge of whether or not you have already used the bonus ability. Therefore what should $V'$ be? And following on from that, what should $E'$ be?


Solving consensus for a known number of processes I was given an object with exactly 2 operations test-and-reset that sets the value of the object to 0 only if it was previously set to 1 and does not return a value and fetch-and-add(v) which adds v to the value of the object and returns the previous value.

I am almost sure the consensus number of this object is 2 and I think I found an algorithm for it (I should mention the problem is binary consensus):

if input = 0
    test-and-reset(obj)
    prev = fetch-and-add(obj, 3)
    if (prev != 2)
        decide(0)
    else
        decide(1)
else
    prev = fetch-and-add(obj, 1)
    if (prev = 0 or prev = 3)
        decide(0)
    else
        decide(1)

The problem was to find a wait-free algorithm an algorithm for n processes using any number of these objects (n is known).

The problem is that I an not sure if I am right (I'm pretty sure and this holds me back on this idea)? And if I am right no idea how to use this to solve the problem.

Thanks

I was wrong the object has an infinite binary consensus number.

if (input = 0) test-and-reset(obj)
prev = fetch-and-add(obj, 2)
if (prev mod 2 = 0)
    decide(0)
else
    decide(1)


The proportion of halting programs vs non-halting programs, of decidable programs vs undecidable languages Can the following two statistics be bounded:

the proportion of halting programs vs non-halting programs
the proportion of decidable vs undecidable languages

For example, can we say that one class is much larger than the other, almost all problems are such and such, or both are similar in size?

By Chaitin's argument on the Omega number, we know that the halting probability is undecidable, so it is difficult to obtain an exact statistic on the number (if not impossible). However, Omega numbers have been computed for specific universal machines for prefix-free programs using probability measures decreasing in length (cf. Calude et al.).

So are there known valid statements about these proportions? My intuition (following the argument of the scarcity of life in the universe) would lead me to believe that there are much more undecidable languages than decidable ones. But it is only an intuition that is not backed.

EDIT: There are countably many recursive languages, and uncountably many non-recursive languages, so there are way more non-recursive languages.

There are countably infinitely many halting programs and non-halting programs alike.  I can't think of an interesting structure you can put on the set of programs that includes a concept of "proportion" where you end up being able to say anything interesting about the proportion of halting programs, unfortunately.

For instance, one natural structure to put on the set of programs is to give them a computable well-ordering.  One can make sense of questions about how big an infinite co-infinite subset of a countable set is if that countable set is well-ordered.  For example, the notion of asymptotic density can give credence to the intuition that there are more non-square integers than there are integers.  It basically says that the percentage of numbers that are not square tends towards 100% as you consider larger and larger finite initial segments of the naturals.  Asymptotic density makes sense for subsets of the naturals which have a canonical (computable) well-ordering.  The same cannot be said, however, for subsets of the set of all programs.  Since there is no canonical enumeration of the programs, there's no canonical answer to the question of proportion of halting programs in terms of asymptotic density.

Proposition: If $0 \leq \alpha \leq \beta \leq 1$ where $\alpha, \beta$ are computable real numbers, then there is an effective enumeration of the set of all programs such that the lower asymptotic density of the halting programs is $\alpha$, and the upper asymptotic density is $\beta$.

Proof Sketch: Let $\pi_1, \pi_2, \dots$ be a computable enumeration of all programs.  Let $\eta_n$ be the program:

print n
exit

Let $\nu_n$ be the program:

print n
loop {}

Note that $\eta_1, \eta_2, \dots$ is an effective enumeration of (some, obviously not all) programs that halt, and $\nu_1, \nu_2, \dots$ is an effective enumeration of programs that don't halt.

Let $0.a_1a_2\dots$ be the decimal expansion of $\alpha$, and $0.b_1b_2\dots$ the expansion of $\beta$.  Note that since $\alpha, \beta$ are computable, the sequences $a_1, a_2, \dots$ and $b_1, b_2, \dots$ are also computable.

Our goal is to build an effective enumeration of all the programs such that the lower and upper asymptotic densities of the halting programs are $\alpha$ and $\beta$ respectively.  We're going to build this enumeration in stages.  Each stage is going to have 3 parts:

At stage $n$:

(Sketch) Select programs from the front of the $\eta$ and $\nu$ lists that aren't already in our partially-constructed enumeration so far, and append them to the partial enumeration.  In this selection of programs, the proportion of $\eta$ (halting) programs chosen should be $0.a_1a_2\dots a_n$.  Select a lot of programs so that the proportion in the overall list (what had already been construct plus what has just been appended) is pretty close to $0.a_1a_2\dots a_n$ as well.  If we do this carefully at each stage $n$, we can assure ourselves that the lower density of the halting programs will be $\alpha$.
(Sketch) Do the same thing, this time so that the proportion of halting programs in the selection is $0.b_1b_2\dots b_n$.  Again, select a lot so that after appending these programs to the list so far, the overall proportion is close to $0.b_1b_2\dots b_n$.  If we do this carefully, we assure ourselves that the upper density of the halting programs will be $\beta$.
If $\pi_n$ isn't already in the list, append it to the end.  This ensures us that the enumeration we're building really does enumerate all the programs.


How does a language abstract away from underlying byte machines? So as the title suggests,

  How does a programing language, such as Java or C, abstract itself away
  from underlying byte machines?

Im curious, because I know that static/dynamic typing, data abstraction and control abstraction play a role. But I don't understand it so I was wondering if anyone could shed a nice explanation on this question!

Thanks a lot in advance!

EDIT: I currently have this as an explanation so far..

  Programming languages tend to abstract away from the underlying byte
  machines to provide a high-level view for the programmer. This can be
  for multiple reasons ranging from making code easier to write and
  debug, to solving platform issues.

  One way languages abstract themselves away is through typing. Using
  java as an example, it uses predefined base types of a certain size,
  including but not limited to: int, float and char. It also uses
  object/structured types which have a dynamic size such as Object and
  String. Like some others, it provides a garbage-collection and automatic memory management utility. This makes it abstract even
  further away as you can worry less about allocating memory space to
  data types, compared to a language like C.

I'm assuming you are really asking

  how is it possible that the same source code can be compiled to different architectures?

In order to achieve this feat different systems use different solutions.

Interpreter
Some languages use an interpreter. In this case there is no underlying architecture. The source code gets interpreted as written.

Virtual machine using byte code
Languages like C# and java compile to intermediary code (called byte code) for a virtual machine.
A runtime then executes this code somewhat like an interpreter would.
Frequently a just-in-time compiler further compiles (critical parts of) the byte-code to actual machine code.
So Java and C# do not care about the actual machine.

Virtual machine as intermediary target
Other compilers use the LLVM architecture. LLVM presents a virtual machine to the front end and a compiler using LLVM compiles for this virtual machine.
Specific LLVM backends tuned to a specific CPU architecture further compile this intermediary code to actual machine code.
LLVM differs from Java in that LLVM always compiles all code to machine code and it does not force any specific runtime upon the compiler.

Direct compilation
Traditional compilers like gcc (gnu C) compile the code to a specific architecture in a direct manner. Every architecture requires a different compiler which follows the language rules to create assembly code.
Maintaining separate compilers for different CPU architectures whilst ensuring all those abstractions work the same on all targets is accomplished through sheer hard work and coordination between compilers.

Hence the rise of intermediary virtual machines as compilation targets.

  To what extend does a compiler abstract away the underlying CPU?

This differs per language. Older languages like C tend to less abstraction.
The trend in newer languages is towards more abstraction.
Some languages offer both abstract types (always the same irrespective of architecture) as well as implementation dependent types (different for different architectures).
An example of this is a NativeInt type that is 32 bits on X86 and 64 bits on X64.

CPU's do some of the abstraction
The other element in play is that CPU's are converging towards a single 'constellation'. More and more CPU architectures are using the X64 model of 32 bit integers and 64 bit memory.
Also many CPU's are backwards compatible with their predecessors.
As long as a compiler produces code that runs on a current or previous version of a CPU that CPU will run it.
So in that case it's the CPU that abstracts away (some of) the differences.

  ... Byte machine

A byte machine does not exist.
There is byte code, which is code for the virtual machine used by e.g. Java.
and there is machine code, which is what a CPU consumes.

Memory management
You talk about memory management.
This is a subject completely different from abstraction.
Every CPU architecture handles memory in essentially the same way.
All but the most esoteric CPU's have a stack and use pointer logic to address the heap.
The fact that e.g. Java and C# use a garbage collector is not technically abstraction, but relates to resource management.
How resource management gets done depends upon the runtime library in use by that language.

Dynamic types
Dynamic types are invented to solve the problem of buffer overflows (arguably the number one security issue facing computing today).
If the runtime library handles string and array management then the burden on the programmer decreases.

  How does a languages abstract away managed or dynamic types

By using a runtime library.
All usage of dynamic and managed types gets translated into calls to the runtime library.
E.g. when using a dynamic string, the runtime library handles the reference counting, copy-on-write and growing and shrinking the storage as needed.
None of these actions are visible in the source code.


Why does Patience sorting find the longest increasing subsequence? According to Wikipedia (link), patience sort finds the longest increasing subsequence of a given sequence. Lets say the longest increasing subsequence of seq has length correct(seq)

Patience sort works like this:

Parameters: A sequence of integers called seq
Output: A number between 0 and the length of seq. Lets call it patienceSort(seq)
Algorithm (in Python):

def patienceSort(seq):
    piles = []
    for el in seq:
        for i in range(len(piles)):
            # If there is a pile with a strictly greater element on top,
            # place current element on that pile
            if piles[i][-1] > el:
                piles[i].append(el)
                break
        # if there is no such pile, create a new one
        else:
            piles.append([el])
    return len(piles)

What I've understood:

(I) We can guarantee that at every time the top of piles (piles[i][-1]) is ordered in increasing order.

(II) For numbers in the same pile: Numbers are ordered...

(II.1) ... by time (first one in the pile came first)

(II.2) ... by value (first one in the pile has highest value)

(III) The numbers on top of the piles are not necessarily an increasing sequence
within seq

(IV) The right pile is always the latest one that was created

Example for (III):

      37
20    38
30    39
40    40
50    70
pile1 pile2
seq = [50,40,70,30,40, 39,38,37,20]
[20,37] is not an increasing sequence in seq

For each card (which is not on the first pile), you can store a pointer to the top of the pile before when you add it to the pile. This way, you can get an increasing sequence by following the pointers and inverting the list. So:

patienceSort(seq) <= correct(seq)

Question

Why is patienceSort(seq) >= correct(seq)

With the two insights from (II) it is obvious that no increasing sequence can use two cards (or more) from one pile.

This means: No increasing sequence can use more cards then the number of piles.
But patience sort returns the number of piles.

So: patienceSort(seq) >= correct(seq)

See also: Slides from Princeton with pictures.

Thank you very much Yuval Filmus :-)


How do I use the pumping lemma for a^n b^m a^(n+m) ? How can I choose the pumping length? $L = {a^n + b^m + a^{n+m}}$
This is the language I want to show is not regular.
Now my problem is to choose p correctly.
Can I just set it as p=2*(n+m) ?
That's the problem I am facing now.
Thanks for any help I am starting to learn it to use the pumping lemma.
Edit:
In the meantime I have done this:
$w=a^nb^ma^{n+m}$
|w|= 2(n+m)=p
$|xy|\leq 2n + 2m$
We choose $x=a^n, y=b^m, z=a^{n+m}$
$|a^nb^m|=nm \leq 2n+2m$
w=xy^iz
Now we set i = 0
$w_0=a^na^{n+m} \notin L $
$\implies $ L is not regular.

It seems that you are trying to force the string length to be $p$, which is not necessary. What is required is that $|xy| \leq p$. The length of $w$ can be greater than $p$. Also, $n$ or $m$ can be $p$ or some multiple of $p$, whatever  makes the reasoning for the impossibilty of partition of $w$ to satisfy the lemma. With that, I think you can follow through and complete your proof.
Just remember, the aim is not to look for a partition of $w$ that does not work. Rather show that no partition works.
Cheers.


How to write a coterminating, effectful program? [Using Idris for code examples and terminology, but the question is not about Idris per se]

In a post titled A Neighborhood of Infinity, @sigfpe argues that "the kind of open-ended loop we see in operating systems and interactive applications" is to be modeled mathematically using codata, and that these sorts of programs can even written in a total functional programming language if they found to coterminate. Though I don't yet understand this to the depth in which he lays it out, the idea makes sense, and I'm familiar with the fact that Idris' totality checker (for example) considers cotermination. Thus, we might write the Unix yes program thus:

yes : Stream String
yes = "yes" :: yes

—except that this is not Unix yes, but intra-Idris yes. I cannot run this program and have it do what yes does: I need an effectful program. Stream is a Functor; it seems I want a main : Stream (IO ()).  Let me make the example slightly more compelling by making this an interactive program, as @sigfpe speaks of:

stopOrPrint : String -> IO ()
stopOrPrint s = do
  maybeQ <- getChar
  if maybeQ == 'q'
  then pure ()
  else putStrLn s

main : Stream (IO ())
main = map stopOrPrint yes

But Idris does not accept programs whose main function has type Stream (IO ()). No problem, maybe if I used traverse_ : Foldable t => Applicative f => (a -> f b) -> t a -> f () instead of map, I could get a main with the right type, IO (). However Stream is not a Foldable, and I'm thinking it's not just because Brady forgot to implement it: how do you guarantee that you can fold a potentially infinite value into a finite value? Isn't that kind of crossing over from infinitude to finitude the opposite of totality?

So I'm stuck. I love the idea that with codata and cotermination, we could write a total operating system or even server. But when I actually go to write a socket server in Idris, I end up marking stuff partial; yet Idris' totality checker respects these ideas.

Am I running into a limitation of Idris (or any languages currently in existence), or a more fundamental limitation? If Idris just learned to take a Stream (IO ()) for its main, would that solve it? I have a feeling that still doesn't address the underlying issue, because now you have a bunch of disconnected IOs: don't you actually want an infinite IO monad (can there be such a thing?)?

Is it possible to mix cotermination and effects, in a pure, total functional language? Has it been done? If not, what would it have to look like?

In these sorts of cases, one idiomatic way is to run it with gas, and to create one non-total gas value to let you finish the program. Yes, perhaps Idris should offer a combinator for IO that allows full streams to be run, but this is sufficient, and doesn't affect the validity of anything else.

Seeing this, I'd agree that the IO monad should be coinductive, not inductive.

%default total

data Gas : Type where
  More : Lazy Gas -> Gas
  Done : Gas

runStream : Gas -> Stream (IO ()) -> IO ()
runStream (More g) (i :: is) = i >>= \_ => runStream g is
runStream Done _ = pure ()

partial
unbounded : Gas
unbounded = More unbounded


Is a stack overflow detected by hardware or software? Is it the task of the software (operating system) to detect stack overflows or is a stack overflow detected in hardware, causing an exception in the CPU?

It can be software, or hardware, or both, or none.

There are two kinds of overflows: overflow when growing the stack (when entering a function), and overflow when accessing an array on the stack. Overflows when growing the stack can be detected by making a bounds check on function entry, to verify that there is enough room (and either signal an error or grow the stack if there isn't). Overflows when accessing an array on the stack are only an issue in low-level languages that don't verify array bounds; the solution there is to verify array bounds.

These software approaches have the advantage that they work fully reliably: you can be sure that any stack overflow will be detected. Their downside is that they increase the code size and the execution time. Hardware can help by providing a method to detect most overflows at no cost as long as no overflow occurs. On an architecture with an MMU¹, the runtime environment can arrange to map the stack on a page boundary, with the next page remaining unmapped.

+---------------+---------------+---------------+---------------+
| stack                         | unmapped      | other stuff   |
|    ----> direction of growth  |               |               |
+---------------+---------------+---------------+---------------+
^               ^               ^               ^               ^  page boundaries

That way, if the software attempts to access data beyond the page boundary (whether because the stack pointer has moved beyond the boundary or because the array access is out of bounds and beyond the boundary), it will cause a fault by accessing an unmapped area. This only happens if the overflow is small enough: if the amount of overflow is too large, the program may end up accessing other stuff on the other side of the gap in the address space.

The downsides of the hardware approach are that it isn't fully reliable since an overflow by a large amount may not be detected, and that it doesn't detect array overflows that remain within the addressable space.

To detect array overflows, another software technique is a canary: put a special value at the top of the stack or between frames, and check that the canary value hasn't changed on function return. This is also an imperfect technique since the overflow might avoid the canary altogether or might not be detected because the canary value has been restored by the time it is checked. Nonetheless, it is useful to make it harder to exploit some security vulnerabilities.

The safest and cheapest way to avoid stack overflows is to calculate the amount of stack that the program will need before starting to execute it, by static analysis. However this is not always practical: the amount of stack needed by a program is undecidable in general and depends on the data that's manipulated by the program.

¹  The same principle can also be applied with just an MPU, or with no memory protection if there is a single thread whose stack is at the edge of the existing physical mappings.


Is PREFETCH an asynchronous operation? I often hear Prefetching as a technique for speeding up, for example, sequential memory access pattern.  The prefetch should occur sufficiently far ahead in time to mitigate the latency of memory access, for example in a loop traversing memory linearly.

According to the famous "What Every Programmer Should Know About Memory" paper by Ulrich Drepper, it is written:

  This prefetching would remove some
  of the costs of accessing main memory since it happens
  asynchronously with respect to the execution of the program

(emphasis mine)

I could not find references on Google or Wikipedia corroborating or proving this. Does anyone know where I can find if this is true?

The only reasoning I can think of is rhetorical: it must be asynchronous b/c otherwise prefetching offers no benefit to sequential access... unless the execution time of prefetching a cache line is less than bypassing prefetch and placing the same cache line from RAM directly into cache.

If it is implemented in hardware, prefetching is typically done asynchronously.

It's also possible for a compiler to insert extra prefetch instructions into the code.  Thus, the initiation of the fetch is done synchronously, but then the memory access continues asynchronously.

See https://en.wikipedia.org/wiki/Cache_prefetching.


Solving recurrence relation with square n I have the following recursive function:

$$
T(n) =
\begin{cases}
\theta (1) & \text{if $n$ = 1;}\\
T(\sqrt{n}) + \theta (log(n)) & \text{if n $\geq$ 2}\\
\end{cases}
$$

I tried:

\begin{eqnarray*}
T(n)&=&T(\sqrt{n}) + log(n)\\
&=&T(\sqrt[4]{n}) + 2 log(n)\\
&=&T(\sqrt[8]{n}) + 3 log(n)\\
\end{eqnarray*}

I can't find a way to solve it without master theorem.
Is it possible to solve this with the recursive three method? I don't know when should i stop the recursion.

I've already seen other questions about this topic, but they didn't solve my problem.

Thanks

The thing to point out is that the $\sqrt{n}$ in the recurrence relation should be interpreted correctly - either you view $T$ as a function defined on $\mathbb{R}_{\geq 1}$, which is bounded near $1$, or you actually understand the $\sqrt{n}$ as the integral part, i.e. $[\sqrt{n}]$.

In the first case, you fix a small neighborhood of $1$ on which the function $T$ is bounded by a fixed constant, and the recurrence stops when $n$ falls into this neighborhood; in the second case, the recurrence simply stops at $n = 1$.

Here I give a solution using the first understanding:

Put $m = \log(n)$ and rewrite the relation as:

$$ S(m)=\begin{cases}\theta(1) & m = 0 \text{ (or better: $m \rightarrow 0$)};\\ S(m/2) + \theta(m) & m > 0, \end{cases} $$
where $S(m)$ is the function defined by $S(\log(n))=T(n)$.

This translates to the following: we have constants $r$, $c$, $d$, such that:

$S(m) \leq c$ for all $0 \leq m < r$;
$S(m) \leq S(m/2) + d \cdot m$ for all $m \geq r$.

It is then easily proved using induction that we actually have $$ S(m) \leq \max(2c/r, 2d) \cdot m $$ for all $m \geq r/2$. (First note that it is true for $m$ in the interval $[r/2, r)$, and then show that if it is true on the interval $[x/2, x)$, then it is also true on the interval $[x, 2x)$.)

So finally we get $T(n) = \theta(\log(n))$.


Do we generally store the degree of each vertex in the linked list implementation? if not, why? So generally speaking, when we implement the graph using linked list, do we store the degree of each edge too?

I'm asking this because if a question in my exam stated that we implemented this graph using linked list, do i assume we can access the degree of each edge in o(1) or not? this matters because it effects the time complexity of algorithms like finding if the graph has euler cycle which i should check the degree of each edge

and the exams are SAT type of questions so i can't write down anything i should just choose one of the 4 answers which for example says the time complexity of finding if the graph has euler path in linked list implementation

Normally we don't; the adjacency list representation is a list of out-edges, but doesn't separately store the degree.  However, you can certainly store that additional information if you want.  You can choose how you want to represent the graph, and it's not hard to modify the standard data structure to keep track of the out-degree of each vertex.


Characterize an OS as multiprogrammed OS Which of the following features will characterize an OS as multiprogrammed OS?

More than one program may be loaded into main memory at the same
time.
If a program waits for certain event another program is
    immediately scheduled.
If the execution of a program terminates,
        another program is immediately scheduled.

My attempt:

Only, statement (1) is correct, but statement (2) and (3) may not be true when there were no process at ready state. So, they should be false.

But, somewhere it explained as both statement (1) and (2) are true, and (3) is false.

And also, official key is given all statements are correct.

  Can you explain it, please?

Sorry That is not a complete answer but i hope it can help you .

"One of the most important aspects of operating systems is the ability
to multiprogram. A single program cannot, in general, keep either the CPU
or the I/O devices busy at all times. Single users frequently have multiple
programs running. Multiprogramming increases CPU utilization by organizing
jobs (code and data) so that the CPU always has one to execute.
The idea is as follows: The operating system keeps several jobs in memory
simultaneously (Figure 1.9). Since, in general, main memory is too small to
accommodate all jobs, the jobs are kept initially on the disk in the job pool.
This pool consists of all processes residing on disk awaiting allocation of main
memory.
The set of jobs in memory can be a subset of the jobs kept in the job
pool. The operating system picks and begins to execute one of the jobs in
memory.Eventually, the job may have to wait for some task, such as an I/O
operation, to complete. In a non-multiprogrammed system, the CPU would sit
idle. In a multiprogrammed system, the operating system simply switches to,
and executes, another job. When that job needs to wait, the CPU switches to
another job, and so on. Eventually, the first job finishes waiting and gets the
CPU back. As long as at least one job needs to execute, the CPU is never idle.
This idea is common in other life situations. A lawyer does not work for
only one client at a time, for example. While one case is waiting to go to trial
or have papers typed, the lawyer can work on another case. If he has enough
clients, the lawyer will never be idle for lack of work. (Idle lawyers tend to
become politicians, so there is a certain social value in keeping lawyers busy.) Multiprogrammed systems provide an environment in which the various
system resources (for example, CPU, memory, and peripheral devices) are
utilized effectively, but they do not provide for user interaction with the
computer system. Time sharing (or multitasking) is a logical extension of
multiprogramming. In time-sharing systems, the CPU executes multiple jobs
by switching among them, but the switches occur so frequently that the users
can interact with each program while it is running."

"Time sharing and multiprogramming require that several jobs be kept
simultaneously in memory. If several jobs are ready to be brought into memory,
and if there is not enough room for all of them, then the system must choose
among them. Making this decision involves job scheduling."

'Having several programs in memory at
the same time requires some form of memory management'

Operating System Concepts Essentials -Abraham Silberschatz -second edition [2013] section [1.4]


what does it mean by problem of size $0$? I am having problems understanding a basic concept in CLRS, it is about worst case partitioning during quicksort --

  The worst-case behavior for quicksort occurs when the partitioning routine produces one subproblem with $n − 1$ elements and one with $0$ elements.

What does it mean by subproblem of size $0$? But what I see is there will be two subproblems, one with size $n-1$ and another with size $1$. I fail to grasp the idea of $0$ size.

Can someone explain?

We're talking about algorithms to sort a list.  Therefore, in this context, a problem of size 0 is a list of size 0, i.e., the empty list.

Quicksort splits a list of size $n$ into two sublists of size $m$ and $n-m-1$.  They sum to $n-1$ (not $n$), because quicksort removes the pivot element: the pivot element is not included in either sublist.  Therefore, the text you have quoted is correct.  If one sublist has size $n-1$, then the other will have size 0 (not size 1).


How center the eyes of human face at specific pixels? I am facing a problem with processing some frontal facial images.

I need to adjust the centers of the eyes (irises) to be at certain specific pixels in the image. In other words, i need to transform the image until the centers of the eyes are at specific pixels.

Can anyone help me with this problem, an algorithm, technique, ...etc. that might solve this problem ?

Thanks,

Assuming you can find the centers of the eyes...

Rotate - Find the difference of the angle between the actual eyes and your desired angle. Rotate image accordingly.
Scale - Find the distance between eyes. Scale according to the desired distance.
Translate - Move the image so that one eye lines up. If you've rotated and scaled properly, both should now be in the desired spot.


Perplexed by Rice's theorem Summary: According to Rice's theorem, everything is impossible. And yet, I do this supposedly impossible stuff all the time!

Of course, Rice's theorem doesn't simply say "everything is impossible". It says something rather more specific: "Every property of a computer program is non-computable."

(If you want to split hairs, every "non-trivial" property. That is, properties which all programs posses or no programs posses are trivially computable. But any other property is non-computable.)

That's what the theorem says, or appears to say. And presumably a great number of very smart people have carefully verified the correctness of this theorem. But it seems to completely defy logic! There are numerous properties of programs which are trivial to compute!! For example:

How many steps does a program execute before halting? To decide whether this number is finite or infinite is precisely the Halting Problem, which is non-computable. To decide whether this number is greater or less than some finite $n$ is trivial! Just run the program for up to $n$ steps and see if it halts or not. Easy!
Similarly, does the program use more or less than $n$ units of memory in its first $m$ execution steps? Trivially computable.
Does the program text mention a variable named $k$? A trivial textual analysis will reveal the answer.
Does the program invoke command $\sigma$? Again, scan the program text looking for that command name.

I can see plenty of properties that do look non-computable as well; e.g., how many additions does a complete run of the program perform? Well, that's nearly the same as asking how many steps the program performs, which is virtually the Halting Problem. But it looks like there are boat-loads of program properties which a really, really easy to compute. And yet, Rice's theorem insists that none of them are computable.

What am I missing here?

For the purposes of this discussion, a "program" is a piece of code which always takes an integer as an input, and either runs forever or returns an integer. We say that two programs $f$ and $g$ are extensionally equal if they compute the same function, i.e., for every number $n$ either both $f(n)$ and $g(n)$ run forever, or they both terminate and output the same number.

An extensional property of programs is a property $P$ that respects extensional equality, i.e., if $f$ and $g$ are extensionally equal then they either both have the property $P$ or both do not have it.

Here are some examples of non-extensional properties:

The program halts within $n$ steps. (We can always modify a program to an extensionally equal one that runs longer.)
The program uses fewer than $n$ memory cells within the first $m$ steps of execution. (We can always modify a program to an extensionally equal one so that it uses up some memory for no good reason.)
The program text mentions a variable named k. (We can rename variables.)
Does the program invoke command $\sigma$. This may depend a bit on what $\sigma$ is, but if it is something that can be simulated in some way, then we can evade $\sigma$ and still have a program which is extensionally equal to the original one.

I am sure you have noticed that I listed precisely your alleged counter-examples to Rice's theorem, which says:

  Theorem (Rice): A computable extensional property of programs either holds of all programs or of none.

There is another way to explain this: you have to distinguish between a program and the function it computes. Many different programs compute the same function (they are all extensionally equal). Rice's theorem is about properties of functions, not about properties of programs that compute them.


Adaptive step size constrained to a limited number of iterations I'm solving a differential equation on the form $\ddot x = f( \dot x, x)$ on a microchip within a limited (real world) time frame, hence I want to use an adaptive step size to get as good of a result as possible. However, I only have a limited number of iterations, $N$, to solve the system. If I use the "regular" adaptive time step methods of estimating the local error and adapting the step size there's no guarantee that I will be able to solve the system in $N$ iterations.
Does anyone know where I can find algorithms for this? All I can find are the "regular" adaptive time step algorithms where $N$ isn't limited.
The current solution I have is to assume that the error is proportional to the magnitude of $\ddot x$ and projects a line from $x(t_0)$ with constant velocity $\dot x = c$ to reach $x(t_n)$ and then use the differential equation to get the distribution of the magnitude of $\ddot x$ to know where the step size needs to be small and adjust it accordingly.
This projected line obviously is not the real path but the idea is that it will give me a good approximation of how the error changes in the future so that I know if I can "afford" to have a small step size at each given iteration. This method assumes that you have the primitive function of $f(c,x(t))$ with respect to t when c is constant, $x(t)$ is linear and $f^{-1}$ exists. The method could probably be expanded to use constant acceleration to project the path instead of constant velocity, but the idea is the same.
The problem is that I can't find any information on the subject and I highly doubt that my naive initial idea is the best one out there.

I've come to the conclusion that it's not worth doing for my application, so I thought I would post my progress here for anyone else who might be interested in this same problem.
My more "proper" solution, which does not put any constraints on the differential equation but instead uses an error estimation for the adaptive steps, more like a traditional approach. For anyone dealing with the same problem or interested in a solution here it goes.
For the Euler method we can assume that the error is: $ \varepsilon = c h^2 $, and that $c \approx | \ddot x_t - \ddot x_{t-1}$|. In order to limit the number of iterations we will take we have to make some assumptions about the future. The assumption I made is that we will have some average error when we take an equidistant step, and this error will be constant. So let's define the "future average error" as $\hat \varepsilon = \hat c {\hat h}^2$. Since we assume that the future points will be equidistant we know that $\hat h = l/n$ where $l$ is the remaining length (of time) and $n$ is the remaining number of iterations. We don't know $\hat c$ but after some testing I found that the current average $c$ worked rather well, and an exponentially smoothed $c$ worked even better. Making projections on how $c$ will change based on previous data might yield even better results, but I'm trying to do this with few operations so I don't have time to make any advanced predictions.
Now we have all we need, given the assumption that the best accuracy is reached when the error is constant we can set the two equations equal and get: $c h^2 = \hat c (l/n)^2$ which gives us a step size of:
$h = \sqrt{ \frac{\hat c}{c}} \frac{l}{n}$
This step size alone performs rather well, but we do not have any upper bound on the step size and we will get division by 0 if c is zero (if the acceleration is constant between two points). So we simply introduce a lower bound on c defined by an upper bound on h:
$c_{min} = \hat c ( \frac{l}{n h_{max}} )^2$
After some testing I've found that a good value for $h_{max}$ is $\frac{l}{max(n-1,3)}$
So to recap, for the one who just want to test it the algorithm is as follows:
h_max = length/(max(n-1,3))
c = max(abs( a - a_previous ),c_hat*(length/(n*h_max))^2 )
c_hat = alpha*c + (1-alpha)*c_hat

h = sqrt(c_hat/c)*length/n

where a and a_previous is $\ddot x_t$ and $\ddot x_{t-1}$ for the differential equation. If you implement this it's important to remember that length and n is the remaining length and iterations, not the total, so it needs to be updated every iteration. It's also important to note that c_hat is updated with the current c value, I found this to yield much better results.
On to why I don't think it's worth it. During my testing I got a maximum of a 40% decrease in Mean Squared Error compared to the "true" solution (evaluated using many many more points). The error for the final point however was often worse than simple equidistant evaluation, even for 'simple' differential equations like y' = a -y. It was only for differential equations which varied a lot (like those with sinusoidal solutions) which gave an improvement in the accuracy of the final point, and since I'm mostly interested in the accuracy of the final point I think it's worth spending those computational resources on doing more iterations rather than adapting the step size. I can probably cram in twice the number of evaluations instead of doing adaptive step sizes which in my testing was always better than the adaptive strategy.
For anyone who wishes to test this further, the main reason why this method doesn't perform as good as one might expect is because of how $\hat c$ is evaluated. Since it's based on previous values (and heavily skewed toward the current value) the algorithm holds off on small step sizes which often is detrimental to performance. Trying to predict how $\hat c$ will actually look in the future would probably yield much better results and it would be a good place to start exploring further.
TLDR;
If you have this problem, just spend the computing resources on more iterations (or higher order methods) instead of advanced methods to adapt the step size.