How is electricity brought to the transistors? I feel like my knowledge of computer science is being hindered by this one concept. I understand the concepts of transistors and how a flow of electricity  can turn a transistor on or off, and with the power of logic gates, this can form the foundation of programming. What I do not understand is how these microscopic transistors are turned on or off, and how  electricity gets there in the first place. Thanks.

Electrictiy is brought by wires as usual. But electricity involves 2
kinds of characteristics: voltage (in Volts: V) and current (in
Amperes: A).  Transitors and other similar devices come in various
types. The basic idea is that there are three connectors. A reference
connector (ground), and two others. One correspond to a control
circuit and the other to a controlled circuit. The transistor can have
a high or low resistance to current produced by some source, thus
controlling the flow of electricity and the voltage between the ground
and the controlled circuit connector. The state high or low resistance
is fixed by a small current (bipolar transistor) or by a voltage
(triode vacuum tube, field-effect transistor) between the control
connector and the ground.

The ground connector is called the emitter, source or cathode, for
respectively the bipolar transistor, field-effect transistor and
triode. The controlling connector is the base, gate, or grid, and the
controlled connector is the collector, drain or anode.

The idea is that the controlling circuit uses little energy to
transmit a logical signal to a circuit that can carry much more
energy (the product of voltage and intensity). This can regenerate a
distorted signal, and also make it powerful enough to be sent to
several other circuits, or actuate other devices. With appropriate
circuitry it makes for the various logical gates.

The simplest device to understand may the triode, though it is not a
transistor, strictly speaking, but its vacuum tube ancestor. There is a voltage
between cathode and anode, and by heating the cathode, the (negatively charged)
electrons are freed and can be attacted by the anode that has a
positive charge. However, there is the grid in between: if the grid
has a positive voltage, it will atract the electrons even more, and
they will speed through it with enough momentum to go through (most of
them) and reach the anode. But if the grid is charged negatively, it
will create an obstacle that electrons cross with difficulty and
little current will atually go through.  The working of the
field-effect transistor (FET) has some similarity to that, but I am no specialist.


PCP deterministic emulation Suppose that $S \in PCP(r(n),q(n))$, colclude that $S \in NTIME(2^r \cdot poly) \cap DTIME(2^{2^r q+r} \cdot poly)$

The idea of a nondeterminstic simulation of the $V$ on input $x$ is simple, guess a proof, check every string $y$ of the length $2^r$, and this simulation should take nondeterministic time $2^r \cdot poly$ because $V$ works in time $poly$ and there are $2^r$ string to check.

In case of deterministic simulation the same intuition is applied, the maximum length of the proof is $2^r \cdot q$ with non-adaptive queries, hence $2^{2^rq}$ number of proofs  should be checked by deterministic emulation, therefore the total time is $2^{2^r \cdot q} \cdot poly$, not exactly what's required.

The problem is to show that $S \in NTIME(2^r \cdot poly) \cap DTIME(2^{2^r q+r} \cdot poly)$

Checking each of the possible proofs takes time $O(2^r\cdot poly)$, so checking $2^{2^rq}$ of them would take how much?


How literally is "optimization" or "optimization algorithm" used in CS? I have been confronted with two meanings of the term "optimization" or "optimization algorithm":

to find the absolute maximum in a set $X$ according to some criterion $f:X\to \mathbb R$
to find a "relatively high" or "increasingly high" or "locally maximum" element in a set $X$ according to some criterion $f:X\to \mathbb R$

A friend of mine claimed that nr $1$. is the only "official" meaning of the term, and that only laymen or people who speak informally use the meaning of $2$. Is my friend correct?

There is no governing body mandating the meaning of terms in computer science. Instead, just like all human language, the meaning of a term is defined implicitly by its use, and could depend on the language community.

In theoretical computer science, optimization is a wide topic that covers many different problems. The most common problem is to find the maximum or minimum of a function subject to constraints. Often one is interested in finding an approximate optimum, or an approximate optimum which only approximately satisfies the constraints (this is known as a bicriteria approximation).

When finding even an approximate optimum turns out to be difficult, it is reasonable to consider finding a local optimum or an approximate local optimum. This happens, for example, in machine learning, and is actively pursued by the optimization community.

Summarizing, there is no official meaning of the term optimization in computer science, any more than there is an official meaning of this term in English. In practice, in the theoretical computer science community, the term is widely used in the more relaxed sense corresponding to your second definition, and beyond.


Probability bounds on size of smaller partition in randomized quicksort Let $0 < a < 0.5$ be some constant. We have an $n$-element array as input. Randomized quicksort chooses one element from array uniformly at random as a pivot and partitions. With probability $1-2a$ the smallest section be greater than $an$.
How we can Calculate this probability?
after 72 hours try i reach to following that means valid area is (1-a)n-an=n(1-2a). by dividing n(1-2a)/ n we get 1-2a.

Suppose for simplicity that all elements are distinct, and that after sorting, these elements are $x_1,\ldots,x_n$. A random pivot has the same distribution as $x_i$ for $i$ chosen uniformly at random from $\{1,\ldots,n\}$. The size of the smaller partition is $\min(i-1,n-i)$. If $I$ is the set of indices $i$ such that $\min(i-1,n-i) \geq an$, then the probability you are looking for is $|I|/n$ (by the definition of uniform probability). I'll let you complete the calculation.


Master theorem recurrence relation Consider I have the following recurrence

$$T(n) = 10T(n/3) + \Theta(n^2\log^5 n)\,.$$

Now, by the master theorem, if we evaluate $n^{\log_{b}{a}}$, we get $n^{\log_{b}{a}} = n^{\log_{3}{10}} = n^{2.095}$. Now, can anyone please explain me, which of the three cases apply? If you plot these functions you can see that $n^2\log^5 n$ clearly dominates. So, the answer should be $\Theta(n^2\log^5n)$.

However, if you try plugging in values in this calculator, you see that the answer is $\Theta(n^{\log_{3}{10}})$. Does anyone have a formal reason? I am still confused as to which of these conditions apply.

Plotting isn't foolproof: for any $k,\varepsilon>0$, we have $\log^kn = o(n^\varepsilon)$ (here, I've cancelled the common term of $n^2$). However, you can need to take $n$ really big to see it when $\varepsilon$ is small (e.g., $0.095$) and $k$ isn't so small (e.g., $5$).  Here's the plot for $0\leq n\leq 10^{131}$, again with the $n^2$ term cancelled, and it looks quite different from your plot up to $n=10^5\,$!

Indeed, this question may even have been designed to catch you out if you try to compare the asymptotic growth by plotting instead of by understanding.


Paths in a graph with two kinds of costs A weighted graph $G= (V, E, W_1, W_2)$ has two cost functions $W_1, W_2 : E \rightarrow \mathbb{R}$. Each edge $e$ has two costs $W_1(e)$ and $W_2(e)$. We may think the costs as representing different resources, such as time and fuel. Similarly, a path $p =e_1, e_2, \dots e_n$ has two costs,

$$W_1(p) = \sum_i W_1(e_i) \qquad \text{and} \qquad W_2(p) = \sum_i W_2(e_i) \qquad$$

Consider the following decision problem: given two nodes $u, v \in V$ and two constants $c_1, c_2$, does there exist a path $p$ from $u$ to $v$ such that $W_1(p) \le c_1$ and $W_2(p) \le c_2$?

Is it NP complete or is a polynomial algorithm known to exist?

This is NP-hard by reduction from Partition.

Given an instance of the Partition problem consisting of $n$ nonnegative integer values $x_1, \dots, x_n$, we can generate an instance of your problem as follows:

Make $n+1$ vertices $s_0, \dots, s_n$.  Let $u = s_0$ and $v = s_n$.
Make $n$ vertices $a_1, \dots, a_n$, and edges $s_{i-1}a_i$ for every $1 \le i \le n$ having weights $W_1(s_{i-1}a_i) = x_i$ and $W_2(s_{i-1}a_i) = 0$.
Make another $n$ vertices $b_1, \dots, b_n$, and edges $s_{i-1}b_i$ for every $1 \le i \le n$ having weights $W_1(s_{i-1}b_i) = 0$ and $W_2(s_{i-1}b_i) = x_i$.
Also add edges $a_is_i$ and $b_is_i$ having both weights 0 for every $1 \le i \le n$.
Set $c_1 = c_2 = \frac{1}{2}\sum_{i=1}^n x_i$.

The original Partition instance has a solution if and only if the above-constructed instance of your problem has a solution.  Basically, for each number $x_i$, we must visit exactly one of the vertices $a_i$ or $b_i$, incurring a cost of $x_i$ for one of the two weights (and zero cost for the other weight).


Possible ways to have cross and full edges in a mincut maxflow I am trying to solve the following problem about maxflow mincut
it seems like my conclusion is incorrect and I am wonder where.

There is no graph just following question.

