How does the OS know the physical address of a process' first memory page? If I have a program, its instructions are stored on the hard drive. When I double-click the executable the pages of memory for this process must get loaded in to RAM. However, for the pages to get loaded in to RAM, the CPU must already have resolved the virtual address to physical address. The latter requires the TLB to have been involved- which requires the L1 cache to have been queried- which cannot have happened as the process instructions haven't even been loaded in to RAM yet?

I am totally confused how the instructions for a process are loaded in to RAM the very first time when the L1 cache doesn't contain any information about the process.

The operating system performs a lot of work before executing the first instruction.  The OS must set up at least two data structures, the page table and the region map.  The region map is called different things in different operating systems.  Inside the Linux kernel, for example, it is a linked list of memory-region objects and some kind of index (e.g. a red-black tree) that gives you an efficient way of discovering the region a specific virtual addresses belongs to.

Each memory region has a start address, a length, permissions (can the program read/write/execute from the region), and some information about the "type" of the region, including how the region is supposed to be initialized on first use and how the logical information is supposed to be saved if a mapped page needs to be moved to disk.

The first step is that the operating system creates a new page table with every virtual page marked as "invalid."  Next the OS reads the header of the executable file.  The header describes the region map and also gives the virtual address of the first instruction to be executed.  So the OS creates an in-memory region map to match the structure described in the executable header and then tries to execute the first instruction (it does this by using some kind of "return from interrupt" instruction that sets the root of the page table to the page table for the process we want and then changing the program-counter (instruction-pointer) to the virtual address of the first instruction.

So the processor tries to execute the instruction at the given virtual address.  But every page in the page-table is marked invalid, so when the processor performs the translation from virtual to physical address the processor will invoke an "invalid page" fault, bringing control back to the operating system.  The operating system will look up the virtual address in the region map.  Since this was supposed to be the address of the first instruction, then it should be the case that the virtual address is contained in a region that is marked as being executable, and there should be information about where the instructions are located in the original executable file.  The OS reads a page-worth of date from the original executable file into some physical page in memory, and then modifies the page table to reflect the new virtual-to-physical mapping.  Finally the OS again tries to return-from-interrupt to the instruction address.  This time, although there will be TLB misses and cache misses, the translation will give a mapping from virtual to physical address, the processor will eventually try to fetch the required instruction into the L1 cache and execute it.

In all likelihood the instruction will try to access some not-yet valid data location.  There will be another "invalid page" fault for the data's virtual address.  The OS will look up the data's virtual address in the region map, allocate a physical page, initialize the page, map the page in the page table and then return-from-interrupt a third time.  This time the instruction will get fetched and executed, and after another TLB and cache miss for the data access will actually execute without causing another fault.  Then we move to the next instruction and start all over again.

Hopefully we have some spatial and/or temporal locality so this process doesn't happen with every instruction.


Are context-free languages in $a^*b^*$ closed under complement? The context-free languages are not closed under complement, we know that.

As far as I understand, context-free languages that are a subset of $a^*b^*$ for some letters $a,b$ are closed under complement(!?)

Here is my argument. Each CF language $L$ has a semi-linear Parikh image $\pi(L) = \{ (m,n) \mid a^mb^n \in L \}$. Semilinear sets are closed under complement. The set of vectors that represent the semi-linear set can easily be transformed into a linear grammar.

Question. Is there an easily accessible reference to this fact?

Technically these languages are called bounded, i.e., a subset of $w_1^* \dots w_k^*$ for some words $w_1,\dots,w_k$.

My motivation for this question is from a recent question on the context-freeness of $\{ a^nb^m \mid n^2 \neq m \}$. Its complement within $a^*b^*$ seems easier to handle.

This characterization of bounded context-free languages is due to Ginsburg ("The Mathematical Theory of Context-Free Languages"), and appears as Corollary 5.3.1 in his book. For general $k$ there are some restrictions on the semilinear sets, but for $k \leq 2$ these restrictions are always satisfied, and so it is straightforward to deduce that the complement of such a language (within $w_1^* w_2^*$) is context-free.

Ginsburg mentions these implications in his book.

Corollary 5.6.1 If $M_1 \subseteq w_1^*w_2^*$ and $M_2$ are [context-free] languages, $w_1$ and $w_2$ words, then $M_1\cap M_2$ is a [context-free] language.

Corollary 5.6.2 If $M_1 \subseteq w_1^*w_2^*$ and $M_2$ are [context-free] languages, $w_1$ and $w_2$ words, then $M_1 - M_2$ and $M_2-M_1$ are [context-free] languages.


Using LP to prove the max matching - min cover theorem Konig's theorem says that, in a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover. This theorem has several proofs; I would like to know if the following proof, based on primal-dual linear program, is valid. This is mainly an exercise in understanding this primal-dual concept.

Step 1: define an LP for the maximum matching. For every edge $(u,v)\in E$, define a variable $z_{uv}$ whose value is 1 if the edge is in the matching. The LP is:

\begin{align}
\text{maximize} && \sum_{(u,v)\in E} z_{uv} &&
\\
\text{subject to} && \sum_{v\in Y} z_{uv} \leq 1 && \forall u\in X
\\
                  && \sum_{u\in X} z_{uv} \leq 1 && \forall v\in Y
\\
&& z_{uv}\geq 0  && \forall (u,v)\in E
\end{align}

Step 2. Create the dual LP using the recipe:

Each primal constraint becomes a dual variable - so there is a variable $x_u$ for each $u\in X$ and a variable $y_v$ for each $v\in Y$.
The sign of each dual variable is opposite to the sign of its primal constraint - so $x_u\geq 0, y_v\geq 0$.
The dual objective is minimization, where the coefficient of each dual variable is the number on the right-hand side of its primal constraint - in this case it is always 1. So the objective is "minimize $\sum x_u + \sum y_v$".
Each primal variable becomes a dual constraint.  The coefficient of a dual variable in the dual constraint is the coefficient of its primal variable in its primal constraint. In this case, the coefficient of the dual variable of a node $i$, in the dual constraint of the edge $(j,k)$, should be 1 iff $i=j$ or $i=k$.
The sign of each dual constraint is the sign of its primal variable.
All in all, the dual LP is:

\begin{align}
\text{minimize} && \sum_{u\in X} x_u + \sum_{v\in Y}y_v &&
\\
\text{subject to} && x_u + y_v \geq 1 && \forall (u,v)\in E
\\
&& x_{u}\geq 0, y_v \geq 0  && \forall u\in X, v\in Y
\end{align}

The dual LP finds a minimum vertex cover - it minimizes the number of vertices under the constraint that for each edge, at least one of its endpoints is in the cover.

My question is: is this proof valid?

The main thing I am not sure at is that the LP allows fractional variables, while the original problems are integral. What argument should be added to handle this issue?

Your proof is missing a crucial ingredient, namely that for bipartite graphs, your LPs have the same objective value as the corresponding IPs. This is not true in general (otherwise vertex cover would be in P). You can see a proof for maximum matching in lecture notes of Meena Mahajan, and a proof for both in lecture notes of A. A. Ahmadi.


Some terminologies in Wirth's book and the satisfying of deterministic algorithm I am going through Wirth's Textbook on Compiler design . After proceeding though
some pages ,  I realized I have taken for granted my understanding of some
of the terminologies that have been used . For example ,the following terms :

the examples mentioned in the lines in the screenshot refer to the following set of equations :

Later on while describing the possibility of the conditions of deterministic algorithms being
satisfied it says for an expresion of the following form :

"term_0 | term_1"

the terms must not feature any common starting symbols .And then it says this results in the exclusion of
left recusrsion . If we consider the left recursive production :

A = A "a" | "b"

then the requirement is violated "b" is also a start symbol of "A" .

How is "b" a start symbol of "A" ? Basically from the definitions given I understood start symbol means
the symbol for which an equation is deifined first ?

Why does common start symbol disturb the conditions of deterministic algorithm ?

The definition of start symbol that you quote has nothing to do with the definition of start symbol in the context of deterministic grammars. Here is a correct definition:

  A terminal $a$ is a start symbol of a sequential form $\alpha$ if $\alpha \Rightarrow^* aw$ for some $w \in \Sigma^*$.

In words, $a$ is a start symbol of $\alpha$ if $\alpha$ generates some word starting in $a$.

In your example, $Aa$ generates the word $ba$, and so it shares a start symbol with $b$.

Why is sharing a start symbol bad? Suppose you are trying to parse $A$, and are encountering $b$. Which production do you choose? $Aa$ or $b$? It is impossible to tell without looking ahead. The deterministic algorithm considered by Wirth has no lookahead, and so this situation is problematic for it.


Is it possible to compute the minimum vertex covering set in quasi-polynomial time, by knowing the vertex cover number? If we know the vertex cover number for a simple graph $G$ denoted by $\tau(G)$, is it possible to find the minimum vertex cover set for $G$ in quasi-polynomial time? As I found, we cannot find any quasi-polynomial time solution for NP-hard problems (or at least it is a strong conjecture) such as finding the minimum vertex covering set.

Suppose there is an algorithm $A(G,c)$ which runs in time $T(n)$, where $n$ is the number of vertices in $G$, as long as $c$ is the vertex cover number.
Given a graph $G$, run $A(G,0),\ldots,A(G,n)$ in parallel, for $T(n)$ time each. Some of the copies will terminate within $T(n)$, outputting a set. Out of all such outputs which are vertex covers, choose the one of minimal size. This gives an algorithm for minimum vertex cover running in time $O(nT(n))$.


Reducibility: Show that SUBSET SUM is reducible to the following problem A A: Given nonnegative integers x1,...,xn (written in binary), and an
integer k, can the net expenses be balanced using k or fewer checks? (Suppose that A is in NP).
Purpose: to reveal that SUBSET SUM reduces to A so that A is
NP-complete (since SUBSET SUM is NP-complete).

Let me construct A as follows:

We can find the balanced net expense using SUBSET SUM.

The balanced net expense = (x1+x2+...+xn)/n

There will be some algorithm to compute k.

What I wonder is that as we see the algorithm above A seems to be a harder problem than SUBSET SUM because A uses SUBSET SUM within its algorithm. Is this fact enough to support the idea that SUBSET SUM is reducible to A?
Thank you for your time.

You can consider the numbers $x_i$ as signed integers representing how much each person owes (if the number is positive) or how much each person needs to receive (if the number is negative). Then you have $\sum_{i=1}^n x_i = 0$ and the goal is to make all numbers $0$.
Notice that you can always settle debts with at most $n-1$ checks:
pick an $i$ such that $x_i>0$ and move $x_i$ from $i$ to an arbitrary $j \neq i$.
Delete $x_i$ (now $0$) from the instance. You are left with another instance of the same problem in which you need settle debts between $n-1$ people. Repeat recursively until you are left with only one person (in which cases no transactions are needed).
Suppose now that you can partition the set $\{x_1, \dots, x_n\}$ into two non-empty sets $S_1$ and $S_2$ such that $\sum_{x \in S_1} x =0$ (and hence $\sum_{x \in S_2} x = 0$). Then you can solve $S_1$ and $S_2$ separately using at most $|S_1|-1 + |S_2|-1 = n-2$ checks.
The converse is also true: if you can balance debts using at most $n-2$ checks, then you can partition $\{x_1, \dots, x_n\}$ into non-empty $S_1$ and $S_2$ with $\sum_{x \in S_1} x = \sum_{x \in S_2} x = 0$.
To see this, build the graph $G=(V,E)$ in which $V=\{1, \dots, n\}$ and there is an undirected edge $(i,j)$ if $i$ and $j$ exchange at least one check. Since $|E| \le n-2 = |V|-2$, the graph $G$ has at least $2$ connected component. If $C$ is a connected component then the sum of the integers $x_i$ such that $i \in C$ must be $0$. Let $S_1 = \{x_i \mid i \in C\}$ and $S_2 = \{x_1, \dots, x_n\} \setminus S_1$.
This shows that you can reduce the variant of partition in which the sum of the integers is $0$ (and you need to find a non-trivial partition) to your problem.
To see that this variant remains $\mathsf{NP}$-hard, consider an instance of partition $\{y_1, \dots, y_n\}$ in which each integer $y_i$ is positive, and add two additional integers $y'$ and $y''$ with $y'=y''= -\frac{1}{2}\sum_{i=1}^n y_i$.
Clearly, any non-trivial partition $A,B$ of $\{y', y'', y_1, \dots, y_n\}$ must place $y'$ in $A$ and $y''$ in $B$, or vice-versa, showing that the sum of the elements in $A \cap \{ y_1, \dots, y_n\}$ is $\frac{1}{2}\sum_{i=1}^n y_i$ (and the same holds for $B$). Conversely, given any partition $A,B$ of $\{y_1, \dots, y_n\}$, the partition $A \cup \{y'\}$, $B \cup \{y''\}$ is a solution to our variant.


Scheduling a sequence of queue operations that push and pop items at specified times What is the time complexity of the following problem?

Definitions

A FIFO is a queue functional unit supporting four commands: PUSH (data to back of queue), POP (the head of the queue), PNP (POP the head of queue and PUSH it to the back), NOP (do nothing). Each command takes one unit of time to execute.

FIFO code (or a schedule of commands) is a sequence of commands to execute.

Problem Description

We are given $n$ items of data $T_1,\dots,T_n$, and $n$ triplets $(T_1,t^{in}_1,t^{out}_1),\dots,(T_n,t^{in}_n,t^{out}_n)$. $t^{in}_i$ and $t^{out}_i$ identify the time when $T_i$ is PUSHed and POPed respectively.  We're guaranteed that $t^{in}_i<t^{out}_i$ for every $i$ and $t^{in}_i,t^{out}_i$ are all unique.

The goal is to produce FIFO code (a schedule of commands) that push each $T_i$ at time $t^{in}_i$ and pop it at time $t^{out}_i$, by adding NOP and PNP commands between the PUSH and POP commands given.  No extra PUSH or POP commands can be added: the resulting code must contain exactly $n$ PUSHes and $n$ POPs.

Example

Input:
$(T_1,2,4)$,
$(T_2,1,5)$

Solution:

PUSH $T_2$
PUSH $T_1$
PNP
POP // T_1
POP // T_2

Initial Direction

Solving this problem is equivalent to solving a set of equations with constraints.

Denote the number of time units in an interval between consecutive input $t^{in}_i$/$t^{out}_i$ by $K_i$.

In the above example in the question there are three intervals:

|PUSH($T_2$) | PUSH($T_1$)|---------------|POP($T_1$)  |POP($T_2$)|

|---------------|---------------|---------------|---------------|---------------|

$K_1=0$.
$K_2=1$.
$K_3=0$.

The depth of the FIFO at the beginning and end of each such interval is the number of PUSHs minus POPs made before it, denote it by $d_i$.

In the above example:

$d_0=0$.
$d_1=1$.
$d_2=2$.
$d_3=1$.

Denote by $x_i\in \mathbb{N}\cup\{0\}$ the number of PNP assigned in interval $K_i$, then $x_i\leq K_i$.

In the above example:

$x_1\leq 0$.
$x_2\leq 1$.
$x_3\leq 0$.

Per data unit $T_i$ add an equation asserting it is available at the head of the FIFO at time $t^{out}_i$ by adding $d_i+x_{i+1}$ modulo the depth, $d_{i+1}$ of the FIFO per interval. In the above example:

For $T_1$: $(1+x_2)\bmod 2=0$.
For $T_2$: $((( (0+x_1)\bmod 1+x_2 ) \bmod 2)+x_3) \bmod 1 =0$.

And the solution is $x_1=0, x_2=1, x_3=0$ corresponding with the solution above.

But I'm not sure how to use this information to understand the complexity of the problem.


Is a relational database just a $ \geq 2$-dimensional array? In terms of comparing data structures, is a relational database just a >1 dimensional array?  I'm just asking because I don't know much about databases, but I know a bit about data structures.

I am trying to make this clear in my mind.

No, it isn't. A data structure can be described in two ways:

How does it store the data.
Which operations are supported, their performance (usually given as asymptotic time- and/or space-complexity), and what laws do they obey.

Obviously, a database doesn't store all its data as a single array.

Arrays support, as basic operations, retrieving an element by index and storing an element under an index. Operations required for databases are (to a first approximation) given by relational algebra: selection, projection, union, difference, and join (or product).


Sequential hash tree traversal A lot of articles say that hash tree traversal cost to any randomly chosen leaf is $\mathcal{O}(\log_2 N)$ ($N$ is a number of leafs) and that is right. If we have a tree of 8 leafs it will take us at most 3 operations to get to any leaf, if we have a tree of 64 leafs it will take us at most 5 operations etc.

But lets say I need to check every leaf sequentially to check if all blocks of a file are correct, then I would need $\mathcal{O}(N \log_2 N)$ operations. Or if I would check every second leaf (just left leaf of every pair) I would need $\mathcal{O}((\frac{N\log_2 N}{2}))$ operations. That is, I will need $\mathcal{O}(\log_2 N)$ operations for every leaf? Which leads to exponentially growing evaluations curve and it would be better to use simple hash list or hash chain? Am I right?

Or I just don't see/know something?

*Note, chart has logarithmic scale

You want to access every leaf in a tree, you probably do not want to start from the root every time. If you would then you need indeed $O(N \log N)$ time. If you only want to access all the leaves in the tree, do a depth-first-search traversal and you are done in $O(N)$. If you only want to have every other leaf, do the same, but ignore the "unwanted" elements.

In data structure design one often takes the leaves and put them (in order) in a double linked list. This only costs a constants factor more place, but speeds up sequential access.


Does Master Theorem apply to $T(n) = 4T(n/2) + n^2 \log n$ Based on CLRS Theorem 4.1, master theorem doesn't apply to $T(n) = 4T(n/2) + n^2 \log n$. However, I saw the 4th condition of master theorem on slides of Bourke.
If $f(n)=\Theta(n^{\log_ba}\log^kn)$, then $T(n)=\Theta(n^{\log_ba}\log^{k+1}n)$. So $T(n)=3T(n/3)+n\log n$ can apply to case #2, see for example this question.
With the same logic, $T(n) = 4T(n/2) + n^2 \log n$ should be $T(n) = \Theta(n^2\log^2n)$. But it's actually $T(n) = \Theta(n^2\log n)$. Is there anything wrong of my thinking?

You can expand the recurrence $T(n) = 4T(n/2) + n^2 \log n$ directly:
\begin{align}
T(n) &= n^2 \log n + 4T(n/2) \\ &=
n^2 \log n + 4(n/2)^2 \log(n/2) + 16T(n/4) \\ &=
n^2 \log n + 4(n/2)^2 \log(n/2) + 16(n/4)^2 \log(n/4) + 64T(n/8)
\end{align}
and so on. We can simplify the terms: they are $n^2 \log n$, $n^2 \log(n/2) = n^2 (\log n - 1)$, $n^2\log (n/4) = n^2(\log n - 2)$, and so on. Unrolling the recurrence all the way gives
\begin{align}
T(n) &= n^2 (\log n + \log (n/2) + \cdots + \log(n/(n/2)) + 4^{\log n}T(1) \\ &=
n^2 \sum_{k=1}^{\log n} k + n^2 T(1) \\ &=
\frac{1}{2} n^2 \log n(\log n - 1) + n^2 T(1) \\ &= \Theta(n^2\log^2 n).
\end{align}
This is also what the master theorem gives (case 2 in the Wikipedia version).


What are two's complement integers? Can someone explain in plain English what "two's complement integer" means? I read this:

  in Java long is a 64-bit signed two's complement integer

Two's complement is the most commonly used way to represent signed integers in bits. First, consider unsigned numbers in 8 bits. Notice that $2^8 = 256 = 100000000_2$ does not fit into 8 bits and will thus be represented as 0000 0000. Therefore $255 + 1 =$ 1111 1111 + 0000 0001 = 0000 0000 and in that sense 1111 1111 acts as if it was $-1$. Two's complement is based on this observation.

For a deeper understanding of it, I suggest reading the wikipedia page on it. Note that as long as you you don't need to directly manipulate bits of your integers and your numbers don't go out of range, it makes no difference what signed integer representation is used.


Longest cycle contained in two cycles Is the following problem NP-complete? (I assume yes).

Input: $k \in \mathbb{N},G=(V,E)$ an undirected graph where the edge set can be decomposed into two edge-disjoint simple cycles (these are not a part of the input).
Question: Is there a simple cycle in $G$ with length greater than $k$?

Obviously the problem is in NP and the maximum degree in $G$ is $\leq 4$, but that doesn't seem to help.

A reduction attempt ....

Reduction from Hamiltonian path on digraph $G = (V,E)$ with max degree 3 which is NPC [G&J]

ignore the direction of the edges, and using a first depth (undirected) scan from an arbitrary node, divide the edges of $G$ in two sets of distinct (undirected) paths (red and green in the figures);
join the red paths adding extra "linking nodes" (purple nodes in the figure B) and make an undirected red circuit; join  the green paths adding extra "linking nodes" (purple nodes in the figure) and make an undirected green circuit;
transform each original node $b \in V$ of indegree 1 and outdegree 2 (figure C), adding $k$ yellow nodes on the inbound red edge $a\to b$, and adding $k$ yellow nodes on the first outbound red edge $b \to c$; finally add $k$ yellow nodes "towards" the second outbound green edge $b \to d$ using a "wrapped" path around $b$ that touches the outermost yellow nodes of the red edges (figure D).

In the resulting graph all the $3k$ yellow nodes can be traversed by a simple path only in the two ways showed in figure E and figure F, which correspond to the two valid traversals of the original node $b \in V$; informally if an edge towards the extra "linking" purple node is used, $k$ yellow nodes cannot be traversed.

transform each original node of V of indegree 2 and outdegree 1 in a similar way

Picking a large enough $k \gg |V| $, the result graph $G'$ has an simple path of length greater than $3k(|V|-1)$ if and only if the original graph $G$ has an Hamiltonian path (of length $|V|-1$)

The larger picture can be downloaded here


Question about complexity of algorithms I came across this symbol $2^{\mathcal{O} (n)}$ and I can't figure out what is means. What complexity class is this?

We can understand it as set $\{2^{f(n)}: f \in O(n)\}$.
For example any $n^k,k>0$, will be in $2^{O(n)}$: $n^k=2^{k\log_2 n}$ and  we have $\log_2 n \in O(n)$.
Note: I especially not write $k \cdot \log_2 n \in O(n)$, because multiplication on positive constant has no influence.


Characterization of computationally universal functions Is it correct to state that $u$ is a universal function if and only if
$$
\forall f : \text{RE} \quad
\exists g : \text{R} \quad
\exists h : \text{R} \quad
f = h \circ u \circ g
$$
where RE is the set of recursively enumerable functions and R is the set of recursive functions? (Should R be replaced with something like PR?) If so, does anyone know of a reference that states universality in this generic form?
Defining "universal function"
I suppose we could define "universal function" itself as follows: Let $\phi : \mathbb{N} \rightarrow \mathbb{N} \rightharpoonup \mathbb{N}$ be an enumeration of all partial computable functions $\mathbb{N} \rightharpoonup \mathbb{N}$. Let $\psi : \mathbb{N} \rightharpoonup \mathbb{N}$ where
$$
\psi(n) = \phi(\pi_1(n))(\pi_2(n))
$$
where $\pi_1, \pi_2 : \mathbb{N} \rightarrow \mathbb{N}$ are the first and second Cantor unpairing functions. Then $u : A \rightarrow B$ is universal if and only if
$$
\exists g : R \cap (\mathbb{N} \rightarrow A) \quad
\exists h : R \cap (B \rightarrow \mathbb{N}) \quad
\psi = h \circ u \circ g
$$
This resembles a definition of computable functions given in page 24 of Cutland's Computability: An Introduction to Recursive Function Theory.
Addendum
In a sense, I'm looking for a definition of universality that is more "axiomatic", "abstract", and "generic" than the definition that is usually given, which pertains to partial functions from naturals to naturals specifically. My candidate definition requires only that RE be defined/understood over the relevant domain. (From that, co-RE and therefore R fall out automatically.)
To give an example of what I mean from a different area of mathematics, the reals can be constructed as Cauchy sequences or Dedekind cuts of rationals. However, they can also be directly axiomatized as the (unique) Dedekind-complete ordered field.
I can try to bootstrap the definition of universality from the naturals-to-naturals case, but doing so requires more artificial machinery and is less elegant. I'm wondering whether there's a more "direct" approach. That's why I'm asking for references that discuss how universality is defined in more general domains (than naturals-to-naturals) directly.
Notions like the effective topos and realizability might be relevant.

Several authors have considered this question. If you look at some recent work, it will cite older work. The most recent I am aware of is Pieter Hofstra's and Robin Cockett's work on Turing categories, see Definition 3.1 in their Introduction to Turing categories.


Does a DFA accept an empty string if $q_0$ is the accept state? Suppose $q_0$ is the start state, does this mean that if it's the accept state, then the machine must accept the empty string since it cannot have a transition with the empty string?

Yes.  This is immediate from the definitions.

A DFA accepts if it's in an accepting state after it's read its input. If the input is the empty string, the DFA makes no transitions so, after reading it's input, it's still in its initial state, $q_0$.  If $q_0$ is an accepting state, the automaton accepts the empty string.

Note that you write "the accepting state" but an automaton may have multiple accepting states.


time complexity of word break algorithm I found this question here but I don't think the answer is correct.
Here is the original word break question:

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].

One way to do it is to use backtracking:
vector<string> wordBreak(string s, vector<string>& wordDict) {
    vector<string> sentences;
    string prefix = "";
    findWords(prefix, 0, s, wordDict, sentences);
    return sentences;
}

void findWords(string prefix, int start, const string s, const vector<string> &wordDict, vector<string> &sentences) {
    if (start == s.size()) {
        sentences.push_back(prefix);
        return;
    }
    for (int i = start; i < s.size(); i++) {
        string word = s.substr(start, i - start + 1);
        if (find(wordDict.begin(), wordDict.end(), word) != wordDict.end()) {
            string new_prefix = prefix == "" ? word : prefix + " " + word;
            findWords(new_prefix, i + 1, s, wordDict, sentences);
        }
    }
}

In the worst case, the dictionary contains all prefix of s. From my understanding, in this case, the time complexity is
T(n) = T(n-1) + T(n-2) + ... + T(1) = 2T(n-1) = O(2^n)

I'm not sure if this is correct because I see some threads say it is O(n^n)?
The other way is to use backtracking with memorization:
vector<string> wordBreak(string s, vector<string>& wordDict) {
    return constructSentences(0, s, wordDict);
}

// Return all sentences that can be constructed using substring s[start, ...]
vector<string> constructSentences(int start, const string s, const vector<string> &wordDict) {
    if (dict.count(start)) {
        return dict[start];
    }
    vector<string> sentences;
    if (start == s.size()) {
        sentences.push_back("");
        return sentences;
    }
    for (int i = start; i < s.size(); i++) {
        string word = s.substr(start, i - start + 1);
        if (find(wordDict.begin(), wordDict.end(), word) != wordDict.end()) {
            vector<string> subsentences = constructSentences(i + 1, s, wordDict);
            dict[i + 1] = subsentences;
            for (const auto elem : subsentences) {
                sentences.push_back(elem == "" ? word : word + " " + elem);
            }
        }
    }
    return sentences;
}

I'm not sure how to analyze the time complexity of this approach since some subproblem can be solved in constant time by dictionary lookup but some cannot.
Furthermore, I'm not sure how to analyze the space complexity of these two approaches. From my understanding, the space is bounded by the final output. Since we have O(2^n) final sentence and each sentence have size O(n), does it mean the space complexity for both approach is O(2^n * n) ?

If there is one string x that can be parsed in two ways then repeating x n times can be parsed in at least $2^n$ ways. So the problem has either 0, 1, or an exponential number of solutions. Asking for all is likely pointless.

However, you could provide an answer with many solutions in a much more compact format. Say your input is "catsanddog" repeated 100 times with $2^{100}$ solution, clearly infeasible. Instead we present a solution like this: "word1 word2 word3" if a solution consists of these three words. [solution1 | solution2 | solution3] if there are say three alternatives. And everything concatenated. So the solution in the case above would be written as ["cats and dog" | "cat sand dog"] repeated 100 times.

In practice, this will usually give a solution with size cN for a not very large c, where N is the input size. You can still have extremes. Take the dictionary ["a", "aa"] and a string of n a's as input. The first few solutions are:

"a": "a"
"aa": ["a a" | "aa"]
"aaa": ["a aa" | ["a a" | "aa"] "a"]
"aaaa": [["a a" | "aa"] "aa" | ["a aa" | ["a a" | "aa"] "a"] "a"]


NEAT algorithm and dynamic topology neural networks I have recently been investigating dynamic topology neural networks and there is only one problem I have with understanding them. Because a neuron could be inserted at any point, the neurons are no longer organised into layers, so how is it possible to ensure that all of the inputs for Neuron A at position X have been computed, prior to the computation of Neuron A's output, especially when each neurons output is calculated linearly? I am by no means experienced in the topic, just curious so any information would be helpful, Thank you.

Not an expert in neural net. But I recently read and answer a question on NEAT. From there, I would assume that direction of edges are already determined in each gene. Because of the way operations on genome was designed, I could see that you can ensure the genome is always in `topological order'.

Alternatively, looking at heuristic algorithms that iteratively update graph's weight as it learns (e.g. pagerank and ACO), it should be fine to assume initial weight and just let the iteration stabilise. One could imagine this as every edge being directed both ways --- every link is both input and output.


How to prove $T(n) = 2T(n/2) + n/\log(n)$ can't be solved using the Master Theorem? I have read (in this question) that this recursion can't be solved via Master Theorem.
But I couldn't find exact and complete proof why the Master Theorem does not apply.

Your recursion can be written as:
$$
T(n) = aT(n/b) + f(n),
$$
where $a=b=2$ and $f(n) = n \log^{-1} n$. Defining $c_{crit} = \log_b a = 1$ you can see that $f(n) = \Theta( n^{c_{crit}} \log^k n)$ for $k=-1$, therefore case 2b of the Master Theorem applies.
The solution to the recurrence is therefore:
$$T(n) = \Theta( n^{c_{crit}} \log \log n ) = \Theta( n \log \log n).$$


Why is this language not context free? I been watching tutorials about how to check if a language is not context-free and in 1 video there was a language: L = {a^n b^n c^n | n ≥ 0} and they used a pumping lemma to prove that it's not context-free, I am only a beginner at CFG however I thought a language is Context-free if you are able to create a CFG for it, and this is the CFG i created for this language:

S --> aSX |
X --> bXY |
Y --> cY |

Or am I not understand CFG and what I wrote doesn't make sense?

The grammar you wrote can generate the word "aaa", which is not supposed to be generated, if the grammar generates exactly $L$.

ergo, the grammar is incorrect for $L$. (which is great, since $L$ is not CFL, and no grammar can generate it!)


Min-cut in DAGs with unit edge weights I'm trying to better understand the min-cut problem for directed acyclic graphs. I understand that the minimum capacity cut has equal capacity to the max flow of a graph by the max flow-min cut theorem (https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem). This makes some sense to me but I'm confused as to what happens in a DAG with unit edge weights. In this case, there's three claims I'm trying to make:

The max flow of a DAG with unit edge weights has an upper bound equal to the sum of the number of edges entering all sinks. In other words, max flow is bounded by the sum of the indegree of all sink nodes.
Because all edges have the same weight, there are $\binom{n}{\text{max flow}}$ possible min-cuts where $n$ is the number of edges. In essence, if the max flow for a DAG is 3, then choosing any 3 edges would give you a min-cut.
If you apply the Ford-Fulkerson to identify a min-cut, it will effectively always include edges connected to the source node because those will immediately have their capacity maxed out and the algorithm returns the cut closest to the source(s).

These feel unintuitive to say the least but seem to hold true for the few small examples I tried to run through. In particular, the second statement seems very wrong to me. It seems to imply that any set of edges with capacity equal to max flow constitute a min-cut. While a min-cut definitely has capacity equal to max flow,  I'd guess the reverse statement that any set of cuts with a capacity equal to max flow is a min-cut isn't necessarily true (though I can't quite come up with a counter-example).

My question is, are any of the 3 claims above true?

Edit:

After thinking about it some more, I think I found a counterexample to my 2nd claim. In the DAG below, the max flow is 2 but cutting any two of the dotted edges wouldn't yield a partition.

Your first claim is true.

As for the second consider the following counterexample.
Consider the following DAG with edges $(s,v_1),(v_1,v_2), (v_1,v_3), (v_2,t), (v_3,t)$, where $s$ is the source and $t$ is the sink

                 (v2)
                 /  \
                /    \
        (s)-->(v1)   (t)
                \    /
                 \  /
                 (v3)

There is only one mincut while according to your claim there are $\binom{5}{1} = 5$. So your second claim is false.

For the third claim consider the following DAG with edges $(s,v_1),(s,v_2), (v_2,v_3), (v_1,v_3), (v_3,t)$

                 (v2)
                 /  \
                /    \
              (s)   (v3)---->(t)
                \    /
                 \  /
                 (v1)

The Ford-Fulkerson (or any other) algorithm should find min-cut as the only edge $(v_3,t)$ which is not connected to the source. The the third claim is false.


Is there any relationship between grammar being ambiguous and the language itself? According to my understanding, a grammar is ambiguous if it generate strings which can be interpreted in more than one ways ( that is , more than one parse tree), but when it comes to the language itself , is there any kind of relationship between the language itself and the ambiguous nature of a particular grammar that could generate it. Also , I am having another doubt , Is it possible that there should exist,infinite number of grammars that could generate the strings of a particular language ?

There exist context-free languages which have no unambiguous grammar. Such languages are called "inherently ambiguous".

On the other hand, there is no such thing as a language which does not have an ambiguous grammar; any grammar can be made ambiguous by duplicating some or all of the non-terminals.

The fact that inherently ambiguous languages exist is interesting, but they rarely if ever show up in real-life parsing problems.


What counts as a pipeline? From  Tanenbaum's Structured Computer Organization:

  Figure 2-4(a) illustrates a pipeline with five units, also called
  stages.

  If one pipeline is good, then surely two pipelines are better. One
  possible design for a dual pipeline CPU, based on Fig. 2-4, is
  shown in Fig. 2-5. Here a single instruction fetch unit fetches pairs
  of instructions together and puts each one into its own pipeline,
  complete with its own ALU for parallel operation.

  A different approach is used on high-end CPUs. The basic idea is to
  have just a single pipeline but give it multiple functional units, as
  shown in Fig. 2-6.  The definition of ‘‘superscalar’’ has evolved
  somewhat over time. It is now used to describe processors that issue
  multiple instructions—often four or six—in a single clock cycle. Of
  course, a superscalar CPU must have multiple functional units to hand
  all these instructions to. Since superscalar processors generally have
  one pipeline, they tend to look like Fig. 2-6.

I wonder what counts as a pipeline?

In Figure 2-4(a), a pipeline consists of 5 stages.

In figure 2-5, two pipelines share the same instruction fetch unit, but why isn't it a single pipeline?

In figure 2-6, a pipeline has multiple functional units, but why isn't it multiple pipelines?

Thanks.

In 2-4(a) each stage processes one instruction at a time using one unit for every stage. In 2-5 the instruction fetch unit remains the same but fetches two instructions that are then processed parallelly, each with its own unit. So we have two pipelines of cause. They are logically and physically seperated.
But as far as I understand, the main difference between 2-5 and 2-6 is that in 2-6 the CPU decides dynamically what the order of execution of the instructions will be (out-of-order-execution) so that it can eliminate dependencies and hazards. The multipipeline approach executes parallel but in-order. But a superscalar CPU will as well need all stages twice. I personally think it would be wrong to say a superscalar has one single pipeline.


What's the real difference between throughput and capacity of a network cable? I was preparing a presentation in work on GPON & other optical network technologies using documentation provided by a supplier, and the claim it made was "GPON networks have a capacity of up to 100Tbps".

Instantly that looked odd to me as I know the throughput of the most advanced version of InfiniBand only goes up to 280-290Gbps. I couldn't find any evidence that supported the supplier's claim, only turning up that the throughput of GPON was up to 2.5Gbps. The colleague who had been given the documentation I was working off said that the supplier had claimed that speed was independent of the devices on the network, and that it was limited only by the Optical Network Units (ONUs) and endpoint devices.

That seems a bit ridiculous considering the "data" in an optical cable is a pulse of light. Light travels (in a vacuum) at c, so surely the speed of any fibre-optic network is close to c, and in the same way the speed of electromagnetic wave propagation down a wire is 66 - 99% the speed of light, but I've never heard a CAT5 manufacturer claim their cables can support those speeds.

I brought it up with the supplier rep and he (derisively) let me know that "that's the capacity, not the throughput". I'm aware that to a lot of people the terms are interchangeable, but from a technical standpoint if throughput is the amount of data that can be sent over a network in a specified amount of time, what is capacity?

It would seem like the "capacity" of an optical fibre is "1 flash of light" as that's all it's likely to hold.

NB this question is about the science behind computer (or other data) networks, so I think it belongs here, despite references to particular hardware.

"Capacity", similar to many other terms, is a an overloaded word. In the example you bring, it seems that the meaning is equivalent to "throughput", i.e., the maximal "amount" of information a channel/network/etc. can transfer per time unit.

However, while these terms can be used interchangeably, to my ears "capacity" has the feel of a theoretical limit, while "throughput" has a feel of a practical limit. As in: "the capacity of a fiber channel is 1Gb/sec, which (due to coding, errors, and technical limitation)  leads to a maximal throughput of 986KB/sec (=of YOUR data)".

A different explanation which may be used in other settings is a one in which the capacity of a link is measured in relative terms, that is, it will be a ratio between 0 and 1, to be multiplied with a predefined  maximal rate of information transfer. This notation is useful when computing flows over the network.


Solve the recurrence relation T(n)=3T(√n)+lg(n) Master's Theorem is known to me, but I can't understand how to apply this theorem to this problem.
So, how I will find Θ of T(n)?

Define $X(n) = T (2^n)$.

Then $X(n) = T (2^n) = 3T(2^{n/2}) + n = 3X(n/2) + n$.

You solve the recurrence for $X(n)$, and $T(m) = X (\log m)$.


The role of the root switch after Spanning Tree Protocol has established a tree network in a LAN? In Spanning Tree Protocol, a root switch is selected at first, and then somehow, the shortest path from each other switch to the root is obtained. Thus we established a tree network.

My questions are:

  After the tree network is established, does the root switch act as a center in the network? In other words, all the traffic originated from other switch would first flow into the root switch along the shortest path and then routed to its destination by the root switch, also along the shortest path.
  If it's not the case, why does the protocol calculate a tree such that the path between each non-root switches and the root is minimized?  As far as I can see, a minimum spanning tree would work better, which is not difficult to calculate.

I can find no requirement that all traffic is routed through the root switch. For example, in A<-->B<-->C, with C the root switch, traffic fom A to B does not pass through the root switch.

The spanning tree protocol first selects a root switch. In Cisco, this is the switch with the lowest bridge ID. So the selection of the root is arbitrary. Now a tree is built that connects all switches, without creating cycles. Even if initially a minimum spanning tree is created because links with maximum bandwidth (minimum cost) are selected, at some future point this may no longer be when a link fails and a redundant link or path is enabled. This new link may result in the total tree not being a minimum spanning tree anymore. I can imagine that reconfiguring the whole tree to be minimum again can cause unwanted overhead.

I found this information on Wikipedia and Cisco. I am not a network guru so my answer may not be complete. I found no information that the initial tree created is minimum though it seems to meet the requirements and seems to follow e.g. Kruksal's algorithm.


Strict-Binary Tree - Same Post-order & Pre-order sequences? I'm going through some past exam papers for my course and I'm having trouble completing this one question.

It is as follows: "Draw a strict binary tree with seven nodes that has the same pre-order and post-order traversal sequence".

Is this actually possible? Wouldn't I need to visit the root node before anything else for both sequences, that isn't possible with post-order traversal in a strict binary tree right? Unless the tree consisted of a single node?

I assume I'm missing something obvious. Post-order = LRN, Pre-order = NLR.

It is possible only If all nodes have same value.


Finding related-node clusters I currently have an undirected weighted graph. I am trying to find a good algorithm for learning/finding a cluster of closely related nodes and/or loosely relationship within a cluster in a graph given a size of the cluster. For example, here the longer edges represent the farther relationship between 2 nodes. We identified 2 clusters where each cluster has a close relationship internally. I am new to computer science, could you please suggest an algorithm or a paper for this problem? Your help is really appreciated!

The problem you are trying to solve is called community detection or community structure, where several popular algorithms are listed, such as Girvan–Newman algorithm and Minimum-cut method.

You can find many related questions and answers on this site, on CrossValidate and on StackOverflow, such as the following:

Community detection in weighted directed graphs for fixed number of communities.
How to do community detection in a weighted social network/graph?
What are the differences between community detection algorithms in igraph?

A good introduction can be found at Community detection in graphs.

A recent survey can be found at Community detection in social networks.


Should compilers automatically translate operations into shortcuts? There are several coding operations that (I suspect) most compilers will change into more efficient operations at the assembly or machine code level. I have several questions about whether or not the compiler does any of this work, and if it's even best for the compiler to automatically do so.

(Note: These examples use C and C-like language syntax. However, just because i'm doing examples in C, doesn't mean I only want answers for the C compilers. I'm interested in how most major languages handle these things.)

The first is a += 1; vs a++;, where a is any integer variable. Both these codes ultimately result in the same thing (incrementing by 1), but a++ does it quicker somehow. I was self-taught for my first few languages and just never came across the a++ style, so I use the a += 1 style in all my private programming. However, of course later I discovered that a++ is more common when you only need to increment by 1. I believe the origins of it are from the old days where computers were super slow, therefore finding a shortcut for incrementing (or decrementing) by 1 was a huge deal. Now don't get me wrong, it could still make a difference today like in huge nested loops, and the most common place i see the shortcut is in loops anyway. Is there any reason why you would strictly want the slower a += 1 style? Incidentally, do most compilers automatically translate a a += 1 into a a++?

The second is dividing by a power of 2. b /= 8; can be shortcut to a simple bit shift by 3 bits to the right (towards the least significant bit, and filling in zeros on the MSB side)---as long as b is an integer. Should compilers make this translation, or is there some instance where you want the slower b /= 8 operation? Do compilers typically optimize this?

Can't think of any more simple types of shortcuts, but wouldn't be surprised if some exist.

First compilers may (and often will depending on the optimization level) do transformations far more complex than the one you describe.  You should not be concerned about the performance implication of the way you express the increment or the division before being sure that you are using a compiler for which it matters.

But there are some other implications.  Some are just stylistic (and here my recommendation is that you just follow what is the style of your organization, if you are in position to chose the style, chose one which suit you and don't second guess yourself about it every other week).  Other are semantic.

a += 1 and a++ are equivalent only if the context allows.  In C and C++, they are both expressions, and if the result of the expression is different (a += 1 is the incremented value; a++ is the non incremented value, ++a returns the incremented value).

a/8 and a>>3 are equivalent only if the value of a is positive or null.  For negative values, C and C++ the result is not determined by the C and C++ standards but left to the implementation(*).  The most common behavior gives the same result as a/8 for exact multiple of 8.  For negative values which are not a multiple of 8, a/8 has a result truncated towards 0 (i.e. -1/8 is 0) while a>>3 is truncated towards minus infinity (i.e. -1 >> 3 is -1).  You may know that the replacement is valid for your program but that is hard to determine for the compiler which will often not do the replacement or use a more complex one.

(*) Two reasons: the standards are defined in such a way that machines with ones' complement or sign and magnitude representation for signed values is possible and what is the natural result depend on the representation; some uncommon machines have only an unsigned shift.


What is discrete mathematics and why am I learning about it? I started computer science in university. And we started learning about Discrete and it's mathematics which is completely based on logic, which I understand. however, how is predicates, sets, proofs are related to computers ? I want to know the reason for learning these stuff?

Very roughly speaking, Discrete Mathematics is the body of material that a computer scientist needs to know. You can look at it as that part of mathematics which doesn't involve limits, continuity, differentiation, or integration. In set notation, we have Discrete = Mathematics \ Calculus.

The usual topics in a Discrete course and their applications to CS are

Propositional and predicate logic: used to establish the correctness of a program.
Proofs: used throughout CS, for things like establishing the closure properties of, say, regular languages.
Functions: obvious uses, since functions are ubiquitous in CS.
Sets: you can't do much in the theory of databases without them
Relations: again, fundamental for databases and also the basis for algorithms such as topological sorting
Recurrences: lists and trees can be viewed as recursively defined. Also, you can't do much to establish the time or space complexity of algorithms without being conversant with recurrence relations
Graphs and trees: when establishing the properties of networks
Counting: again, fundamental for the design and analysis of algorithms
Probability: for example, finding the average time complexity of an algorithm

Obviously, I've left out many more uses, but you get the idea. One could make the point that essentially all of CS beyond Programming I uses the concepts of Discrete in one way or another.


Is clrs really needed to be a computer scientist I want to dive in alghorithms and data structures and maybe AI this year. When I searched on internet everybody was recommending to read clrs. But I found it very complicated, because of the amount and the level of math in it. Is reading clrs really important to be a true computer scientist. If yes, how it can be easier to accomplish.
Note: I started reading Data Structures and Algorithm Analysis in C++, but I'm planning to read other books also.

To be a computer scientist you need to be able to reason abstractly.  The reasoning expected in CLRS is an example.  You can find books with titles such as Discrete Mathematics that will help with some of the prerequisite material, and with some of the reasoning strategies.


Is every regular language Turing-decidable, and how can we prove this? I know every regular language is Turing-acceptable, but does that imply it is Turing-decidable?

Every regular language is Turing-decidable and therefore Turing acceptable / recognisable (but note that Turing acceptable does not imply Turing decidable).

Suppose you are given a DFA D such that L = L(D). One can construct a Turing Machine T that simulates D. T's states will be similar to D's. On reaching the end of the input, if T is in a state that corresponds to a final state of D, T halts and accepts; otherwise it halts and rejects.


Understanding expected time bound for unsuccessful search in R-way tries As per Tries slides (page 17) from Algorithm 4th edition book by Robert Sedgewick, the asymptotic expected runtime for an unsuccessful search in $R$-way tries miss is $O(\log_R N)$. Can someone please explain how this number can be derived?

search in a binary search tree is log base 2 of N. Now you have a R-nary tree, so the running time would be log base R of N.


Does there exist a finite automaton for the given language? The question is simple and given as, alphabet $A$ is $\{a, b\}$, and language $L$ over $A$:

$L = \{w: w \in \{a, b\}^*, n(a) - n(b) = 1 \mod 3\}$. Here $n(a)$ = number of $a$ and $n(b)$ is number of $b$.

My answer is that it's not a regular language because the modular expression can be simplified as. $n(a) =n(b) +3k+1$ and hence there is a comparison in between the two alphabets. Further comparison are infinite but a finite automaton has only finite memory which are associated with states.

So we can say the above language is not regular hence no finite automaton for it. But there is a problem, I have read a book by Linz in which the above question was given stating that find the regular expression for it. I am a bit confused so any help will be appreciated. I would also be interested in a general approach to answer this type of question.

Your reasoning about comparisons would be correct, if there were infinitely many numbers. But there's only three of them modulo $3$.

The automaton can be constructed directly. You need three states, one for each of the residues: $0$, $1$ and $2$. Then every $a$-transition should correspond to an increment and $b$-transition to a decrement.


$O(n\log n)$- algorithm for finding tree root All numbers from $1$ to $n = 2^k-1$ are written in unknown way in a full binary tree of height $k$.  We say that a number $t$ lies between $i$ and $j$ if after removing $t$ from the tree we obtain that $i$ and $j$ are in different connectivity components. Propose an algorithm for determining a number in the root of tree asking $O(n\log n)$ questions of the type "Is $t$ lies between $i$ and $j$"? The answer may be "yes" or "no".

I will be gratefull for hints and ideas.

Routine 1
Firstly, observe that only the root node disconnects the tree into exactly two equal connected components of size $2^{k-2}-1$. All other nodes disconnect the tree into three or zero connected components. We have the following $\mathcal{O}(n)$ approach to check if a given node is the root.

Let the node to check be $x$.
Pick another node $y \not= x$
Iterate through all other nodes $z \not\in \{x,y\}$ and ask if $x$ disconnects $y$ from $z$.
If there are $2^{k-2}-1$ nodes in the connected component of $y$, then $x$ is a root, else it isn't.

Routine 2 Now, let's present an $\mathcal{O}(n)$ algorithm to identify leaves. Observe that a random node has $\ge 0.5$ probability of being a leaf node. Hence our algorithm is -

Pick a random node in the tree, say $x$.
Pick another random node $y$.
If $x$ does not disconnect $y$ from $z$, for all valid $z$, then $x$ is a leaf node in the tree.
Repeat steps 1, 2 and 3 till you obtain a leaf.

The expected number of queries used by this algorithm is $\mathcal{O}(n)$.

Routine 3 Now let's make the next observation. There are $2^{k-1}$ nodes in the last level of this complete binary tree. Colour these leaf nodes with two colours, red and blue. A leaf is coloured red if it belongs in the left sub tree of the root and blue otherwise. Using Routine 2, we will try to find a pair of leaf nodes one of which is red and the other is blue in $O(n)$ queries. Here is how -

Find any leaf node using the algorithm in Routine 2. Call this leaf node $u$.
Find a different leaf node, call this $v$.
$u$ and $v$ are of different colour if and only if exactly $2k-1$ nodes  can disconnect $u$ from $v$, i.e., the nodes on the path that connect $u$ to $v$ (We assume that deleting $u$ will disconnect $u$ from $v$). This can be verified in $\mathcal{O}(n)$ queries as well by iterating over all nodes once.
Repeat steps 2 and 3 till you find the desired leaf node.

The probability that a random node is a leaf node and is of a different colour than $u$ is $\ge 0.25$. Hence the expected number of queries asked in this algorithm is also $\mathcal{O}(n)$.

Now that we have our two leaf nodes of different colours, we are ready to make the final observation, i.e., the root node must be one of the $2k-1$ nodes that can disconnect $u$ from $v$. Thus there are $2k-1 = \mathcal{O}(\log{n})$ candidates for the root node. We can iterate through each of them and check if they are the root using Routine 1.

Thus this algorithm uses $\mathcal{O}(n\log n)$ queries.

EDIT The final step can be improved to $\mathcal{O}(\log^2{n})$ by running Routine 1 on just the $2k-1$ candidates to find the node that splits the path from $u$ to $v$ into two equal connected components. Thus the problem can be solved in $\mathcal{O}(n)$ queries as well.


Applying Brewer's theorem (CAP) to a single node I'm going through Brewer's theorem and its proof by Nancy Lynch and Seth Gilbert. But the paper left me with one question. What prevents the theorem from being applicable to a single node?

I haven’t encountered any explicit definition of network partition that restricts its applicability to a network. There are some hints in [1] that suggest that a network partition with a single node would mean cutting off all communication to that node itself. This doesn’t make a whole lot of sense to me because you could always have a partition with all the service nodes on one side and the client node on the other. No service could possibly tolerate that.

A single node data object can be consistent and available if requests sent to it get through. To me, the definition of a network partition and where it applies leaves something to be desired. What am I missing here?

[1] Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services by Seth Gilbert and Nancy Lynch

In my opinion, the CAP theorem is applicable intentionally to distributed systems. To quote the article "Perspectives on the CAP Theorem @ IEEE Computer'2012 by Gilbert and Lynch":

  Brewer first presented CAP in the context of a Web service implemented by a set of servers distributed over a set of geographically diverse datacenters. Clients issue requests to the service, which sends back responses.

In this context, the "network" in CAP theorem refers to communications among servers (instead of communications among clients or between clients and servers). This can be justified by the following two arguments.

To quote the above article again (with emphasis added):

  Unlike the other two requirements, partition tolerance is really a statement about the underlying system rather than the service itself: communication among the servers is unreliable, and the servers can be partitioned into multiple groups that cannot communicate with one another.

In the proof of the CAP theorem in the above article, it says,

  Consider an execution in which the servers are partitioned into two disjoint sets: $\{p_1\}$ and $\{ p_2, \ldots, p_n\}$. Some client send a read request to server $p_2$.

The proof followed is based on the communication among the two disjoint sets of servers.

To summarize, CAP theorem (again, it is my own opinion) does not consider the situation in which client nodes and server nodes are partitioned. After all, we can do almost nothing in this bad situation. In other words, CAP theorem assumes that the communications between clients and servers behave well and focuses on the theory and implementation of the distributed service itself.


How can a language whose compiler is written in C ever be faster than C? Taking a look at Julia's webpage, you can see some benchmarks of several languages across several algorithms (timings shown below). How can a language with a compiler  originally written in C, outperform C code?

Figure: benchmark times relative to C (smaller is better, C performance = 1.0).

There is no necessary relation between the implementation of the compiler and the output of the compiler. You could write a compiler in a language like Python or Ruby, whose most common implementations are very slow, and that compiler could output highly optimized machine code capable of outperforming C. The compiler itself would take a long time to run, because its code is written in a slow language. (To be more precise, written in a language with a slow implementation. Languages aren't really inherently fast or slow, as Raphael points out in a comment. I expand on this idea below.) The compiled program would be as fast as its own implementation allowed—we could write a compiler in Python that generates the same machine code as a Fortran compiler, and our compiled programs would be as fast as Fortran, even though they would take a long time to compile.

It's a different story if we're talking about an interpreter. Interpreters have to be running while the program they're interpreting is running, so there is a connection between the language in which the interpreter is implemented and the performance of the interpreted code. It takes some clever runtime optimization to make an interpreted language which runs faster than the language in which the interpreter is implemented, and the final performance can depend on how amenable a piece of code is to this kind of optimization. Many languages, such as Java and C#, use runtimes with a hybrid model which combines some of the benefits of interpreters with some of the benefits of compilers.

As a concrete example, let's look more closely at Python. Python has several implementations. The most common is CPython, a bytecode interpreter written in C. There's also PyPy, which is written in a specialized dialect of Python called RPython, and which uses a hybrid compilation model somewhat like the JVM. PyPy is much faster than CPython in most benchmarks; it uses all sorts of amazing tricks to optimize the code at runtime. However, the Python language which PyPy runs is exactly the same Python language that CPython runs, barring a few differences which don't affect performance.

Suppose we wrote a compiler in the Python language for Fortran. Our compiler produces the same machine code as GFortran. Now we compile a Fortran program. We can run our compiler on top of CPython, or we can run it on PyPy, since it's written in Python and both of these implementations run the same Python language. What we'll find is that if we run our compiler on CPython, then run it on PyPy, then compile the same Fortran source with GFortran, we'll get exactly the same machine code all three times, so the compiled program will always run at around the same speed. However, the time it takes to produce that compiled program will be different. CPython will most likely take longer than PyPy, and PyPy will most likely take longer than GFortran, even though all of them will output the same machine code at the end.

From scanning the Julia website's benchmark table, it looks like none of the  languages running on interpreters (Python, R, Matlab/Octave, Javascript) have any benchmarks where they beat C. This is generally consistent with what I'd expect to see, although I could imagine code written with Python's highly optimized Numpy library (written in C and Fortran) beating some possible C implementations of similar code. The languages which are equal to or better than C are being compiled (Fortran, Julia) or using a hybrid model with partial compilation (Java, and probably LuaJIT). PyPy also uses a hybrid model, so it's entirely possible that if we ran the same Python code on PyPy instead of CPython, we'd actually see it beat C on some benchmarks.


Oracle machine solving halting problem for other oracle machines Could someone give me a simple explanation why an oracle machine that can solve the halting problem for standard Turing machines, is however unable to solve the halting problem for other such oracle machines?

I have tried searching for the answer online but could not find any that really answered the question.

The proof that a Turing machine with an oracle for $X$ can't solve the halting problem for Turing machines with an oracle for $X$ is identical to the proof that an ordinary Turing machine can't solve the halting problem for ordinary Turing machines.


Converting final state PDA to empty stack PDA I'm having a problem understanding this conversion. Let's say we have a CFL like this:
$ { a^nb^m : n > m } $

A final state acceptance PDA for this language would push $A$ symbols in the stack for every 'a' input, and pop them for every 'b' input. If the stack has no more $A$s while we still have 'b' inputs to process, the automaton goes in a non-accepting state, and the string is not accepted.

To convert this to an empty stack acceptance PDA, I add the two states, one before the previous start state, and another state after the last to empty the stack. Whenever the inner automaton goes to the accepting state, it also moves to the empty-stack state with an $\epsilon$ transition.

If I test the string $aabbb$, after we process the first 3 characters, we still have an $A$ symbol in the stack, but the automaton moves to the empty-stack state with an $\epsilon$, it empties the whole stack, therefore the string is accepted.

Where is my mistake in this reasoning?

Your description of the construction is wrong. The new automaton has a new initial stack symbol, from the new start state it places the original PDA's initial stack on top of it and moves to the original's start state. The new initial stack can only be removed in a new state that is entered via $\epsilon$ from final states, and in this new state all that is done is to slurp down the stack's contents.

This is activated from any final state, and the automaton can end up with empty input and empty stack only if the original reached the final state at the end of the input.


Can I assume every clause of 3SAT has one positive literal? Can we assume that each clause in 3SAT contains at least one positive literal? That is, there is no clause with all negative literals (but it is fine that there is a clause with all positive literals).

No, you can't.
If each clause has at least one positive literal, then, by assigning TRUE to all variables, one gets all clauses satisfied.


Do regular languages belong to Space(1)? I was wondering, if we take some regular language, will it be in Space(1)?

For a regular language X, for instance, we can construct an equivalent NFA that matches strings in the regular language.

But I cannot see why is X in Space(1).

If it is true, why is X or any other regular language in Space(1)?

A regular expression can be transformed into an NFA as you say. And an NFA can be transformed into a DFA. This latter transformation is exponential in the worst case (in terms of the size of the original NFA), but that is irrelevant. The amount of time this transformation takes is independent from the size of the input, and is thus $O(1)$.

Similarly, the size of this DFA is also independent from the size of the input, so storing it takes $O(1)$ space. No further space is needed other than the DFA, and thus a recognizer for a regular expression can run in $O(1)$ space.


Computing the right tangent of two convex hulls My question deals with the algorithm of computing the convex hull in 2D by Preparata.

Let us assume we have two sets, $A$, $B$, of points in the plane. Let $CH(A)$ and $CH(B)$, denote the convex hulls of the two sets, A and B respectively. And suppose that $y(a) < y(b)$ for all $a \in A$ and $b \in B$.

Let $CH(A) = \{a_{0},...,a_{n}\}$ and $CH(B) = \{b_{0},...,b_{m}\}$ such that we have indexed both sets to be clockwise sequences.

Now there is $k$ such that $x(a_{k}) = \text{max}(x(a_{i}))$ for all $ 0\leq i \leq n$ and $j$ such that $x(b_{j}) = \text{max}(b_{l}))$ for all $0 \leq l \leq m$.

Now our first task is to find the common tangents of $CH(A)$ and $CH(B)$. My question is about finding the right tangent.

Now let $\alpha_{i, i+1}$ denote the slope of the two points $a_{i}$ and $a_{i+1}$; $\beta_{j,j+1}$ denote the slope of the two points $b_{j}$ and $b_{j+1}$; $\gamma_{i,j}$ denote the slope of the two points $a_{i}$ and $b_{j}$ (all indices are taken mod n and mod m).

Suppose $a_{i^{*}}$ and $b_{j^{*}}$ denote the two endpoints of the right tangent.
Preparata states the two endpoints of the right tangent satisfy the following:

(1) $i^{*} > 0: \alpha_{i^{*},i^{*}+1} < \gamma_{i^{*},j^{*}} \leq \alpha_{i^{*}-1,i^{*}}$

(2) $i^{*} = 0 : \alpha_{0,1} < \gamma_{1,j^{*}}$

(3) $j^{*} > 0: \beta_{j^{*},j^{*}+1} \leq \gamma_{i^{*},j^{*}} < \beta_{j^{*}-1,j^{*}}$

(4) $j^{*} = 0: \beta_{1,2} \leq \gamma_{i^{*},1}$

However I found that if we take $A = \{(0.2,0.2),(0.3,1.3),(1.2,1)\}$ and $B = \{(2,2),(2,3),(2,3)\}$ then we have the following picture:

We see that the left endpoint (i.e. the endpoint in $CH(A)$) of the right common tangent should be $(0.2,0.2)$ and the right endpoint (i.e. the endpoint in $CH(B)$) should be $(3,2)$ .

However the criterion that Preparata claims does not select $(0.2,0.2)$ as the left endpoint, since it does not satisfy $(2)$, but $(0.3,1.3)$. Why does this occur? Does Preparata's algorithm have some other claim that it needs to be correct?

Here is a link to the original paper:

http://www.cs.jhu.edu/~misha/Spring16/Preparata77.pdf

The section I'm referring to is called "Merge Algorithm for Two-Dimensional Sets."

The paper of Preparata and Hong says:

We let $l_A$ and $r_A$ be two points of A such that $x_2(l_A) = \min_i {x_2(a_i)}$ and $x_2(r_A) = \max_i{x_2(a_i)}$; similarly $l_B$ and $r_B$ are defined in B.

and:

Without loss of generality, we shall also assume that $r_A = a_1$ and $r_B = b_1$.

So, in this notation, vertices in your two polygons will be numbered differently:
$$A=((1.2,1),(0.2,0.2),(0.3,1.3))$$
$$B=((3,2),(2,2),(2,3))$$
In simple words, the algorithm starts from rightmost vertices on both polygons and continues clockwise potentially until leftmost vertices - so, only lower sides of both polygons will be involved. Tangential vertices $(0.2,0.2)$ and $(3,2)$ will be found.
This paper has been published long time ago, and since then this algorithm has been clarified and simplified. The newest version of it starts from the rightmost vertex on the left polygon and the leftmost vertex on the right polygon, and continues clockwise for the left polygon and counterclockwise for the right polygon (to find lower tangential line). Also they usually check a vertex location relative to a line using the dot product instead of calculating and comparing slopes - because the tangential vertex has to have both its neighbors on the same side of the tangential line. For more information, pictures and code - please see this monograph, Section 3.8.


How many size $s$ circuits from $\{0, 1\}^n \to \{0, 1\}$ are there? For simplicity, we can assume that only NAND gates are allowed.  An asymptotically correct solution is all I really need.

Thanks!

Hint: Each of the $s$ gates is connected to two other gates or inputs, for a total of $(s+n)^2$ possibilities. This gives a rough upper bound which isn't tight, but is good enough for many purposes, for example to show that some functions require circuits of size $\Omega(2^n/n)$. See Steurer's notes, for example.


How to encode date as input in neural network? I am using neural networks to predict a time series.
The question I'm facing now is how do I encode date/time/serial no. of each input set as an input to the neural network?

Should I use 1 of C encoding (used for encoding categories) as described here?

Or Should I just feed it the time (in milliseconds since 1-1-1970)?

Or is feeding it the time unnecessary as long as I feed it the rest of the data chronologically?

Neural Networks are not magic. If you treat them like they are and just throw data at them without thinking you're going to have a very bad time.

You need to stop and ask youself "Is milliseconds since 1970 actually going to be predictive of the event I'm interested in?" The answer you should arrive at immediately is no. Why? For every instance you actually care about (events in the future, the past already happened) the time variable will take on a value that is greater than any value the time variable will take in your training data. Such a variable is very unlikely to help. Even worse it is likely to cause overfitting (a serious problem for powerful non-linear models like neural networks) if you aren't careful.

Now what might make sense is a variable like week of the year or month that could help you model seasonal or annual effects. I've done some work in agricultural disease prediction where Julian day ended up being a very important variable. Based on this experience, I suspect you'd be better off encoding this type of variable as a categorical variable rather than ordinal, your experience may very. Notice that month or week of the year are repeatable events that one is likely to see many times in your training data and it is possible to explain why such a variable could impact a financial outcome. Contrast this with milliseconds since 1970 which is just a monotonically increasing value.

Lastly, from your statement "Or is feeding it the time unnecessary as long as I feed it the rest of the data chronologically?" it sounds like you might not have a very good grasp of how neural networks work. With a standard feedforward neural network the order you feed the network your data is going to have no impact on the predictions. Order may impact training if you're using stochastic or mini-batch gradient descent, but this is only an artifact of the iterative (as opposed to batch) training method. If you want to model temporal dependence with a neural network you'll need to use something like a sliding window or a recurrent neural network.


Finding a strong loop invariant Pseudocode:

if n < 2
    return false
while n != 1
    if n % 2 != 0
        return false
    n = n/2
return true

The loop will terminate when n is odd. If n = 1, true is returned and that means that n0 was a power of 2. Otherwise it's false.

I'm new at this and struggle with the proving the power of 2 part for before and during iterations and after the loop terminates. Also what does a loop invariant look like for a true vs false return on a loop?

Is it reasonable to say something like:

at the every iteration i, 1 <= n <= n0/(2^i)
true returned when n = 1 and n0 is a power of 2
false returned when n is odd and n > 1

Is it possible to even make strong loop invariant here without referencing the initial value of n?

One loop invariant is "$n_0/n$ is a power of 2 and $n \geq 1$", where $n_0$ is the original value of $n$.

The loop invariant holds initially (before the first iteration of the loop) since $n_0 = n$, and $n_0 \geq 2$. As for what happens in the loop, there are several cases:

If $n$ is odd then $n = 2k+1$ for some $k$; since $n > 1$ (otherwise the loop would have terminated), moreover $n \geq 3$, and so $n_0 = 2^t (2k+1)$ for some $t \geq 0$ and $k \geq 1$, showing that $n_0$ isn't a power of 2.
If $n$ is even then the value of $n$ in the next iteration is $n' = n/2 \geq 1$, and so $n_0/n' = 2n_0/n$ is also a power of 2.

If the loop terminates naturally then necessarily $n = 1$, and so the loop invariant guarantees that $n_0 = n_0/n$ is a power of 2.

Finally, since $n/2 < n$, the value of $n$ keeps decreasing; since always $n \geq 1$, it cannot decrease forever, i.e., the loop terminates. In fact, the running time is $\Theta(\log n)$.


Difference between weak and strong AI I'm trying to understand the difference between weak and strong AI. For an example, let's say we would pass the turing test - would it show strong AI or weak AI then?

I don't believe that this is standard terminology, but more philosophical. It was mentioned  by John Searle in his "Chinese room argument". As I understand, strong AI is about computers really being intelligent such as having a mind and thus a conciousness, and weak AI refers more to computers being able to simulate the behaviour of human intelligence on only specific problems (think chess, etc.)

Now, the question is - if we would be able to pass the turing test, would it be called weak or strong AI then? Could it be strong AI due to the fact that the turing test is not limited to a certain area or a specific problem?

I came across it on wikipedia: http://en.wikipedia.org/wiki/Chinese_room

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

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


What is the worst case time-complexity of removing the root of a Binary Search Tree? My answer is constant time O(1) since an implementation would naturally have the pointer to the root. However, the solution guide I am looking at argues it is O(logN).

I hope I'm not misunderstanding you, but keep in mind that you don't just have to find the node you want to get rid of. You also have to replace it with another node to still have an intact tree afterward.

For it to then still be a binary tree that node needs to be closest to the root in value.
The worst case will turn out to be that all nodes have two children, and in that case the node closest in value to the root is either the leftmost leaf on the right side or the rightmost leaf on the left side.

So with deletion we're looking at two operations to perform:

finding the element to delete (that's $\mathcal{O}(1)$ when we're deleting the root, as You've correctly pointed out)
finding a replacement for the root (turns out to be $\mathcal{O}(\log n)$ as we'll see...)

To find that replacement you have to traverse a full path from root to leaf, which in a binary tree could be anywhere between length $\log n$ and $n$.
But note that if the path were any longer than $\log n$ nodes, we'd have to have some node with only one child, in which case we can simply move that node up a level and save ourselves any further effort.
(This also kind of shows that the worst case is in fact what I've claimed above since in any other case we could stop earlier.)

Thus at worst we'll have $\mathcal{O}(\log n)$.


For a turing machine which computes $y$ with argument $x$, how much does the descriptional length of a machine producing $y$ without input increases Let $f$ be some function in some programming language (like C), and we need $n$ bits to store this function. Suppose we have some fixed value $v$ for the argument, then let

  g() { f(v) }

be the function with no argument which just calles $f$ with $v$ as an argument. Then we need $n + |v| + C$ bits to store it, where $C$ is some constant which takes account of the additional bits needed to declare $g$, and this is independent of $v$ and $f$.

So in any programming language so far, to go from programs accepting parameters, to the one for a fixed parameter the desriptional complexity  raises up at most by a fixed constant plus the descriptional length of $v$.

Does the same hold for Turing-machines? If I have a Turing-Machine which for input $x$ produces $y$, then to have a machine without accepting parameter to produce $y$ I can built one that first writes $x$ and then runs $M$, and a general machine that writes $x$ for any $x$ would be one that saves the tokens of $x$ in its states and writes them one after another. If I look at how instructions are specified in Turing machines, then we see that for $x$ we need $|x|\cdot C$ bits (with $C > 1$) then to store this additional machine, hence given $M$ with $M(x) = y$ we get a machine $M_x = y$ without arguments with
$$
 |M| + C|x| + C'
$$
needed bits, where $C > 1$ and $C'$ account for some additional setup independent of $M$ and $x$.

But would it be possible to built a Turing machine $M_x$ with $M_x = y$ without input which has descriptional complexity at most $|M| + |x| + C'$ for some constant $C'$ independent of $M$ and $x$? Like above for ordinary programming languages?

First of all, there are two notions of Kolmogorov complexity, that Li and Vitanyi (in their classic monograph) call algorithmic complexity and algorithmic prefix complexity. Each of them is defined with respect to a universal computer which has a certain property.

Algorithmic complexity $C(x)$ has the property that for every computer $P$, if we denote by $C_P(x)$ the complexity of $x$ with respect to $P$, then $|C(x) - C_P(x)| \leq \gamma_P$, where $\gamma_P$ depends only on $P$. This property is known as universality.

Algorithmic prefix complexity $K(x)$ uses a computer in which the valid programs form a prefix code (a prefix computer), and we only require the universality property for prefix computers.

The actual definitions are slightly more complicated, since we also need to define, at the same time, the notion $C(x|y)$ or $K(x|y)$.

If you want to use some encoding of Turing machines as your definition of Kolmogorov complexity (of either kind), you need to use an encoding which is universal. But the point of Kolmogorov complexity is that which computer you use doesn't matter, since the resulting notions of Kolmogorov complexity only differ by an additive constant.

Finally, the Kolmogorov complexity analog of your "substitution" rule is
$$
K(x) \leq K(x|y) + K(y) + O(1).
$$
In fact, more is true:
$$|K(x|y) + K(y) - K(x,y)| = O(1). $$
This holds for prefix complexity.


Sort an array of $n$ elements when only $\log n$ are not in place I'm trying to understand how can I sort an array of $n$ elements when only $\log n$ are not in place.

I heard that sorting an array with at most $I$ inversions has complexity $O(n\log(I/n))$. Because there are $\log n$ elements that are unsorted, in my case there are at most $n\log n$ inversion.

The answer to the question is $O(n\log\log n)$ which is consistent with the formula, but I can't understand the"idea behind it, or which sorting algorithm achieves it.

Assuming that "$k$ elements out of place" means that there exist $k$ elements whose deletion leaves the rest of the array sorted, there's an $O(n+k\log k)$-time algorithm to sort the whole array.

In a nutshell, compute an increasing subsequence of length at least $n-2k$, sort the others, and merge. The former can be accomplished in time $O(n)$ by a simple stack algorithm that pushes elements one at a time and pops the top two whenever they're out of order. The optimal deletion strategy must delete at least one of these elements, so the total damage is upperbounded by $2k$  deletions.


Adjacency matrix and recognizing hierarchy? I'm currently learning about graphs and I have some questions regarding adjacency matrices. Given an arbitrary adjacency matrix:

Is there any way to tell if that matrix represents a hierarchal graph structure? Obviously in the above case it's not.

Something like:

I know the rows of and i x i  adjacency matrix represent the out-degree of ith vertex and columns represent the in-degree of the ith vertex. But is there any way to tell just by looking at the general structure of the adjacency matrix if the graph is hierarchical (At least, for smaller matrices as above) ?

By definition you can check if a graph is a tree (regardless of its representation) with these facts:

The graph does not have cycles.
It only has a single connected component.

The first condition can be checked with a simple DFS checking if there is a back edge. The connected components can be counted using either DFS or BFS.

Regarding to an adjacency matrix, every tree is a bipartite graph. See this, but keep in mind that proving that a a graph is bipartite does not mean it is a tree.


Given a set of points, find all collinear subsets General problem

Given a space $S$ which is $N$-dimensional, bounded, and quantized
Given a set $P$ of unique points
Find the set of collinear subsets of $P$, each containing at least 3 points
One point can exist in multiple subsets

Specific problem

I am creating a 4D, 5 by 5 by 5 by 5 tic tac toe game. Each dimension is bounded by $\left(0,4\right)$ and quantized by $1$. I have a set of points within that space. Each point is associated with a player (the number of players is not bounded), so that could be treated as an additional bounded, quantized dimension.

I need to find any and all combinations of 5 points (played by the same player) that are collinear.

Question

What is an efficient way to do this?

Here is a simple algorithm.  For each way to choose 2 points from $P$, find the line that goes through those two points and then find all other points from $P$ that are on the line.   If this yields at least 3 points, output it.  Continue until you've iterated over all possible ways to choose 2 different points rom $P$.

The running time will be at most cubic.  In particular, suppose there are $m$ points in the set $P$.  Then there are ${m \choose 2} = m(m-1)/2$ ways to choose two different points from $P$.  Thus, you'll do $\Theta(m^2)$ iterations.  Then you can find all other points on the line in at most $O(m)$ time, so the total running time is $O(m^3)$.

There are probably more efficient algorithms.  However, this might probably suffice for your needs.  Specifically, in your example, you'll have $m \le 5^4$.  Also, each iteration can be done faster than $O(m)$ time: given two points $p,q \in P$, you only have to check at most 3 other cells in the tic-tac-toe space.  So, in your situation, the running time is $\Theta(m^2)$, and $m^2 \approx 2^{18.6}$, so this should be pretty fast.


What is handle in bottom up LR parsing? I was taking course on compilers by Alex Aiken. You can find the slide discussing handles on this page. On the page of the slide, the instructor defines handle as follows:

  Assume a rightmost derivation
  $\require{AMScd}$
  \begin{CD}
  S @>{\text{*}}>> \alpha X\omega @>{}>>\alpha\beta\omega
\end{CD}
  Then $\alpha\beta$ is a handle of $\alpha\beta\omega$.

When I referred the Dragon Book, it says:

  if $\require{AMScd}$
  \begin{CD}
  S @>{\text{*}}>> \alpha A\omega @>{}>>\alpha\beta\omega
\end{CD}
  then production $A\rightarrow\beta$ in the position following $\alpha$ is a handle of $\alpha\beta\omega$. For convenience, we refer to the body $\beta$ rather than $A\rightarrow\beta$ as a handle.

So which one is correct? Is $\alpha\beta$ called as handle, or just $\beta$?

"When I use a word," Humpty Dumpty said, in rather a scornful tone, "it means just what I choose it to mean—neither more nor less."

Charles Dodgson -- who wrote those words under the name of Lewis Carroll -- was a brilliant mathematician with a taste for whimsy, all of which provide an interesting undercurrent to works such as Through the Looking Glass. Humpty's creed could have been taken directly from Dodgson's textbook on Symbolic Logic:

[Authors of other textbooks on logic]… speak of the Copula of a Proposition “with bated breath”, almost as if it were a living, conscious Entity, capable of declaring for itself what it chose to mean, and that we, poor human creatures, had nothing to do but to ascertain what was its sovereign will and pleasure, and submit to it.
In opposition to this view, I maintain that any writer of a book is fully authorised in attaching any meaning he likes to any word or phrase he intends to use. If I find an author saying, at the beginning of his book, “Let it be understood that by the word ‘black’ I shall always mean ‘white’, and that by the word ‘white’ I shall always mean ‘black’,” I meekly accept his ruling, however injudicious I may think it. (Dodgson18??, p. 166)

This is particularly true in computer science, in which most papers seem to be about 75% definitions, loosely interconnected with proofs. The definitions need to be repeated in every paper because there are often conflicting uses of the same phrases in the literature. This often creates a kind of cognitive dissonance for learners, who have been schooled in a model of teaching which presents definitions as received truth:

To be more accurate, we might say that what eludes the
students is the distinction between a dictionary definition as
a description of pre-existing objects and a mathematical
definition as the chosen basis for deduction, one which
serves to determine the nature of the objects. (AS2002, p. 33, emphasis added).

The distinction is important. Definitions are a way to organise one's understanding of the world, and the liberty to choose categories appropriately is an important part of mathematical thinking. So Dodgson's advice and Simon & Alcock's observation, both directed at teachers of mathematics, seem to me to continue to be relevant.
On that basis, I assert that Alex Aiken has every right to define "handle" as he sees fit. Perhaps he has a good reason to use this particular definition, which will be revealed later. Or perhaps not, because we all make mistakes, even famous presenters of popular courses. The test will come later, when the definition proves to be useful (or not). Because definitions (in the mathematical sense) are neither right nor wrong; they are simply useful or not.
However, like Dodgson, I too reserve the right to think that a definition may be injudicious, and it seems to me that Aiken's definition of handle as being the entire input up to the point of reduction is not as useful as the normal definition of handle as a production which could be reduced at a given point of input. (As the authors of the Dragon book point out, although they often talk about handles as though they were a subsequence of the stack, they actually define the handle to be the production itself.)
Both definitions involve the necessary fact that a handle is rooted in a moment in the parse. The fact that the right-hand side of a production happens to match the top of the stack does not necessarily make that production into a handle; it is only a handle because the reduced stack could appear in a rightmost derivation.
Aiken later talks about the handle as something which can be reduced, which implies that it is not simply the stack at the point of the reduction, as his definition appears to say, but the stack at the point of the reduction with a marker indicating what reduction will take place. If it were just the stack, an ambiguous grammar would have a single handle, which obscures the concept of ambiguity. I prefer to say that a grammar is ambiguous if there could be more than one handle at a point in the parse.
I have no doubt that Aiken, Aho&al, and, less importantly, I have the same concept of what a handle is for. And the essential point of that concept is that a reduction (or right-hand side) is a handle for the entire parser stack, not just a reduction whose right-hand side happens to match the top of the stack.
This would all be a minor point if it were not for the quiz Aiken inserts into the course immediately following his definition, which asks the student to focus on the definition rather than the use (in the sense highlighted by Alcock & Simpson).
[AS2002] Alcock, L. and Simpson, A. P. (2002) 'Definitions : dealing with categories mathematically'. In For the learning of mathematics, vol. 22 No. 2, pp. 28-34.
[Dodgson1896] Dodgson, Charles Ludwig (published under the name Lewis Carroll) (1896), 'Symbolic Logic', 2nd edition.


Why a language specified by a regular expression is not a complement of a given language? I am taking a compiler MOOC online on my own time. The class is self paced. There is a question with an answer but I can't understand why the answer is correct.
Here is the question.

For any language $L$, the complement of the language (usually written
$L′$) is defined as the language that consists of all the strings that
are NOT in $L$. That is,
$L′=Σ^*−L$
It turns out that the complement of any regular language is
also a regular language. Which of the following regular expressions
define a language that is the complement of the language defined by
the regular expression: $1(01)^*$?

$(10)^*+\big((10)^*0(0+1)^*\big)+\big(1(01)^*1(0+1)^*\big)$
$\epsilon + (0(0 + 1)^*) + ((0 + 1)^*0) + \big((0 + 1)^*(00 + 11)(0 + 1)^*\big)$
$(0 + \epsilon)\big((1 + \epsilon)(0 + \epsilon)\big)^*$
$(10)^*$

Correct answers are 1 and 2. I can't understand why 3 and 4 are not correct as well since the strings generated by these languages are also not in $L$.
Any explanation is greatly appreciated.

The complement of a language $L$ should contain all strings not in $L$. Your language $L$ doesn't contain the word $0$, which the language $(10)^*$ also doesn't contain – so $(10)^*$ can't be the complement of $L$.


Proof of 0/1 knapsack optimal substructure I'm trying to understand why exactly the 0/1 knapsack problem actually has the optimal substructure property.

Let $E$ be the set of items to consider and $v$ and $w$ the value and weight functions defined over $E$.

Now, suppose that, among all solutions weighing at most $W$, $S \subseteq E$ is the best solution. How can I prove that $S - \{x\}$ is the best solution weighing at most $W - w(x)$, considering the set of possible items as $E - \{x\}$? I tried to suppose that $S' \subseteq E - \{x\}$ is a better solution (that is, $v(S') > v(S - \{x\})$ and $w(S') \leq W - w(x)$), but I get stuck when I try to find a contradiction.

Any help?

Thanks in advance!

Suppose that some $S'\subseteq E-\{x\}$ is a better admissible solution than $S-\{x\}$. Then $S'\not= S$, the value is more, $v(S') > v(S-\{x\})$, and $x\not \in S'$, and $w(S')\leq W-w(x)$, as you indicated. Now add $x$ to $S'$ to obtain $S''=S'\cup \{x\}$. What will be the value and weight of this new subset? And how does it compare to the value and weight of $S$? Let's write it out:

$w(S'') = w(S')+w(x) \leq (W-w(x))+w(x) = W$ so $S''$ weighs less than $W$, so $S''$ is an admissible solution, so it makes sense to compare their values.

$v(S'') = v(S') + v(x)$. By assumption, $v(S')>v(S-\{x\})$, so, adding $v(x)$ to both sides of this last equation, $v(S')+v(x)>v(S-\{x\})+v(x) = v(S)$. Hence $v(S'')>v(S)$. But this is a contradiction, because $S''$ is supposedly a better admissible solution while you had presumed that $S$ was the best admissible solution. $\square$

By admissible I mean that the knapsack weighs less than the maximum weight.


Under which field of computer science does cloud computing fit? I am trying to categorise subfields of computer science. Wikipedia does a good job of it.

However, it cannot fit cloud computing, virtual machines, containers and related technologies in any of the mentioned fields.

Does it fit under computer architecture or do we need a new sub-field?

I know categorising topics under subfields might not seem that useful but it really helps me put things into perspective.

According to the ACM classification, cloud computing belongs to:

Distributed architectures, under Architectures, under Computer systems organization.
Network services, under Networks.
Distributed systems organizing principles, under Software system structures, under Software organization and properties, under Software and its engineering.
Storage architectures, under Information storage systems, under information systems (as Cloud based storage).

So cloud computing is at the intersection of Computer architecture, Networking, Software engineering, and Information systems.

Cloud computing could also be considered its own area, since it has a dedicated conference, SoCC.


Describe in English the pattern in the following regular expressions Describe (in English phrases) the languages associated with the following regular expression. it says to be as simple as possible

#1 (x (yyy + x)*)*
#2 (c (cc)*d(dd)*)*

for number 1 I got all words in which when y is in the word it can only appear in blocks that are divisible by 3(0,3,6,9, etc.)

the second question I can not see any type of pattern.

I would like to know if the first one is correct, and if what pattern is on the second one?

Thanks

The first one is very close, but not quite right. Your phrasing technically allows strings that start with $yyy$, but the language contains no such string. There are lots of ways to fix what you have to incorporate this. For instance, you might try "all strings in which $y$s appear only in blocks of length divisible by $3$ preceded by at least one $x$." You'll want to check that to make sure it's right, of course.

The second one isn't too bad. Notice that a description of the regular expression inside the outermost parentheses might be "an odd number of $c$s followed by an odd number of $d$s." By applying the Kleene star, we allow this to be repeated an arbitrary number of times. Something like "All strings which, if non-empty, start with a $c$, end with a $d$ and alternate blocks of $c$s and $d$s of odd lengths," should be close.

Some general pointers:

Work from the inside out. Describe the subexpressions first, and use those descriptions to describe expressions.
If you're not seeing a pattern, it never hurts to write out some representative strings.
Pay special attention to boundary cases, especially around the empty string. Natural language tends to be a little unclear when it comes to things existing, satisfying properties vacuously, etc.