An edge e can be (x) always full, (y) sometimes full, (z) never full; it can be (x') always crossing, (y') sometimes crossing, (z') never crossing. So there are nine possible combinations: (xx') always full and always crossing, (xy') always full and sometimes crossing, and so on. Or are there? Maybe some possibilities are impossible. Let's draw a table:

Possible answers ---based on my conclusions

always full and always crossing. (true based on the image above)
always full and sometimes crossing.  (true based on the image above and the fact that we may have several crossing edges one of them may be full, all them if all edges in the min cut is 1 and one of the crossing edges is 2)
always full and never crossing. (false seems like there always must be a possibility of one of the ways to use edge with less capacity)
sometimes full and always crossing. (true if we have all edges in the mincut that are 1 and crossing edge is two)
sometimes full and sometimes crossing.( false since if we have many crossing edges that are 1 and one of them is 2 means that we might want to use the edge 2to flow more)
sometimes full and never crossing. (true easy to see and edge that sometime full but never crossing in a graph)
never full and always crossing. (true if all edges in a mincut is 1 and crossing edge is two)
never full and sometimes crossing. (true if we have many 2 crossing edges)
never full and never crossing. (true if we have a graph where one edge is 2 in min cut that never crossing)

Have asked this question on /math.stackexchange.com with no luck.

wording used.

The edge is full means in in any way we pump the flow the edge is always going to be full, basically if we have and C---(1)---A------(1)----B   and there is no other way to get to B other then going thru a then A is always full.   Somewhat full if we can have C---(1)---A------(1)----B  and if there is another way to get to b by doing  C---(1)---E---(1)----B  then edge is only sometime full. never full if we have C---(1)---E---(2)----B then most we can flow is 1 but b takes 2 then it never full.  The crossing part if we it can be the crossing edge in the min-cut from the cut to the sink. basically it and edge that connects the cut with the rest of flow.

Thanks.

This is the previous question which defines the terms. I hope this helps you solve the question.

Thus question provides these as true:

always full and always crossing.
always full and sometimes crossing.

We know from the definitions I've provided that the following are also true:

sometimes full and never crossing
never full and never crossing

This is all. The answer is included in the definitions.


Why are random numbers important to the study and application of computer science? Why are random numbers important to the study and application of computer science? I am new to computer science. So I am studying random numbers right now.

There are a lot of applications of Random numbers in Computer science, there are full books about it, check Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan, for instance. There you will find many arguments for the case of random numbers.

Here is a not exhaustive list of applications in sub-fields of CS:

Algorithms (As Yuval pointed, there are many problems where only randomized algorithms are known and you will find that many times randomized algorithms are simpler and more efficient than their deterministic counterpart)
Machine Learning ( Generative algorithms, variational autoencoders, GANS, Bayesian inference, Monte-Carlo algorithms, ...)
Cryptography(randomized prime number testing, ...)
Computer graphics and simulation (Path Tracing, Procedural stuff, games, ...)
Big Data (search for sketching algorithms, probabilistic counting, Bloom filters, ...)
Optimization (stochastic gradient descend, meta-heuristics)
Simulation (random processes, multi-agent, stochastic differential equations,...)

I am sure there are plenty more.


Why postfix arithmetic expression is not ambiguous? A binary tree can be written as an expression, no matter prefix, postfix or infix.
But why an infix expression needs brackets, while the others don't?

Say, why postfix, prefix produce only one binary tree, while infix can produce many (and become ambiguous)?

I'm looking for a formal proof...

With operator precedence infix is not ambiguous.  Brackets are a convenience but not necessary to form an expression.  However when parsing you have to resolve each precedence level in precedence order (e.g., $^,[*,/],[+,-]$).

A postfix expression is written exactly in computation order:
$e0\ e1\ o1\ ... (ek\ ok) ... eN\ oN$
Computation is

$r[1] = o1(e0,e1)$
...
$rk = ok(r[k-1],ek)$
...
$rN = oN(r[N-1],eN)$

Infix is subjectively thought by many to be easier for humans to read and write.

There is no reason why brackets couldn't be added to postfix or prefix with the obvious meaning, but it is generally not done as those formats are intended for machines rather than humans.


How can Kruskal's algorithm return different spanning trees? We assume that we have the same graph G.

In introduction to Algorithms by Cormen it's said that it`s possible depending on how it breaks ties when the edges are sorted into order.

I have trouble visualizing the answer given:

  Suppose that A is an empty set of edges. Then, make any cut that has (u, v)
  crossing it. Then, since that edge is of minimal weight, we have that (u, v) is
  a light edge of that cut, and so it is safe to add. Since we add it, then, once
  we finish constructing the tree, we have that (u, v) is contained in a minimum
  spanning tree.

What does it mean to make a cut? I`m familiar with Kruskal's algorithm but nowhere in the process do I see cuts being made. It's either we unite two trees and add the edge to A or we reject the edge and continue on.

Cuts aren't made as part of Kruskal's algorithm; they are used in a proof that it always returns a minimum spanning tree. See e.g. here.

But you don't need them to answer the question in the title; instead, take as your graph a triangle with all 3 edges the same weight. Then any order on these edges is allowed and Kruskal's algorithm will return the tree consisting of the first 2 edges, whichever they are.


Why scholarly papers focus on DAGs instead of DCGs (Directed Cyclic Graphs) In trying to understand how to convert DCG's (Directed Cyclic Graphs) to DAG's (Directed Acyclic Graphs) without removing all the edges, I came across this paper which says:

  Since the problem involves DCG, therefore a new algorithm to reduce the DCG into the form of a DAG should be proposed. It is simpler when no cycle exists in a graph. A DCGSimplify algorithm is presented to reduce the graph from DCG to DAG.

Update

I am wondering what advantages you gain by removing cycles from your data structure. For example, maybe it allows you to traverse it easier during graph matching, or it makes it so you can generate a graph covering of some sort that's not possible with cyclic graphs. Basically I have noticed many papers talk about DAG's, even in relation to CFGs (Control-Flow Graphs) and data-flow graphs, which in practice always have cycles. They restrict it to DAGs for some reason, and don't address Directed Cyclic Graphs, which CFGs and such are most of the time. Wondering why this is, what advantage does DAGs have from a mathematical perspective or computer science perspective.

Let me mention one thing which is absent in the other answers: DAGs actually occur in applications. For example, a Boolean circuit is an ordered DAG whose vertices are labeled by logic gates. Dependencies of various sorts, like prerequisites for different parts of a project, also form a DAG. Wikipedia has many other examples.

Some problems can only be stated for DAGs. For example, topological ordering only makes sense for a DAG. Other problems can be solved faster on a DAG due to its restricted nature. This suggests studying algorithms on DAGs. For similar reasons, there is a lot of literature on algorithms for planar graphs – another naturally occurring class of graphs on which some algorithms run faster.


Efficient way to find matching date ranges? We have a set of problems involving date ranges - a pair of dates representing a start date and an end date. In some places, we have say 1000 of these and need to find the ones that overlap a separate set of 1000 of these. But a linear search is exponentially expensive.

So is there an algorithm that is more efficient? (For data related to a single date, using the date as the key of a hashmap works, but not much help when there is a pair of dates.)

(The source of the problem is my commercial work where there are a large number of date ranged payments that need to be matched with another large set of date ranged payments. And the environment the code runs in applies hard limits to how much CPU time can be consumed.)

Your question is not clear.

I am assuming you have 1000 date intervals in some set $A$ and another 1000 in set $B$ and you wish to find which intervals in $B$ lie completely inside some interval in $A$.

For an interval [x,y] in $B$, search points $x$ and $y$ in the segment tree built on $A$ and find sets that overlap.

Look up Segment tree.

Its stores line segments with starting point and end point.
You can modify it to store start date and end date.

https://en.wikipedia.org/wiki/Segment_tree


How does the Galil's rule work on Boyer-Moore algorithm? I would like to know how Boyer-Moore text searching algorithm with Galil's rule works,. I tried to search for but I couldn't understand the information I found, for example this Wikipedia page.
And why with this rule we go to a linear time complexity?

The algorithm is based on a simple principle. Suppose that we are trying to match a substring of length n. We are going to first look at character at index m. If that character is not in the string, we know that the substring we want can't start in characters at indices 1 2....n

If that character is in our string, we will assume that it is at the last place in our string that it can be. We will then jump back and start trying to match the string from that possible starting place. This piece of information is my first table.

Once I start matching from the beginning of the substring, when I find a mismatch, I can't just start from scratch. I could be partially through a match starting at a different point. For instance if I'm trying to match anand in ananand successfully match, anan, realize that the following a is not a d, but I've just matched an, and so I should jump back to trying to match my third character in my substring. This, "If I fail after matching x characters, I could be on the y'th character of a match" information is stored in the second table.

Note that when I fail to match the second table knows how far along in a match I might be based on what I just matched. The first table knows how far back I might be based on the character that I just saw which I failed to match. You want to use the more pessimistic of those two pieces of information.


Find Best N Points From a Graph I've given a task and wonder if there are any better solutions.

Inputs of task are:

Distance of district pairs
Population of pairs

Goal is:

Find n districts at which its population and districts x miles range districts' population is max.

Extra information:

Unique district size is tens of hundreds.

As an example, if I pick up district A, population will be A's population plus other districts' population which are less than x miles far away from it. Total population will be   n districts at which population is calculated as I mentioned.

What I've tried:

Brute Force
Generic Algorithms

What I planning to do:

A* Search

My question is, there may be any other solution (optimal if possible) instead of these one. i.e. sorting districts by their population, merging x miles nearest to them into one until I get n districts.

Any ideas?

If I understand the problem correctly, there is no polynomial-time algorithm that finds an optimal solution to your problem unless $\mathsf{P}=\mathsf{NP}$.
This holds even in the special case in which all distances are $1$, all populations are $1$, and $x=1$.

To see this notice that, given a graph $G=(V,E)$ and a non-negative integer $n \le |V|$, $G$ admits a dominating set of size at most $n$ if and only if there is a set $S \subseteq G$ with $|S| = n$ such that $\sum_{u \in V : d(u, S) \le 1} 1 = |V|$.

On the bright side, a simple greedy algorithm has an approximation ratio of $\frac{e}{e-1} < 1.582$: iteratively add to $S$ the district $v$ that maximizes the population that falls within distance $x$ of $S \cup \{ v \}$, i.e., the quantity $\sum_{u \in V : d(u, S \cup \{v\}) \ge x} p(u)$.

The approximation ratio of the above algorithm follows from the fact that you can cast your problem as a weighted maximum coverage problem.
In this problem you have a set $X$ of elements and a collection $\mathcal{S}$ of subsets of $X$.  Each element $v \in X$ has a non-negative weight $w(v)$. You are given an integer $k \le |S|$ and you want to select a subset $S$ of at most $k$ sets of $\mathcal{S}$ such that $\sum_{x \in \bigcup_{S' \in S} S' } w(x)$ is maximized.
To reduce your problem to weighted maximum coverage problem pick $X=V$, $\mathcal{S} = \{S_v \mid v \in V\}$ where $S_v = \{u \in V \mid d(u,v) \le x\}$, $w(v) = p(v)$, and $k=n$

Since you can also reduce any instance of weighted maximum coverage problem to your problem, this is essentially the best polynomial-time approximation algorithm that you can hope for. The reduction is as follows: Create a complete bipartite graph $G = (V,E)$ with $V = \mathcal{S} \cup X$ and $E = \mathcal{S} \times X$. Each edge in $E$ has weight $1$. The population $p(v)$ of a vertex $v \in V$ is $p(v) = 0$ if $v \in \mathcal{S}$, and $p(v) = w(v)$ if $v \in X$. Pick $n=k$ and $x=1$.
You can easily see that you can restrict yourself to a solution $S$ that does not select any district in $v \in X$ (since $S \setminus X$ is as good as $S$ and $|\mathcal{S}| \ge k = n$). Then, selecting a subset $S \subseteq \mathcal{S}$ of districts corresponds to covering all the elements in $\bigcup_{S' \in S} S' \subseteq X$, and the population within distance $x$ of a vertex in $S$ is exactly $\sum_{x \in \bigcup_{S' \in S} S'} p(x) =  \sum_{x \in \bigcup_{S' \in S} S'} w(x)$.


How to prove a problem is NOT NP-Complete? Is there any general technique for proving a problem NOT being NP-Complete?

I got this question on the exam that asked me to show whether some problem (see below) is NP-Complete. I could not think of any real solution, and just proved it was in P. Obviously this is not a real answer.

NP-Complete is defined as the set of problems which are in NP, and all the NP problems can be reduced to it. So any proof should contradict at least one of these two conditions. This specific problem, is indeed in P (and thus in NP). So I am stuck with proving that there is some problem in NP that can't be reduced to this problem. How on the earth can this be proven??

Here is the specific problem I was given on exam:

  Let $DNF$ be the set of strings in disjunctive normal form.
  Let $DNFSAT$ be the language of strings from $DNF$ that are satisfiable by some assignment of variables. Show whether or not $DNFSAT$ is in NP-Complete.

A problem $Q$ is NP-complete if it is both NP-hard and in NP.  This means that you need to disprove one of these two.

Under the assumption that P $\neq$ NP, you can give a polynomial time algorithm solving $Q$.  Rarer, under the assumption that graph isomorphism is not NP-hard, you can show that $Q$ is polytime reducible to graph isomorphism.
You show that $Q$ is not in NP.  This is harder, and you must usually use other assumptions, like non-collapse of polynomial hierarchy, that NP $\neq$ coNP or show that it is hard for some other class higher than NP, e.g. by showing that it is NEXPTIME-hard.

Usually, the answer is to give a polynomial time algorithm, which would be the simplest for DNF-SAT, but this relies on the hypothesis that P $\neq$ NP.  However, proving that DNF-SAT is not NP-complete without any assumptions implies, as Shaull points out, proving that P $\neq$ NP, so that is somewhat trickier.


Infinite Language vs. finite language I'm unclear about the use of the phrases "infinite" language or "finite" language in computer theory.

I think the root of the trouble is that a language like $L=\{ab\}^*$ is infinite in the sense that it can generate an infinite (but countable) number of strings. Yet, it can still be recognized by a finite state automaton.

It also doesn't help that the Sipser book doesn't really make this distinction (at least as far as I can tell). A question about infinite/finite languages and their relationship to regular languages came up in a sample exam.

Oh my. This seems like a confusion caused by the (old school) terminology of "finite-state language" as a synonym for what is known today as "regular language".

Anyways, the standard definitions for finite/infinite accepted these days regard only the size of the language:

a finite language is any set $L$ of strings, of finite cardinality, $|L|<\infty$.
an infinite language is any set $L$ of strings, of infinite ($\aleph_0$) cardinality $|L|=\infty$.

A finite $L$ is always regular.

An infinite $L$ can be regular (sometimes called "finite-state"), decidable (sometimes called "recursive"), non-regular (non-finite-state), non-decidable, etc.,


How to find recurrences where Master formula cannot be applied Given: $T(n) = T(\sqrt{n}) + 1$ (base case $T(x) = 1$ for $x<=2$)

How do you solve such a recurrence?

For the recurrence,
$$
T(n) = T(\sqrt{n}) + 1
$$
Let $n = 2^{2^{k}}$, therefore we can write the recurrence as:

$$
T(2^{2^{k}}) = T(2^{2^{k-1}}) + 1 \\
T(2^{2^{k-1}}) = T(2^{2^{k-2}}) + 1
\\\ldots\\\\\ldots\\
T(2^{2^{k-k}}) = 1
$$

, i.e. $ k * O(1) $ work or linear in $k$. We can express $k$ in terms of $n$:
$$
\log{n} = 2^{k} \\
\log{\log{n}} = k
$$

Hence, the recurrence solves $T(n) = O(\log{\log{n}}) $


Union of halting-like problem and non-halting-like problem I came across the following problem:

Define languages $L_0$ and $L_1$ as follows :
$L_0=\{⟨M,w,0⟩∣M\text{ halts on }w\}$
$L_1=\{⟨M,w,1⟩∣M\text{ does not halt on }w\}$
Here $⟨M,w,i⟩$ is a triplet, whose first component $M$ is an encoding of a Turing Machine, second component $w$ is a string, and third component $i$ is a bit.
Let $L=L_0∪L_1$. Which of the following is true?
A. $L$ is recursively enumerable, but $\overline{L}$ is not
B. $\overline{L}$ is recursively enumerable, but $L$ is not
C. Both $L$ and $\overline{L}$ are recursive
D. Neither $L$ nor $\overline{L}$ is recursively enumerable

I first felt that despite the bit as a third member of triple, $L_0$ is still equivalent to halting problem and $L_1$ is non halting problem. Union of halting and non halting problem is recursive as can be seen here. So, same will apply to the languages in the problem and their union will also be recursive, that is option C. But the answer given was D. So am guessing if its correct or not. I was not able to guess how that extra bit in the triple makes it different from halting problem.

Let's write formally what $L$ and $\overline{L}$ are:

$$L=\{\langle M,w,b \rangle| (b=0 \wedge M(w) \mbox{ halts}) \vee (b=1 \wedge M(w) \mbox{ does not halt}) \}$$

$$\overline{L}=\{\langle M,w,b \rangle| (b=1 \vee M(w) \mbox{ does not halt}) \wedge (b=0 \vee M(w) \mbox{ halts}) \}$$
The latter is confusing, so let's rearrange it:

$$\overline{L}=\{\langle M,w,b \rangle| (b=1 \wedge M(w) \mbox{ halts}) \vee (b=0 \wedge M(w) \mbox{ does not halt}) \}$$

(Note that we ignore malformed inputs, but that can be easily circumvented and does not effect the answer).

From this, you can easily see that $L$ and $\overline{L}$ are basically the same idea -- the bit at the end determines whether you're looking at the halting problem or at its complement. In either case, neither $L$ nor its complement are recursively enumerable.

One thing that can trigger you to suspect this is the answer, even without formally writing $\overline{L}$, is the fact that both the halting problem and its complement easily reduce to $L$. Thus, $L$ is not recongnizable nor co-recognizable, and so neither is its complement.


Is the complement of the language generated by $S \to aSbS|\epsilon$ context-free? How is it possible to prove whether the language $\{a, b\}^{∗} \setminus \{S → ε, S → aSbS\}$ is context free?

The first step is finding a simpler description of the language generated by the grammar $S \to aSbS \mid \epsilon$.
The second step is deducing a description of the complement, which is the language you're actually interested in.
Finally, in order to show that the language is context-free, you can consult our reference question on this topic.


Why pointer dereference was once called "decrement"? I'm reading McCarthy's paper Recursive Functions of Symbolic Expressions And Their Computation by Machine, where when the author describes the machine implementation of lists, he writes this:

  a. Representation of S-Expressions by List Structure. A list structure is a collection of computer words arranged as in figure 1a or 1b.  Each word of the list structure is represented by one of the subdivided rectangles in the figure.  The left box in the rectangle represents the address field of the word and the right box represents the decrement field.  An arrow from a box to another rectangle means that the field corresponding to the box contains the location of the word corresponding to the other rectangle.

From further reading it isn't clear why would he use the word "decrement" to mean "a pointer to a memory location where the data associated with the given list element is stored".  It doesn't exactly translate into "dereference" as used today when describing languages s.a. C, but if, in C terms, you were to treat the contents of "decrement" field as a pointer, and then dereference it, you'd get the value of the element.

So, why "decrement"?  Was something really decremented?  Was it due to some particular features of memory layout of IBM 704?

OK, I found a lead.  Just needed to know what to search for: https://en.wikipedia.org/wiki/CAR_and_CDR

  The 704 and its successors has a 36-bit word length and a 15-bit address space. These computers had two instruction formats, one of which, the Type A, had a short, 3-bit, operation code prefix and two 15-bit fields separated by a 3-bit tag. The first 15-bit field was the operand address and the second held a decrement or count. The tag specified one of three index registers. Indexing was a subtractive process on the 704, hence the value to be loaded into an index register was called a "decrement".[2]:p. 8 The 704 hardware had special instructions for accessing the address and decrement fields in a word.[2]:p. 26 As a result it was efficient to use those two fields to store within a single word the two pointers needed for a list.[3]:Intro.

Still, this memory model is very foreign to me, so I wouldn't mind if anyone explained how this would work.


What is the expected number of nodes at depth d of a tree after i random insertions Suppose one wanted to build a tree at random.  Let the first insertion at step $i = 1$ be the root node.  From here, nodes are inserted into the tree at random one at a time.  How would one go about calculating the expected number of nodes $E(d)$ at depth $d$ after $i$ insertions?

For example, At $i = 1$, it's just the root node, so $E(0) = 1$ and all other depths will have zero nodes.  At $i = 2$, $E(0) = 1$ and $E(1) = 1$ as the inserted node has to be at depth 1 from the root.  At $i = 3$, the next node may either be attached to the root node or the existing node at depth one, so the tree may either look like:

    *
   / \
  *   *

Or:

     *
    /
   *
  /
 *

Depending on what happend at $i = 3$, at $i = 4$ there's either a $2/3$ chance of the new node attaching at depth 2 and $1/3$ attaching at depth 1, or an even $1/3$ probability of the new node attaching at the root, the node at depth 1 or the node at depth 2.  Keeping random insertion in mind (not a binary or balanced tree in any way), how would one go about calculating the expected number of nodes at depth $d$ after $i$ insertions?

Let $X_{d,t}$ denote the expected number of nodes at level $d$ and time $t$, and let $p_{d,t}$ be the probability that at time $t$, a node is added at level $d$. Our indexing is such that $p_{0,0} = X_{0,t} = 1$. Clearly
$$ X_{d,t} = \sum_{s=0}^t p_{d,t}. $$
Suppose that at time $t-1$, the number of leaves at depth $d-1$ is $X$. Then the probability that at time $t$ a leaf is added at depth $d$ is $X/t$. The expectation of this across the first $t-1$ steps is exactly $X_{d-1,t-1}$, and so
$$ p_{d,t} = \frac{X_{d-1,t-1}}{t}. $$
Therefore
$$ X_{d,t} = \sum_{s=1}^t \frac{X_{d-1,s-1}}{s}. $$
What does this look like? Let's use generating functions:
$$ P_d(z) = \sum_{t=0}^\infty X_{d,t} z^t = \sum_{t=0}^\infty \sum_{s=1}^t \frac{X_{d-1,s-1}}{s} z^t = \sum_{s=1}^\infty \frac{X_{d-1,s-1}}{s} \sum_{t=s}^\infty z^t = \sum_{s=1}^\infty \frac{X_{d-1,s-1}}{s} \frac{z^s}{1-z}. $$
Notice that
$$
\int_0^z P_{d-1}(w) dw = \sum_{s=1}^\infty X_{d-1,s-1} \int_0^z w^{s-1} dw = \sum_{s=1}^\infty X_{d-1,s-1} \frac{w^s}{s}.
$$
Therefore
$$
P_d(z) = \frac{1}{1-z} \int_0^z P_{d-1}(w) dw, \quad P_0(z) = \frac{1}{1-z}.
$$
We can calculate
$$
\begin{align*}
P_0(z) &= \frac{1}{1-z} \\
P_1(z) &= \frac{-\log (1-z)}{1-z} \\
P_2(z) &= \frac{1}{2} \frac{\log^2(1-z)}{1-z} \\
P_3(z) &= \frac{1}{6} \frac{-\log^3(1-z)}{1-z}
\end{align*}
$$
A pattern becomes apparent, and is easy to prove by induction:
$$ P_d(z) = \frac{1}{d!} \frac{\log^d (1-z)^{-1}}{1-z}. $$
We can pack all this data into a bivariate generating function:
$$ P(z,w) = \sum_{d \geq 0} X_{d,t} z^t w^d = \frac{\exp (w\log (1-z)^{-1})}{1-z} = (1-z)^{-w-1}.$$
In principle, we can compute $X_{d,t}$ asymptotically from the generating functions; but it is easier to do this directly:
$$
\begin{align*}
X_{0,t} &= 1 \\
X_{1,t} &= \sum_{s=1}^t \frac{1}{s} = \log t + O(1) \\
X_{2,t} &= \sum_{s=1}^t \frac{\log s + O(1)}{s} = \int_1^t \frac{\log s + O(1)}{s} ds + O\left(\frac{\log t}{t}\right) = \frac{\log^2 t}{2} + O(\log t) \\
X_{3,t} &= \sum_{s=1}^t \frac{\log^2 s + O(\log s)}{2s} = \int_1^t \frac{\log^2 s + O(\log s)}{2s} ds + O\left(\frac{\log^2 t}{t}\right) = \frac{\log^3 t}{6} + O(\log^2 t)
\end{align*}
$$
Generalizing, we get
$$X_{d,t} = \frac{1}{d!} \log^d t + O(\log^{d-1} t).$$
With more work, it is possible to obtain lower order terms as well, indeed a polynomial in $\log t$ followed by a Laurent series.


Name of binary encoding scheme for integer numbers I once found on Wikipedia a nice technique for encoding $k \in (2^{n-1}, 2^n)$ uniformly distributed integer numbers with less then $\log_2n$ average bits/symbol, thanks to a simple to compute variable length code. Basically it used $\log_2n$ for some symbols and $\log_2n - 1$ for some others.

Unfortunately all my Googling has failed me. I recall something similar to "variable length binary", but I keep ending on VLQ which are a different beast. Since I know your memory better than mine, can you help me?

The technique idea is perfectly described in Yuval Filmus answer. Even if slightly different, it is called Truncated binary encoding in Wikipedia. I couldn't find an original source for that, apart from a mention in a patent, in this book, or in this Google API
Another mention can be found in the ACM ICPC 2011–2012, Northeastern European Regional Contest, November 27, 2011.


expected length of linked list Consider a datatype whose objects will be sequences of elements that has the following two methods

prepend($x, T$) which will insert an element to x to the beginning of the sequence T

search($T, i$) which returns the ith element in the given sequence

T is a linked list. prepend takes $1$ step. Search takes $i$ steps

Suppose T has exactly one element and a sequence of n operations are performed. You are given that prepend has probability $p$ and search has probability $1-p$ for each operation. The value of $i$ is chosen uniformly from $[1, \dots, T]$

Q) Derive the expected length for the linked list just before the k'th operation is performed

so we need the weighted average of all possible values of some random variable. for each $X_i$ let it be the number of steps for given events. If theres a prepend we add a node whereas if theres an access we do nothing to the length. How do we come up with an equation for expectd length?

$E(X) = something \cdot (k-1)$ since just before $k$ but not sure how to derive the probability yet

Any help appreciated

$E(X) = something \cdot (k-1)$

That $something$ is $p$. The full formula should be $E(Y)=1+p(k-1)$, where $Y$ is the random variable that is the length for the linked list just before the $k$-th operation is performed.

To convince yourself that $p$ is the right answer, try a few cases. When $p=1$, every operation adds one element to $T$. When $p=0$, no prepend operation will happen. When $p=1/2$, an element is added about half of the times. Make sense?

Here is the simple reason why. Let $Y_i$ be the increase of length in step $i$. Then

$Y_1, Y_2, \cdots, Y_n$ are independent random variables,
$E(Y_i)=p$ for all $i$ since the probability of prepending is $p$ for each operation.

Since the expectation of the sum is the sum of the expectations for independent variables, we have
$$\begin{align}
E(Y)
&=E(1+ Y_1+ Y_2+ \cdots+ Y_{k-1})\\
&=1+ E(Y_1)+E(Y_2)+\cdots+E(Y_{k-1})\\
&=1+ p(k-1)
\end{align}$$
where 1 comes from the initial one element in $T$.


Is there a "natural" example of a total, computable but non-primitive recursive function? Every example of a total, computable but non-primitive recursive function seems to be explicitly constructed for proof theory, or in Godelian proofs of "what is the name of this book?" kind. But is there a non-primitive recursive function or algorithm that occurs naturally, like in physics or number theory or even in industry software?

This answer gives us a hint, namely that an interpreter for a language more powerful than primitive recursion, is itself not primitive recursive. For example, System F has no self-interpreter, and thus any interpreter for System F is not self-recursive.

This then extends to Turing-complete languages: JavaScript, Python, Ruby, etc. Any interpreter you run is utilizing functions more powerful than primitive recursion.


An FPT algorithm for Hamiltonian cycle running parameterized by treewidth I'm looking for an algorithm that solves the Hamiltonian cycle problem parameterized by treewidth. In particular, I'm curious about such an algorithm running in $\text{tw}(G)^{O(\text{tw}(G))} \cdot n$ time.

In other words, once you have the treewidth, an algorithm that says if the input graph has a Hamiltonian cycle.

If you want an FPT algorithm for the problem (parameterized by treewidth $t$), you want an algorithm working in time $f(t) \cdot n^{O(1)}$, where $f$ is any computable function (depending solely on $t$). Of course, it would be nice to make $f$ as appealing as possible.

In addition to the mentioned algorithm running in $O(t^t n)$ time, you can also get a faster (randomized) algorithm using the Cut'n'Count technique of Cygan et al. [1]. In particular, you get an algorithm running in time $4^t n^{O(1)}$. It is also possible to get a deterministic algorithm working in $c^t n^{O(1)}$ (for some small constant $c$) using a rank-based approach of [2].

[1] Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J. M., & Wojtaszczyk, J. O. "Solving connectivity problems parameterized by treewidth in single exponential time." IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011.

[2] Bodlaender, H. L., Cygan, M., Kratsch, S., & Nederlof, J. "Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth." Automata, Languages, and Programming. Springer Berlin Heidelberg, 2013. 196-207.


Minimum edge weight k-exact cover with triangle inequality Suppose you have a weighted graph $G = (V, E \subseteq V^2, w \in E \to \mathbb{R}^+)$, where $w$  satisfies the triangle inequality $w(x, y) + w(y, z) \ge w(x, z)$. Suppose $k \in \mathbb{N}$ (in practice, $k \le 6$ is common). I want to find a set $C \subseteq \mathbb{P}(V)$ (a set of subsets of $V$) such that:

$\max_{I \in C} \sum \{w(x, y) \mid x \in I \wedge y \in I\}$ is minimized.
For all $I \in C$, $\mathrm{card}(I) = k$.
No two elements of $C$ have nonempty intersection.
The union of all elements of $C$ is $V$.

Assume that $\mathrm{card}(V) = r \cdot k$ for some $r \in \mathbb{N}$.

Is there a polynomial-time approximation algorithm for this task?

I believe this problem is related to facility location problems, but I am not sure.

Let $n := |V| = rk$ be the total number of vertices in the graph. Basically, we are looking for a partition of $V$ into $r$ sets each of size $k$. The total cost will be then the sum of the weights of all edges present in the graph induced by each of these sets. Note that the edges having one end in one of these sets and the other endpoint in another set form together an $r$-cut and are exactly the edges we do not count in our sum. Hence, instead of minimizing the sum of edges in the subgraphs induced by the sets of the partition, we can maximize the weights of edges having one end in a set of the partition and the other end in a different set.

Note that we are looking here at a special variation of maximum $k$-cut, where we require that all the subsets of the partition have equal sizes and hence the problems are not completely equivalent. However, it is not hard to reduce the maximum $k$-cut problem (let us call it for now maximum $s$-cut to avoid confusion) to your problem, where given an instance of the $s$-cut problem (with $N$ vertices), you can add $(s-1)N$ additional vertices to the graph and connect each of them with all vertices in the graph with edges of weight 0. Set $k = N$ (note that $n = sN$) and hence, we will have $r = s$. Each solution to your problem corresponds to a solution to the maximum cut problem with dummy vertices assigned arbitrarily to make the count consistent.

The maximum cut problem is APX-hard and hence does not admit PTAS (polynomial time approximation scheme) unless P=NP. Using the previous reduction, and since the maximum cut problem is a special case of the maximum $k$-cut problem, your problem is at least as hard as the maximum cut problem.


NP-complete and polynomial time reduction A decision problem is NP-complete if it is in NP and all other problems in NP can be reduced to it by a reduction that runs in polynomial time. Why it is important to require that the reduction runs in polynomial time, as opposed to accepting any computable reduction.

If there is no resource bound for the reduction and you want to reduce problem A to problem B then there is a trivial "reduction" algorithm for any computable A - simply compute the answer for problem A.


Trapezoidal decomposition of a graph When we plan the motion of a robot we may apply the trapezoidal
decomposition of free space.  While applying the trapezoidal
decomposition we add nodes to both the centers of trapezoids and
vertical walls.
When a robot wants to traverse between obstacles it avoids the obstacles
by following the nodes added.  The nodes create a graph which provides a
smooth traverse between the obstacles (at least so we assume).  In this
case we assume that we are creating a graph using all nodes.
Is it possible to plan a graph with only using the center of trapezoid
or the center nodes of vertical walls?
My idea is; it depends on the situation (the position of obstacles, the
shape of the robot etc.)  But I could not image such graph which could
be changed to a new graph with only using the nodes on the vertical
walls. If we design the example do we need to increase the number of
edges?
I think it is not necessity to increase the number of edges to manage to
use only vertical walls' nodes, but I could not figure out how it could
be possible exactly.

In order to get valid paths in the free space from paths in the graph $G=(V,E)$ that is constructed via the trapezoidal decomposition, we require that all edges of $G$ lie inside the free space.
The segment between two centers of adjacent trapezoids is not always fully contained inside the free space. For example, consider a square and take a slightly smaller square with the same center as the obstacle. So, using only the nodes at the center of the trapezoid is not sufficient to find paths in the free space.
On the other hand, any segment between a pair of nodes centered at a vertical boundary of the same trapezoid is fully inside the free space, since trapezoids are convex. So, the graph $G'=(V',E')$ with as vertices the centers of the vertical boundaries with an edge between every pair of vertices that lies on the boundary of the same trapezoid lies fully within the free space.

So, why bother using the graph $G$ and not $G'$? One issue with $G'$ is that a trapezoid with $d$ adjacent trapezoids means $G'$ has the complete graph on $d$ nodes as a subgraph, which has $\Theta(d^2)$ edges. So in the worst case, finding a path in $G'$ takes at least $\Omega(n^2)$ time, where $n$ is the number of  in the decomposition. On the other hand, $G$ has at most $2$ edges for each vertical trapezoid boundary, so at most two per vertex of the obstacle boundary, which means it has $O(n)$ edges and we can find shortest paths in $O(n\log n)$ using Dijkstra.


Given a set of integers $D$ and a positive value$P$, find an algorithm to find set of integers satisfying a condition Given a set of positive integers :

$ \\ D = \{ D_1, D_2, ..., D_n\}$

and a non-negative integer $P$, where $P$ is divisible by every element in $D$, then find a set of non-negative integers:

$C = \{ C_1, C_2,..., C_n\}$

such that

$S > P $

where
$S = \displaystyle \sum_{i = 1}^nC_iD_i$
and for all $i$ where $C_i > 0 $,

$\ S - D_i < P$

There can be multiple solutions, any solution can suffice.

For example, if

$D = \{2, 6, 9 \}$
$P = 18$

$ C $ can be:

$C = \{0, 2, 1 \}$

since $ S = 0*2 + 2*6 + 1*9 = 21 > 18 $
and $ 21 - 6 = 15 < 18 $ and $ 21 - 9  = 12 < 18 $

What can be some approaches to tackle this?
For starters, is there a way to ensure that there even exists a solution? There can be examples where there is no solution.

If all of $D$ divide $P$, then $P$ is also multiple of $\gcd(D)$.
Any sum like $S$ is a multiple of $\gcd(D)$ too, so you can divide everything by $\gcd(D)$ and consider just the case where the $D_i$ are relatively prime. For definiteness, take $D$ sorted in increasing order.
In that case you have just:

$\begin{equation*}
  P
    = c \cdot \prod_{1 \le k \le n} D_k
\end{equation*}$

For the Frobenius problem sums like $S$ with non-negative $C_i$ can represent all numbers greater than a function $g(D)$, and it can be shown that $g(D) < D_n^2$ (computing the exact value of $g(D)$ is NP-complete). So, if $P > D_n^2$ (the other $D_k$ would have to be small indeed for this to be false), any number $S \ge P$ can be represented, and also any number $S - D_i$, pick say $S = P + 1$ to satisfy your condition.

To get a set of $C_i$, you can now use the greedy algorithm: Take $C_n = \lfloor S / D_n \rfloor$ (as large as possible), $S \leftarrow S - C_n D_n$, and repeat for the next largest.


How do I prove that Context Free languages have more memory than FSM This is very much clear to me that an FSM has limited memory (sufficient to store present state). How do I prove that (intutively or otherwise) that a CFL has more memory than a DFA or NFA (thus making a CFL more powerful than FA) ?

There's a small mistake in your question.

The FSM (DFA or NFA) are machines that accept regular languages.

the CFL is also a language.

They are accepted by a machine called PDA (PushDown Automata) which you can think of as a generalization of the a DFA/NFA.

A PDA is like a NFA but in addition, it also has a stack. So it can accept (context free) languages like $L = \{0^p1^p | p \geq 0\}$

Its fairly easy to show that the PDA is more powerful than DFA.. (see it accepts $L$ that the DFA cannot)

We will show something stronger, i.e. formally define the construction of the PDA that will show that any language accepted by some DFA is also accepted by some PDA .

a PDA is 6 tuple $(Q, \Sigma, \Gamma, \delta, q_0, F )$, where,

$Q$ is the set of states
$\Sigma$ is the input alphabet,
$\Gamma$ is the stack alphabet,
$\delta$ is the transition func. $\delta:(Q \times \Sigma_\epsilon \times \Gamma_\epsilon) \rightarrow \mathcal{P}(Q\times \Gamma_\epsilon)$ ,
$q_0 \in Q$,
$F \subseteq Q$

now observe that a DFA/NFA is just the same thing where $\Gamma$ is always 'empty'.


Maximum value of LOOP-Program turing-computable Lets consider the class of "simple" LOOP-Programs.

A LOOP-Program P is inducively defined as:

$P_1: x_i = x_j$ and $P_2:x_i = x_i +1$ are LOOP-Programs. We also define a length property $l(P)$  where $l(P_1) = l(P_2) = 1$

P: $P_1;P_2$ is also LOOP. (sequential execution of statements). The length of these programs is $l(P) = l(P_1)+l(P_2)$

P: $LOOP\ \  x_I \ \  DO  \ \ P_1 \ \ END $ (execute P a fixed amount of times, this program will execute P  exactly $x_i$ times.) The length of this program is $l(P) = l(P_1)+1 $

The input of a LOOP-Program is passed as as $f(n_1 \cdots n_k) \rightarrow x_1 \cdots x_k$ and the output is alsways stored in $x_0$

Lets further consider $S(n)$ the function which computes the maximum value of a simple LOOP-Program of maximum length $n$ with input $n$.

It is known that $S(n)$ is not LOOP-computable. ( can write proof if needed)

The question stands wether $S(n)$ is Turing-computable.

First we can note down the following theorems:

a LOOP-Program always halts after a finite amount of steps.
a function is turing-computable if a Turingmachine $M$ exists which computes $S(n)$ given the input $n$ after a finite amout of steps.

My solution to the question wether $S(n)$ is turing-computable is:

We construct a TM $M$ which enumerates all LOOP-Programs of length $n$ onto the tape.:

We know this is possible because there is only a finite amount of LOOP-Programs of length $n$ using the variables $x_1 \cdots x_{2n}$.
We will use a suitable encoding method  which encodes a LOOP-Program syntactically onto the tape.

This step of the algorithm will halt after a finite amount of steps.

Then we simulate the LOOP-Programs on the tape and write the results onto the tape. This step also terminates after a finite amount of steps.

We then have the output of every single LOOP-program of length $n$ with input $n$ on the tape and we know we can find the largest value in a finite amount of steps.

Thus $S(n)$ is computable.

My question is: does my answer hold up and can one poke any holes in this logic ?


Contradiction proof for inequality of P and NP? I'm trying to argue that N is not equal NP using hierarchy theorems. This is my argument, but when I showed it to our teacher and after deduction, he said that this is problematic where I can't find a compelling reason to accept.

  We start off by assuming that $P=NP$. Then it yields that $\mathit{SAT} \in P$ which itself then follows that $\mathit{SAT} \in TIME(n^k)$. As stands, we are able to do reduce every language in $NP$ to $\mathit{SAT}$. Therefore, $NP \subseteq TIME(n^k)$. On the contrary, the time hierarchy theorem states that there should be a language $A \in TIME(n^{k+1})$,  that's not in $TIME(n^k)$. This would lead us to conclude that $A$ is in $P$, while not in $NP$, which is a contradiction to our first assumption. So, we came to the conclusion that $P \neq NP$.

Is there something wrong with my proof?

Then it yields that $SAT \in P$ which itself then follows that $SAT \in TIME(n^k)$.

Sure.

  As stands, we are able to do reduce every language in $NP$ to $SAT$. Therefore, $NP \subseteq TIME(n^k)$.

No. Polynomial time reductions aren't free. We can say it takes $O(n^{r(L)})$ time to reduce language $L$ to $SAT$, where $r(L)$ is the  exponent in the polynomial time reduction used. This is where your argument falls apart. There is no finite $k$ such that for all $L \in NP$ we have $r(L) < k$. At least this does not follow from $P = NP$ and would be a much stronger statement.

And this stronger statement does indeed conflict with the time hierarchy theorem, which tells us that $P$ can not collapse into $TIME(n^k)$, let alone all of $NP$.


Compactly representing integers when allowed a multiplicative error Consider the problem of representing in memory numbers in the range $\{1,\ldots,n\}$.

Obviously, exact representation of such number requires $\lceil\log_2(n)\rceil$ bits.

In contrast, assume we are allowed to have compressed representations such that when reading the number we get a 2-approximation for the original number. Now we can encode each number using $O(\log\log n)$ bits. For example, given an integer $x\in\{1,\ldots,n\}$, we can store $z = \text{Round}(\log_2 x)$. When asked to reconstruct an approximation for $x$, we compute $\widetilde{x} = 2^z$. Obviously, $z$ is in the range $\{0,1,\ldots,\log_2 n\}$ and only requires $O(\log\log n)$ bits to represent.

  In general, given a parameter $\epsilon>0$, what is the minimal number of bits required for saving an approximate representation of an integer in the above set, so that we can reconstruct its value up to a multiplicative error of $(1+\epsilon)$?

The above example shows that for $\epsilon=1$, approximately $\log\log n$ bits are enough. This probably holds asymptotically for every constant $\epsilon$. But how does epsilon affect the memory (e.g., does it require $\Theta(\frac{1}{\epsilon^2}\log\log n)$ bits?).

Storing $x$ to within a $1+\epsilon$ approximation can be done with $\lg \lg n - \lg(\epsilon) + O(1)$ bits.

Given an integer $x$, you can store $z = \text{Round}(\log_{1+\epsilon} x)$.  $z$ is in the range $\{0,1,\dots,\log_{1+\epsilon} n\}$, so requires about $b = \lg \log_{1+\epsilon} n$ bits.  Doing a bit of math, we find

$$b = \lg \frac{\lg n}{\lg(1+\epsilon)} = \lg \lg n - \lg \lg (1+\epsilon).$$

Now $\lg(1+\epsilon) = \log(1+\epsilon)/\log(2) \approx \epsilon/\log(2)$, by a Taylor series approximation.  Plugging in, we get

$$b = \lg \lg n - \lg(\epsilon) + \lg(\log(2)),$$

which yields the claimed answer.


What are the sufficient conditions for a grammar to be unambiguous? There is no algorithm that, given an arbitrary grammar, decides if it's ambiguous or not. However, Are there any sufficient conditions that make it easier to tell that a grammar is unambiguous?

For example, if I'm not mistaken, it can be algorithmically checked if a grammar contains no conflicts under LR(1), LALR(1) or LL(1); if so, is there any  implication like "If the grammar has no conflicts under LL(1) then it is unambiguous" or something like that?

If you can construct a deterministic parser corresponding to a grammar, then the grammar is clearly the unambiguous. (If it were ambiguous, there would need to be a point in some parse which admitted more than one parse action, violating the presumption of determinism.)

All of the algorithms you mention for constructing a parser either produce a deterministic parser for a grammar or report conflicts. So the absence of conflicts implies unambiguity.

Note that there might exist parsing algorithms which produce parsers which do not precisely correspond to the grammar. For example, yacc/bison use an algorithm which resolves conflicts, either using precedence declarations or through some default resolution rules. The resulting parser is then unambiguous, but it is no longer capable of producing the same set of derivations as the original grammar. Indeed, it might not even be able to recognise the same sentences.


Why classes implicitly derive from only the Object Class? I do not have any argument opposing why we need only a single universal class. However why not we have two universal classes, say an Object and an AntiObject Class. In nature and in science we find the concept of duality - like Energy & Dark Energy; Male & Female; Plus & Minus; Multiply & Divide; Electrons & Protons; Integration & Derivation; and in set theory. There are so many examples of dualism that it is a philosophy in itself. In programming itself we see Anti-Patterns which helps us to perform work in contrast to how we use Design patterns. I am not sure, but the usefulness of this duality concept may lie in creating garbage collectors that create AntiObjects that combine with free or loose Objects to destruct themselves, thereby releasing memory. Or may be AntiObjects work along with Objects to create a self-modifying programming language - that allows us to create a safe self modifying code, do evolutionary computing using genetic programming, do hiding of code to prevent reverse engineering.

We call it object-oriented programming. Is that a limiting factor or is there something fundamental I am missing in understanding the formation of programming languages?

This is only an answer to answer the question in the title.

Languages such as Java have every class deriving from Object for two reasons.

Firstly, to increase the amount of polymorphism available. This was particularly required before generics were added to the language. Without Object,  collection classes would be impossible to write in a useful fashion.

Secondly, there are many methods that classes are expected to have or are useful, and these are collected in Object. By ensuring that all classes inherit from Object, all classes will implement  the same minimal interface.

As mentioned in a comment, C++ does not have a class like Object. C++ is in many ways untyped, so the issues I mention above are not applicable. Also, C++ templates provide a lot of polymorphism and are used to implement collections.


Why is low-dimensional discrete representation of input space useful? Self-organizing maps undergo unsupervised training to produce a low-dimensional, discrete representation of the input space. Why is this useful?

I think the results of the self-organizing map would have to be combined with some other machine learning algorithm or neural net in order to solve problems. Is this the case? If so, what algorithms or neural networks would benefit from being complemented with a self-organizing map? If not, what problems does the output of a self-organizing map solve?

It may or may not be useful, depending upon the circumstances.

In some cases it can be useful as a visualization technique.  The representation is low-dimensional, and often 2-dimensional -- which means it can be visualized.  That said, there are many other methods of representing data in a low-dimensional space so it can be visualized, and it's not clear that self-organizing maps are the best way to do that.

Sometimes self-organizing maps are used as a general form of clustering, and can be useful anywhere that (unsupervised) clustering is useful.

That said, I agree with your general reaction.  Often, self-organizing maps aren't very useful.  I would not expect neural networks or other algorithms to benefit from being combined with self-organizing maps.  Self-organizing maps don't really solve any clearly defined problem, and probably aren't of all that much use in many/most practical situations.

If you had never heard of self-organizing maps, you probably wouldn't be missing much (in my personal opinion).


Which potential function does this algorithm minimize or maximize? Considering two sets $A, B$ containing some $p$-dimensional points $x \in \mathbb{R}^p$. Let $d_x^S = \min_{x' \in S \setminus \{x\}} \lVert \mathbf{x} - \mathbf{x'} \rVert$ denote the Euclidean distance from $x$ to its nearest point in $S$. We have a very simple algorithm:

$\forall x \in A$, if $d_x^A > d_x^B$ then move $x$ from $A$ to
$B$.
$\forall x \in B$, if $d_x^A < d_x^B$ then move $x$ from $B$ to
$A$.
Repeat (1) and (2) until convergence

Convergence is when there is no more $x \in A$ such that $d_x^A > d_x^B$, and there is no more $x \in B$ such that $d_x^A < d_x^B$.

How could I figure out which function does this algorithm minimize or maximize at each iteration ? The function $\Phi(A)+\Phi(B) = \sum_{x \in A} d_x^A + \sum_{x \in B} d_x^B$ does not seem to decrease at each iteration.

Note: another version of this algorithm is when we define $d_x^S$ as the mean distance from $x$ to its $k$ nearest points in $S$, instead of the distance to its nearest point in $S$. I don't know if $k > 1$ would make the proof more complicated or not.

It takes at most $|A \cup B|$ iterations until convergence. Consider the directed graph $D(V,E)$ with a vertex $v \in V$ for each point
 $p_v \in (A \cup B)$ and a directed edge $(u,v) \in E$ such that $p_v, v \neq u$ is the nearest point to $p_u$ (connect each point to its nearest neighbour point).

If points $p_u$ and $p_v$ are each other's nearest then
 $(u,v),(v,u) \in E$. On the other hand, there is no cycle consisting of more than two edges. For contradiction assume the corresponding points in such a cycle as $p_0,p_1,...,p_k,p_{0}$. Since each $p_{((i+1) \bmod k)}$ is the nearest point to $p_i$ the distances decrease as we go along the cycle. This means that $p_k$ is closer to $p_0$ than $p_1$ and by construction this is not possible. A cycle of length three or more could cause an infinite chain of label changes (switching between labels $A$ and $B$).

The out degree of vertices in $D$ is exactly one, and in any path the last vertex have an out edge to its previous vertex in that path (because they are mutually each other's nearest). So the last vertex change label at most once, in the first iteration. Then its label propagates backward along all the path ending at this vertex until all the vertices in those paths receive this label.

Therefore, at each iteration, at least one vertex in any path gets its final label. So the number of iterations is the length of the longest path in $D$  which is at most $|V|-1$.


Can we prove that $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ using a computer program? Chapter 7 of The Haskell Road to Logic Math and Programming discusses induction and recursion.

Haskell is strongly typed and we can define the natural numbers

data Natural = Z | S Natural
deriving (Eq, Show)

and we can try to construct addition

plus m Z = m
plus m (S n) = S (plus m n)

Can we write a program that proves that addition is associative $(a+b)+c = a+(b+c)$?
Can we prove that $1 + 2 + \dots + n = \frac{n(n+1)}{2}$?

Is it possible to write a program (e.g. in Haskell) that proves the equivalence of two other programs?

https://stackoverflow.com/questions/4077970/can-haskell-functions-be-proved-model-checked-verified-with-correctness-properti

  Model-checking a general purpose language is neigh impossible since models must be domain specific to be practical. Due to Gödel's Incompleteness Theorem, there simply is no method for automatically finding proofs in a sufficiently expressive logic.

  This means that you have to write proofs yourself, which raises the question of whether the effort is worth the time spent. Of course, the effort creates something very valuable, namely the assurance that your program is correct. The question is not whether this is a must-have, but whether the time spent is too great a cost. The thing about proofs is that while you may have an "intuitive" understanding that your program is correct, it is often very difficult to formalize this understanding as a proof.

This blog says associativity and other simple statements can be proven in Haskell using the Curry-Howard correspondence.  Not entirely sure what that is.

https://jeltsch.wordpress.com/2012/04/30/dependently-typed-programming-and-theorem-proving-in-haskell/

assoc :: Nat nat1                                          ->
         Nat nat2                                          ->
         Nat nat3                                          ->
         (nat1 :+ nat2) :+ nat3 :== nat1 :+ (nat2 :+ nat3)
assoc Zero        nat2 nat3 = Refl
assoc (Succ nat1) nat2 nat3 = case assoc nat1 nat2 nat3 of
                                  Refl -> Refl

The program compiles and therefore the proof works.

Apologia

I am an experience mathematicians, but I am new to how programmers and CS people think about proofs and theorem-proving.  So please excuse me if I confuse one branch of math for the other.

In order with the explicit questions:

Yes
Yes
No

To answer the question I think you're attempting to ask, we can prove many things using type checking, but not everything. What does this have to do with programs? That's what the Curry-Howard correspondence tells us. The Curry-Howard correspondence is a relationship between logic and computational models. The informal version is "proofs and programs and programs are proofs". While the specifics are far too much to detail here, the rough idea is that a function (read program) that takes an input of type $A$ and produces an output of type $B$ is a proof that $A \rightarrow B$ (and yes the funtion type arrow maps to the logical implication arrow).

Why can't we do everything? The good old halting problem. Some things we just can't check. Even worse, in practice, we're often limited to things we already know we can check, i.e. programs that are of a subclass that we know always halt.

Just to give a more complicated example, I've written a proof/program for $1+\ldots n = \frac{n\cdot(n+1)}{2}$ in Coq. Coq is a bit different to Haskell, but the idea should be fairly apparent. In this case, Coq has the advantage that it's explicitly built for theorem proving, so we can get a "proof-like" version and a "program-like" version. The proof can only complete if all the types match correctly - i.e. if we can specify a way to get from the input type to the output type, in the normal type checking sense. To avoid using division, I've rephrased the lemma.

The proof-like version:

Fixpoint sum (n : nat) : nat :=
match n with
| 0 => 0
| S n' => n + sum n'
end.

Lemma sum_closed_form (n : nat) : 2 * sum n = n * (n + 1).
Proof.
  induction n.
  reflexivity.
  assert (Step: sum (S n) = S n + sum n).
    reflexivity.
  rewrite Step.
  rewrite mult_plus_distr_l.
  rewrite IHn.
  assert (Id : S n = n + 1).
    omega.
  rewrite Id.
  repeat rewrite mult_plus_distr_l.
  repeat rewrite mult_plus_distr_r.
  omega.
Qed.

So apart from the individual steps being black boxes, it's fairly clear that this looks a lot like a normal proof - it is in fact an induction, and all the mystery black boxes are in fact just other proofs that allow us to take some input type to another. One of the key steps in understanding how this works is to look closely at statement of the lemma: Lemma sum_closed_form (n : nat) : 2 * sum n = n * (n + 1).

Notice that it looks a bit like a function declaration, it takes a parameter of type nat, and produces an output of type 2 * sum n = n * (n + 1). That is in fact what it is, so in this form we can see the proof bit, and get an idea of the function bit - i.e. the proof is in fact a program. More explicitly, it is this program:

sum_closed_form =
fun n : nat =>
nat_ind (fun n0 : nat => 2 * sum n0 = n0 * (n0 + 1)) eq_refl
(fun (n0 : nat) (IHn : 2 * sum n0 = n0 * (n0 + 1)) =>
(fun Step : sum (S n0) = S n0 + sum n0 =>
eq_ind_r (fun n1 : nat => 2 * n1 = S n0 * (S n0 + 1))
(eq_ind_r (fun n1 : nat => n1 = S n0 * (S n0 + 1))
(eq_ind_r (fun n1 : nat => 2 * S n0 + n1 = S n0 * (S n0 + 1))
((fun Id : S n0 = n0 + 1 => eq_ind_r
(fun n1 : nat => 2 * n1 + n0 * (n0 + 1) = n1 * (n1 + 1))
(eq_ind_r (fun n1 : nat =>
n1 + n0 * (n0 + 1) = (n0 + 1) * (n0 + 1 + 1))
(eq_ind_r (fun n1 : nat =>
2 * n0 + 2 * 1 + n1 = (n0 + 1) * (n0 + 1 + 1))
(eq_ind_r (fun n1 : nat =>
2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1) = n1)
(eq_ind_r (fun n1 : nat =>
2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1) = n1 + (n0 + 1) * 1)
(eq_ind_r (fun n1 : nat =>
2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1) = n1 + (n0 + 1) * 1 + (n0 + 1) * 1)
(eq_ind_r (fun n1 : nat =>
2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1) = n0 * n0 + 1 * n0 + n1 + n1)
(Decidable.dec_not_not
(2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1) = n0 * n0 + 1 * n0 + (n0 * 1 + 1 * 1) +
(n0 * 1 + 1 * 1))
(dec_eq_nat (2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1))
(n0 * n0 + 1 * n0 + (n0 * 1 + 1 * 1) + (n0 * 1 + 1 * 1)))
(fun H : 2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1) <> n0 * n0 + 1 * n0 +
(n0 * 1 + 1 * 1) + (n0 * 1 + 1 * 1) =>
(fun (P : Z -> Prop) (H0 : P (Z.of_nat 2 * Z.of_nat (sum n0))%Z) =>
eq_ind_r P H0 (Nat2Z.inj_mul 2 (sum n0)))
(fun x : Z => x = Z.of_nat (n0 * (n0 + 1)) -> False)
((fun (P : Z -> Prop)
(H0 : P (Z.of_nat n0 * Z.of_nat (n0 + 1))%Z) =>
eq_ind_r P H0 (Nat2Z.inj_mul n0 (n0 + 1)))
(fun x : Z => (2 * Z.of_nat (sum n0))%Z = x -> False)
((fun (P : Z -> Prop) (H0 : P (Z.of_nat n0 + Z.of_nat 1)%Z) =>
eq_ind_r P H0 (Nat2Z.inj_add n0 1))
(fun x : Z => (2 * Z.of_nat (sum n0))%Z =
(Z.of_nat n0 * x)%Z -> False)
(fun _ :  (2 * Z.of_nat (..))%Z =
(Z.of_nat n0 * (.. + 1))%Z =>
(fun  (P : Z -> Prop) (H0 : P (..)%Z) =>
eq_ind_r P H0 (Nat2Z.inj_add (..) (..)))
(fun x : Z => Z.of_nat (..) = x -> False)
((fun (P : ..) (H0 : ..) => eq_ind_r P H0 (..))
(fun x : Z => .. = ..%Z -> False)
(fun _ : .. => (..) (..) (..) (..)))
(inj_eq  (sum (S n0)) (S n0 + sum n0) Step))))
(inj_eq (2 * sum n0)
(n0 * (n0 + 1)) IHn)))
(mult_plus_distr_r n0 1 1))
(mult_plus_distr_r n0 1 n0))
(mult_plus_distr_l (n0 + 1) n0 1))
(mult_plus_distr_l (n0 + 1) (n0 + 1) 1))
(mult_plus_distr_l n0 n0 1))
(mult_plus_distr_l 2 n0 1)) Id)
(Decidable.dec_not_not (S n0 = n0 + 1)
(dec_eq_nat (S n0) (n0 + 1))
(fun H : S n0 <> n0 + 1 =>
(fun (P : Z -> Prop)
(H0 : P (Z.of_nat 2 * Z.of_nat (sum n0))%Z) =>
eq_ind_r P H0 (Nat2Z.inj_mul 2 (sum n0)))
(fun x : Z => x = Z.of_nat (n0 * (n0 + 1)) -> False)
((fun (P : Z -> Prop)
(H0 : P (Z.of_nat n0 * Z.of_nat (n0 + 1))%Z) =>
eq_ind_r P H0 (Nat2Z.inj_mul n0 (n0 + 1)))
(fun x : Z => (2 * Z.of_nat (sum n0))%Z = x -> False)
((fun (P : Z -> Prop)
(H0 : P (Z.of_nat n0 + Z.of_nat 1)%Z) =>
eq_ind_r P H0 (Nat2Z.inj_add n0 1))
(fun x : Z => (2 * Z.of_nat (sum n0))%Z = (Z.of_nat n0 * x)%Z -> False)
(fun _ : (2 * Z.of_nat (sum n0))%Z =
(Z.of_nat n0 * (Z.of_nat n0 + 1))%Z =>
(fun (P : Z -> Prop) (H0 : P (Z.of_nat (S n0) + Z.of_nat (sum n0))%Z) =>
eq_ind_r P H0 (Nat2Z.inj_add (S n0) (sum n0)))
(fun x : Z => Z.of_nat (sum (S n0)) = x -> False)
((fun (P : Z -> Prop) (H0 : P (Z.succ (Z.of_nat n0))) =>
eq_ind_r P H0 (Nat2Z.inj_succ n0))
(fun x : Z => Z.of_nat (sum (S n0)) = (x + Z.of_nat (sum n0))%Z -> False)
(fun _ : Z.of_nat (sum (S n0)) =
(Z.succ (Z.of_nat n0) + Z.of_nat (sum n0))%Z =>
(fun (P : Z -> Prop) (H0 : P (Z.succ (Z.of_nat n0))) =>
eq_ind_r P H0 (Nat2Z.inj_succ n0))
(fun x : Z => Zne x (Z.of_nat (n0 + 1)) -> False)
((fun (P : Z -> Prop) (H0 : P (Z.of_nat n0 + Z.of_nat 1)%Z) =>
eq_ind_r P H0 (Nat2Z.inj_add n0 1))
(fun x : Z => Zne (Z.succ (Z.of_nat n0)) x -> False)
(fun H0 : Zne (Z.succ (Z.of_nat n0))
(Z.of_nat n0 + 1) => ex_ind (fun (Zvar29 : Z)
(Omega75 : Z.of_nat n0 = Zvar29 /\ (0 <= Zvar29 * 1 + 0)%Z) =>
and_ind (fun (Omega66 : Z.of_nat n0 = Zvar29)
(_ : (0 <= Zvar29 * 1 + 0)%Z) =>
ex_ind (fun (Zvar30 : Z) (Omega74 : .. /\ ..%Z) =>
and_ind (.. => ..) Omega74) (intro_Z (sum (..)))) Omega75)
(intro_Z n0))) (inj_neq (S n0) (n0 + 1) H)))
(inj_eq (sum (S n0)) (S n0 + sum n0) Step))))
(inj_eq (2 * sum n0) (n0 * (n0 + 1)) IHn)))) IHn)
(mult_plus_distr_l 2 (S n0) (sum n0))) Step) eq_refl) n
: forall n : nat, 2 * sum n = n * (n + 1)

To give a shorter example, the associativity of addition can be proved like so:

Lemma add_assoc (n m p : nat) : n + (m + p) = (n + m) + p.
Proof.
  induction n.
  reflexivity.
  simpl. rewrite IHn.
  reflexivity.
Qed.

The associated function is:

add_assoc =
fun n m p : nat =>
nat_ind (fun n0 : nat => n0 + (m + p) = n0 + m + p) eq_refl
  (fun (n0 : nat) (IHn : n0 + (m + p) = n0 + m + p) =>
   eq_ind_r (fun n1 : nat => S n1 = S (n0 + m + p)) eq_refl IHn) n
     : forall n m p : nat, n + (m + p) = n + m + p


Data General MV/8000 virtues of "No mode bit" I'm reading Tracy Kidder's "The Soul of a New Machine" where a team at Data General design a new machine (codenamed "Eagle", later named MV/8000). It is 32-bit extension of a previous architecture (the 16-bit Eclipse). One of the revolving themes seems to be, that they don't want to create a machine with a mode bit and that they succeeded in this.

However, it leaves out how this is technically achieved, and it also doesn't go into why it was so attractive to create a machine without a mode bit. The book is not a technical book so it could be that the details were somehow distorted. However, you get the feeling reading that book that a "mode bit" solution was common (and hence feasible) at the time, but was deemed unattractive by the engineers maybe for aesthetic reasons. The book also makes it seem like an immensely difficult task to create a design without a mode bit, which was somehow overcome by this particular team.

I found this description of how it was achieved:

http://people.cs.clemson.edu/~mark/330/kidder/no_mode_bit.txt

It seems to basically be about using a previously unused portion of the opcode space for the new instructions. I must admit I was a bit disappointed that it was "just that". Also I think this still leaves some questions unanswered:

Firstly, how did the 16-bit processes live in the 32-bit address space? Because I think that is the key challenge in making a 32-bit extension "without a mode bit". Extending the instruction set, on the other hand, is a relatively common undertaking. Since there's no description of how it happened one could assume that the 16-bit code simply access memory as it always did, maybe it sees some type of virtualized/banked view of memory (with new CPU registers controlling where the first address is) or something like that. But I don't know if there's more to it than that. In that case one could argue it sort-of was a "mode bit" solution. The 16-bit mode processes could run alongside the other processes by virtue of special features added to the CPU. Whether this might imply a new bit in a control register or just some new added control register is unclear.

Secondly, why was it so appealing to create a machine without a mode bit? Many  of the benefits touted in the book is that customers wanted to run old software. But this doesn't seem to speak against a mode bit, since the whole purpose of using a mode bit is to have backwards compatibility. When AMD extended x86 to 64-bits, at least according to my understanding of the word "mode bit" what they did was exactly to add a mode bit. A special bit that would make the CPU in 64-bit mode. And another bit that would make a process execute in a "sub-mode" of the 64-bit mode (to enable compatibility with 32-bit applications). The essence of the submode is that the CPU interprets the instruction stream as the old 32-bit instructions but that the 32-bit memory accesses made are resolved using the new page tables format (setup by the 64-bit aware operating system) and eventually mapped to the full physical address space. Also, the 32-bit code can be preempted by 64-bit code. Like the Data General solution this also allowed a 32-bit program to run along under 64-bit programs (16-bit vs 32-bit in the DG case). So from a customer point-of-view there appears to be no difference at all. Hence the only benefit could have been in the implementation, simplifying the design, but the book doesn't make it sound like that is the concern, since the mode bit seeemed to be common even at that time (and it seems later architectures have also employed it as the x64 case shows).

I'm sure there's something I missed, so it would be great if someone could discuss more on the technical details and virtues of this "no mode-bit" design.

The answer is that Ed deCastro, President of Data General Management, had established a team of engineers in North Carolina specifically to design the next generation CPU. He assigned the task of support and incremental enhancements to us, the Massachusetts team. Three times we proposed a major new architecture, each time with a very sensible mode bit, and described it as a modest incremental enhancement. Each time, Ed saw through our disguise and rejected the proposal, expecting the North Carolina team to succeed. Ed believed that regardless of how we attempted to disguise our proposals, he would know it was a new generation architecture if it had a mode bit. So we had to propose a new generation architecture with no mode bit, even if that made it less efficient. That's how we got it past Ed deCastro. See The Soul of a New Machine, by Tracy Kidder.


Subsequence of one string but not of others Let $\Sigma$ be an alphabet, and let $x^+,x^-_1,\dots,x^-_n \in \Sigma^*$ be strings over that alphabet.  Call a string $s \in \Sigma^*$ good if $s$ is a subsequence of $x^+$ but not a subsequence of any of $x^-_1,\dots,x^-_n$.

Given $x^+,x^-_1,\dots,x^-_n$, I am looking to find the shortest good string $s$.  Is there a reasonable algorithm for this?  I am interested in a practical algorithm, even if its worst-case running time is not great.  In my domain, the strings $x^+,x^-_1,\dots,x^-_n$ might be fairly long but I expect there will exist a good string $s$ that is fairly short, in case that helps.

The case $n=1$ is handled by Shortest sub-sequence of one string, that's not a sub-sequence of another string, but I need to deal with the case $n>1$.

Mistakes

First of all, in the comments I made a few mistakes: Both the original claim I made about interleaving, and the comment "correcting" it (now deleted) were wrong, and separately my claim that trying all possible interleavings must yield an optimal solution was also wrong (I give a simple counterexample below).  Finally, my suggestion to set $x^+ = z_j$ and iterate, or use beam search, is actually also not helpful: Whatever answer could be produced by doing this and applying Aryabhata's DP can never be better than using the original $x^+$, since all it does is reduce the size of the solution set from which the DP can pick.  Sorry!  Hopefully the improved version below contains no further problems...

I also noticed two mistakes in Aryabhata's DP as well.  Fortunately they can both be easily repaired (see my comments on that post).

A heuristic solution using random interleavings

If you don't need absolutely the shortest subsequence, you could use the fact that, if a string $s$ is a subsequence of some $x^-_i$, then it is also a subsequence of every possible interleaving of all the strings $x^-_i$.  Turning this around, if $s$ is not a subsequence of some particular interleaving of all the strings $x^-_i$, then it is not a subsequence of any individual $x^-_i$.

So you could try many different ways of randomly interleaving the $n$ strings $x^−_i$ into a single string, and for each such interleaving $y_j$, look for the shortest subsequence $z_j$ of $x^+$ that avoids being a subsequence of $y_j$ using Aryabhata's nice DP algorithm for the two-string case, and pick whichever $z_j$ is shortest over all interleavings you tried.

Caveat: No guarantee of optimality even if we try all interleavings

Surprisingly (to me at least), even if you repeat the above procedure for all possible interleavings, you are not guaranteed to find the optimal solution: Consider the instance in which $x^+ = aaa$, $n=2$, and $x^-_1 = x^-_2 = a$.  Then $aa$ is an optimal solution with length 2, but the shortest solution found by trying all interleavings of $x^-_1$ and $x^-_2$ is $aaa$, with length 3.


Ambiguity with the Top View of a binary tree What exactly is the top view of a binary tree?

I find great ambiguity and lack of clarity from the articles I find.

For example, this is what is used to demonstrate the top view on geeksforgeeks:

       1
    /     \
   2       3
  /  \    / \
 4    5  6   7

They go on to say that the top view is 4 2 1 3 7. The problem here is that they leave a lot of speculation on what isn't the top view. Consequently it becomes ambiguous to implement in code.

Stackoverflow examples are not any better. Hackerrank's example is even worse.

So I have signed up here hoping someone will tell me explicitly what the top view is because I have been trying to find out for 2 days. For instance, what is the top view of this tree:

      1
       \
        14
       /  \
      3    15
     / \
    2   7
       /  \
      4     13
     / \   /
    5   6 10
         /  \
        8    11
         \    \
          9    12

And if I may be bold to ask, why is it important?

I think what they are trying to define is the following.

Given a rooted binary tree $T$, let $V(T)$ be the set of vertices of $T$. For $v \in V(G)$, let $P_v$ the unique path from the root of $T$ to $v$.
We will call an edge $(u,w) \in P_v$ a left edge if $w$ is the left child of $u$, and a right edge otherwise.

Let $\ell_v$ and $r_v$ be the number of left and right edges in $P_v$, respectively, and define $\delta(v) = \ell_v - r_v = 2\ell_v - |P_v|$.

Let $h(u)$ be the depth of vertex $u$ in $T$ and define $\Delta(v) = \{ \delta_u \, : u \in V(T) \wedge h(u) < h(v) \}$.
The top view of $T$ is the set $\{ v \in V(T) :  \delta_v \not\in \Delta(v)  \}$.

In your example the top view would be $\{1, 2, 12, 14, 15 \}$. In general, you can compute the top view in $O(|V(T)|)$ time thought a preorder DFS visit.

I have no idea why this is important, sorry.


Why is the number of digits (bits) in the binary representation of a positive integer $n$ is the integral part of $1 + \log_2 n$? I've stumbled on this definition on Wikipedia, and I can't figure out why.

I could probably start the demonstration by saying that, with $n$ bits, you can create $2^n$ possible different numbers, so $2^n=x$. If I rewrite the expression with logarithms, I find $\log_2x = n$, so the base-2-log of the total number of possible combinations of 0 and 1 is $x$.

And I'm stuck here. I'm probably seeing this from the wrong angle. Also, I wonder what is that $+1$ for?

Sorry if it's a dumb question, but the only way I can memorize a formula is to give a meaning to its numbers.

If you have $n$ bits available you can represent the numbers $0$ to $2^n-1$ in binary. Therefore, if you want to represent a number $x$ in binary, you need a number of bits $n$ that is large enough so that

$$
\begin{split}
2^n - 1 & \geq x\\
n & \geq \log_2(x+1)\,.
\end{split}
$$

Now there are two cases for $\log_2(x+1)$:

It is an integer. Then $\log_2(x)$ won't be. It'll be slightly less. So $\lfloor\log_2(x)\rfloor + 1$ will yield the same value. (The exception where $x=1$ can be checked separately.)
It isn't an integer. In this case $\lfloor\log_2(x)\rfloor + 1$ yields the next largest integer just as $\lfloor\log_2(x+1)\rfloor + 1$ would.

In either case, because $n$ is always an integer we can write

$$
n \geq \lfloor\log_2(x)\rfloor + 1\,.
$$


Induction proof of alpha-beta search Is there a functional specification of alpha-beta search that makes it easy to prove by induction that the algorithm works?

The following is an easy to understand approach to tree pruning. It's easy to see why it's correct.

Let's start with ordinary minimax evaluation. If you are trying to evaluate position $p$ when it's the minimizing player's turn, you return $\min\{\operatorname{eval}(p',\text{max}) \mid p'\text{ successor of }p\}$.

To do tree pruning you change what $\operatorname{eval}(p',\text{max})$ does. Instead of returning a single value, it streams messages to you. Messages like "my final value will be at greater than 3", "my value will be greater than 20", "my value is 23". If the minimizer already got a message saying that one successor $p'$ has has value $5$, and it gets a message from $\text{eval}(p'',\text{max})$ saying that its value will be at least $10$ then the minimizer will close the channel with $\text{eval}(p'',\text{max})$.

It's easy to translate this into code and it's clear that it's functionally identical to minimax.

But it's not quite the algorithm presented on Wikipedia under alpha beta pruning.


Given a boolean matrix A of size n, A^p can be computed in space O(log n log p) The solution to this problem can be found here. It says:

  To multiply $k$ matrices, we generate the result entry by entry, by running a counter $t$ and generating the $it$th entry in the product of the first $k − 1$ and the $tj$th entry in the last matrix. Inductively, we need to maintain $k$ counters which can be done in $O(k \log n)$ space. Finally, note that using repeated squaring, we can compute $A^p$ using $O(\log p)$ matrices, which are different powers of $A$. To generate each of these matrices, we just need $A$ and a single counter. Hence the total space needed is $O(\log p \log n)$.

What I don't understand is that in the case of multiplying $k$ fixed matrices, they're part of the input tape so no space is needed for them in the work tapes. In the case of the $A^p$ computation, the intermediate results $A^{2^t}$ must be stored somewhere demanding more space. So how can this be done in $O(\log p \log n)$ space?

Thanks!

No.  The intermediate matrices $A^{2^t}$ don't need to be stored anywhere.  When you need a value, you just recompute it.  This might sound very inefficient -- but remember, we're only counting the space complexity here, not the time complexity, so it's fine to take a very long time to recompute the same value many times, if that saves you some space.


Method for eliminating spent hashes from a large collection? Consider a DB with a large set of numbers, like hashcash tokens, where new numbers are constantly added(spent). Only numbers that has not been already added can be accepted.
Is there a functional way to do this by some sequential operation on the numbers, so that only a single number X is needed to verify that a new number K has not been added before, i.e. a function like:
Xn+1 = f(Xn,K)
which will return zero if K was previously added? (Or where a small set of numbers can do the same job?)

There is no lossless way to compress a set of arbitrary numbers where the size of the set is unbounded to a fixed number of bits. Cryptography won't help with that.

If you're okay with the storage requirements growing linearly with the number of elements, then use a hash table. This method has no false positives or false negatives. Queries take $O(1)$ time.

If you want a fixed size and are okay with false positives then use a bloom filter. The more elements you add the greater the probability of false positives become.

If you can force the inputs to use a timestamp then you can reject attempts to add records with a timestamp too far into the past. You can then decide to remove all records from a database that are old enough to be rejected and still prevent double spending. (But if you remove the original record you can no longer test for its membership to the set.)

Hashcash rejects headers with dates more than 2 days in the past, so hashes older than 3 days can be deleted to save storage space while still preventing reuse.


Problem from the Cormen appendix C 1.13 I am currently working on CLRS 1.13. The idea is to use Stirling's
approximation to prove that
$${2n \choose n} = \frac{2^{2n}}{\sqrt{\pi n}} \left( 1 + O \left( \frac{1}{n} \right)  \right)$$
Now directly replacing Stirling's approximation I arrive to something like:
$${2n \choose n} = \frac{2^{2n} \left( 1 + \Theta(\frac{1}{2n}) \right)}{ \sqrt{\pi n} \left(1 + \Theta( \frac{1}{n}) \right)^2 }$$
Now the quotient is a function that ends up being $O(\frac{1}{n})$ because we
have terms in $O(\frac{1}{n})$ and $O(\frac{1}{2n})$.  The problem is that even if there
is a quotient of two functions that are $O(\frac{1}{n})$.
I don't know if the result is still $O(\frac{1}{n})$.  In fact I haven't seen
any general rule for the quotient of two big $O$ s.
Is there a general rule that I can apply here?

Just simply use the inequality $1 + \Theta(1/n) \geq 1$ in the denominator. You will get the required answer.


Computing tree alignment distance I am implementing the dynamic programming algorithm for computing tree alignment distance as described in "Alignment of trees — an alternative to tree edit". But I got stuck in lemma 3 on page 141 (page 5 of pdf). The notations are given at the beginning of section 2. The last case in lemma 3 says

However, there is no recurrence formula given to compute . How did we obtain this?

I don't think the following holds either:
?

If I understand the paper correctly (and I might not), the solution seems to be described in Section 2.2 of the paper.  It says "we have to compute $D(F_1[i],F_2[j_s,j_t])$..." and then it goes on to describe a strategy for doing so (namely, the Procedure 1, as described in Figure 2).


How to detect sunshine on a photo How would you algorithmically detect for any given photo whether the sun was shining when the picture was taken?

Examples

A sample from this webcam at a mountain top:

Clearly the sun is shining.

In this other sample it's far less obvious:

One could probably detect fairly easy whether it's foggy by trying to identify the tiny church spire on the chapel in the center. However, knowing very little about image processing I'd be surprised if there was a (combination of) algorithm that could reliably tell if there's sunshine or not.

If you can access the meta-data you could apply a number of heuristics:

Check the white-balance setting, the camera has chosen for the photo. Basically it indicates the color temperature of the light at the time the photo was taken. Usually sunlight is around 5500 Kelvin. Indoor lighting or cloudy days, usually have different temperatures.
Check the exposure settings. Usually when the sun shines, there is more light available, so this influences the following settings:

A lower shutter speed
A lower ISO setting
A higher f-value

In the old days of photography, the Sunny 16 rule was used to estimate exposure. And you could use it, together with the information in the list above, to check if the photo was taken during the day.
Check if a flash fired or not.
Check the time the photo was taken. Assuming the user has configured the clock, you might immediately remove photos shot at night.

If however you want to approach this problem simply from an image-processing point of view. I can say that sunlight has usually higher contrast, and harsher edges. Therefore histogram analysis and finding harsh edges might give a good indication.

Assuming the photos you are processing are in a Raw Image Format you could apply the same white-balance trick described above. This however does not work for standard images like jpeg or png. This because the image processor on the camera already compensates for the shift in color temperature, and bakes the result into the final image, merely recording the wb-setting it in the metadata.


Maximisation of graphs weight I have a graph related problem.
Let $G$ be an undirected weighted graph of $N$ nodes. I want to find $p$ independent (they have no edge linking them) sub-graphs of $m$ nodes in a way that the total weight is maximized.

For example, let $G$ be a graph of $16$ nodes, I want to find $4$ sub-graphs of $4$ nodes with $w_1, w_2, w_3, w_4$ as their weights (sum of the weights on the subgraph's edges) I want to determine the $4$ subgraphs that will maximize $w_1+w_2+w_3+w_4$.

Is this a classic graph problem? Is there already an algorithm for this? I am not very experienced with graphs and my research on the net was only confusing. Any ideas on how to approach this?

Thank you for your help

It is definitely not a classic graph problem such as the shortest path, maximum-flow, or graph coloring problem. But your problem, in its general form, seems to solve the Independent set problem, which is $NP$-complete.

Assume that you have a polynomial time algorithm $A(G,m,p)$ solving this problem. Then take $m=1$ and call $A(G,1,p)$ for $p=N,N-1,...,2,1$ (at most $N$ times) until you find a solution. When $m=1$, each subgraph has only one node and so its weight is 0, which is maximum for a single node graph. Furthermore, these nodes are not connected by an edge, and so they are not adjacent, i.e. they are independent.

If this procedure finds a solution for the maximum $p$ less than $N$, then this means we have a maximal independent set, since
we have exactly $n$ nodes (subgraphs) with no edges between them, i.e. independent.

Once your problem is $NP$-complete, you could try any approximation algorithm including Linear or Integer programming.


Checking whether at least n/2 + 1 elements of a set/vector are equal We have a set of elements, say a vector of $n$ elements (actually, the data structure really doesn't matter in this case). It is NOT sorted. We want to check whether at least $n/2 + 1$ elements are equal.

I have been thinking about an efficient algorithm to do so but I don't know, the fact that it is not sorted makes it quite difficult for me.

If it was sorted, we could do it with an $O(n)$ algorithm, I'd say: just iterate over the vector, saving the most common element. If the counter arrives to $n/2 + 1$, we are done.

Could you give me some advice? Thank you very much.

I think there is an even better approach to your problem:

The element you are looking for will also be the median of the list. Find the median of the list using the Median of Medians algorithm. $O(n)$ complexity
Check if the median appears at least $n/2 + 1$ times on the list $O(n)$ complexity

So, the algorithm you're looking for runs in linear time.


What is a "geometric rectangle"? In the [Kushilevitz and Nisan 2006, P.10] they give an exercise which says as following:

  Exercise 1.18: Let $X=Y=\{1,\ldots,n\}$. A geometric rectangle is a set of the form $\{(x,y)|x_{\min} \leq x \leq x_{\max}, y_{\min} \leq y \leq y_{\max}\}$, for some values $x_{\min},x_{\max},y_{\min}$, and $y_{\max}$ in $\{1,\ldots,n\}$. A comparison protocol is a one in which at each node $v$, if Alice needs to transmit a bit then this bit is the result of comparing her input $x$ with some value $\theta_v$ (that is, $a_v(x)$ is $0$ if $x < \theta_v$ and $1$ if $x \geq \theta_v$). Similarly, at each node $v$ where Bob speaks he sends the result of comparing his input $y$ with some value $\theta_v$. Prove that every comparison protocol for computing a function $f$ partitions the space $X\times Y$ into $f$-monochromatic geometric rectangles.

My simple question is "What is geometric rectangle" in order to understand the exercise?

Assume that we have 2 bits, then we have four possible ways to represent 2 bits on X and on Y, so total is $ 4 \times 4 = 16$ cells on the matrix. When I try to follow what the definition of "geometric rectangle", I found that all matrix have 1 entry; because it achieves the definition of a "geometric rectangle"; it didn't sounds "reasonable" because there is a comparison between the inputs, so there must be a {0} and {1} entry on the matrix.

I tried to look up for another definition of a "geometric rectangle", it turns out that "geometric rectangle" is "the Euclidean geometric rectangle", I don't understand what is the relation between "Euclidean geometric rectangle" and "combintorial rectangle" on communication complexity, does "geometric rectangle" refer to "Euclidean geometric rectangle" or there is misunderstanding here?

Any hence or reference would be very helpful, Thank You!

Geometric rectangle is not a standard term. That's why they define it in the question.

In communication complexity, Alice has an input from the set $X$, and Bob has an input from the set $Y$. Usually we assume that the sets $X,Y$ are unstructured. A combinatorial rectangle is a subset of $X \times Y$ of the form $A \times B$, where $A \subseteq X$ and $B \subseteq Y$.

In this question, the sets $X,Y$ are ordered, and the authors defined a geometric rectangle to be a subset of $X \times Y$ of the form $A \times B$ where $A$ is a subinterval of $X$ and $B$ is a subinterval of $Y$. That is, $A = \{ x \in X : x_1 \leq x \leq x_2 \}$ for some $x_1,x_2 \in X$, and $B = \{ y \in Y : y_1 \leq y \leq y_2 \}$ for some $y_1,y_2 \in Y$.


Find a strategy to evade hungry lions on the real line for the longest time This is an interview question I was asked, which I don't know how to approach. I would appreciate pointers to algorithms I should look up.

You are placed on the real line, and there also are $K$ lions on the real line, which are currently sleeping. You are given the wake up time of each lion. You can walk past a lion as long as it is sleeping. As soon as any lion wakes up, it starts walking towards you to eat you. Both you and the lions can walk at a maximum speed of 1m/s.

Given your starting position and the starting positions and wake up times of the lions, find the maximum time you can stay alive (can be infinite), and the strategy you should follow.

Assume you start at zero. Lion #i is at $d_i$ and wakes up at $w_i$. If there is no lion with $d_i > 0$ and $w_i < d_i$ then you walk to the right and are safe. If there is no lion with $d_i < 0$ and $w_i < |d_i|$ then you walk to the left and are safe.

Otherwise, you die. There is always an optimal strategy of the form "move to some point X and stop, then wait until lions force you to move, and die when two lions from either side meet" - the point X is obviously not known. The point X is limited; if for example $d_i > 0$ and $w_i < d_i$ then you can walk only $(d_i + w_i)/2$ before you are forced back.

Just check the points X that are just before a sleeping lion, or just before one of the two points where you are forced back. For each of these points X, calculate at which time you will die, and pick the best one.

(To make this easier to visualise: If all lions wake up at the same time, and you can't escape, then you want to be within the largest gap between two lions that you can reach, at the moment they wake up. So the point to move to could be anywhere, depending on where the lions are).