Can a dfa return only the final state? I am given an assignment to design a tiny arithmetic unit (from 0 to 15 inclusive)  start with 0 and using a DFA. The operations are as follow:

increment x+1 and if x+1 is larger than 15 then x+1 goes to 0
decrement x-1 and if x-1 is less than 0 then x-1 goes to 15
multiplication: 2*x and if 2*x is larger than 15 then we take 2*x - 16
division: we simply take the floor of (x/2)

My initial though of the solution was as follow:

1) number the states as follow q0,q1,q2,...,q15 where q0 is the initial state. So the state represent the result of the arithmetic operations

2) the transitions between the states represent the arithmetic operations.

However, soon after I remembered my teacher saying that the DFA return a string of transitions.

My question is can we make the DFA return the final state only (so in my case if it returns qN then the result is N) ?
if not how should I solve this problem?

I think there's a misconception.  DFA by themselves don't return anything.  A DFA is a mathematical model.  You can interpret the current state of the DFA when it hits an accept state as containing a result, but that's an interpretation you are making that's not part of the mathematical notion of a DFA.  Alternatively, you can consider a Moore machine or Mealy machine, which are mathematical models that do produce output; you can think of them as like a DFA but with an extension to allow them to produce output.


Variant of Turing machine How to prove that standard Turing machine is equivalent to a variant model where a string is accepted if the machine enters an accept state during computation? However, the machine may leave the accept state, and this action does not change the acceptance outcome.

In order to prove that your modified Turing machine is equivalent to a standard Turing machine, you need to do two things:

Given a standard Turing machine $T_1$, give a modified Turing machine $T_2$ such that $L(T_1) = L(T_2)$.
Given a modified Turing machine $T_3$, give a standard Turing machine $T_4$ such that $L(T_3) = L(T_4)$.

Good luck!


Subclass specification From http://web.mit.edu/6.031/www/fa19/classes/12-interfaces-enums/#implementing_generic_interfaces
"That means B is only a subtype of A if B’s specification is at least as strong as A’s specification. When we declare a class that implements an interface, the Java compiler enforces part of this requirement automatically: for example, it ensures that every method in A appears in B, with a compatible type signature. Class B cannot implement interface A without implementing all of the methods declared in A.
But the compiler cannot check that we haven’t weakened the specification in other ways: strengthening the precondition on some inputs to a method, weakening a postcondition, weakening a guarantee that the interface abstract type advertises to clients. If you declare a subtype in Java — implementing an interface is our current focus — then you must ensure that the subtype’s spec is at least as strong as the supertype’s."
However, later they define a generic class Set with method contains(E e) and a non-generic subclass CharSet with method contains(Character e). Does this count as strengthening pre-condition? If so, does it contradict the above?

CharSet is not a subtype of Set<E>, but it is a subtype of Set<Character>.  If you compare the signatures of the contains methods for Set<Character> and CharSet, you'll see that the preconditions are identical.
It might be helpful to imagine that Set is not a type and is not meaningful on its own; you have to instantiate the generic parameter to obtain a type.


How to compare algorithms in class NC time complexity with other classes? I know these relations :

\begin{gather}
\mathrm{NC}^1 \subseteq \mathrm{NC}^2 \subseteq \dots \subseteq \mathrm{NC}^i \subseteq \dots \subseteq \mathrm{NC} \\
\mathrm{NC}^i \subseteq \mathrm{AC}^i \subseteq \mathrm{NC}^{i+1} \\
\mathrm{NC}^1 \subseteq \mathrm{L} \subseteq \mathrm{NL} \subseteq \mathrm{AC}^1 \subseteq \mathrm{NC}^2 \subseteq \mathrm{P}
\end{gather}

But I don't know how to compare an algorithm with time complexity of $\mathrm{NC}^i$ to an algorithm with Polynomial complexity?

For example, Topological sort $\mathrm{NC}^2$ with BFS $\mathcal{O}(|V| + |E|)$

The class NC is by definition a subset of P, since it consists of uniform polynomial size circuits with some restrictions (namely, polylogarithmic depth). It is unknown whether $NC \neq P$, but this is strongly suspected.

Let me comment that $O(NC^2)$ is a syntax mismatch since $NC^2$ is a complexity class rather than a function. We simply say that topological sort is in $NC^2$.


Behavior of different multiplied and added time complexities Θ - Tightly bound

O - Upper bound

Ω - Lower bound

I understand that for addition, the max asymptotic value is taken, for example...

if ƒ1(n) = O(n) and ƒ2(n) = O(n log n), then ƒ1 + ƒ2 = O(max(ƒ1, ƒ2) = O(n log n)

and for multiplication, the multiplied asymptotic value is taken, for example...

if ƒ1(n) = O(n) and ƒ2(n) = O(n log n), then ƒ1 * ƒ2 = O(ƒ1 * ƒ2) = O((n^2)log n)

My question is, what happens to the formulas for adding and multiplying functions of different growth rates when other bounds besides upper bounds (such as Ω - Lower bound and Θ - Tightly bound) are used?

Let $f(n)\in \theta(h_1(n))$ and $g(n)\in \theta(h_2(n))$.

We start with multiplication:
It is easy to prove (from the basic definitions) that $f(n)\cdot g(n)\in \theta ((h_1\cdot h_2)(n))$, and similarly for $\Omega,o,\omega$.

Accordingly, multiplication of functions is preserved in all the asymptotic notations ($O,\Omega,\theta,o,\omega$)

As for addition, the idea is to make the following observation:
$$f(n)+g(n)=\max\{f(n),g(n)\}+\min\{f(n),g(n)\}$$
But $\min\{f(n),g(n)\}\le \max\{f(n),g(n)\}$, so $f(n)+g(n)\le 2\max\{f(n),g(n)\}$. Thus, we get
$$\max\{f(n),g(n)\}\le f(n)+g(n)\le 2\max\{f(n),g(n)\}$$

This implies that the asymptotic behavior of $f(n)+g(n)$ differs from that of $\max\{f(n),g(n)\}$ by a multiplicative constant, which means that they have the same order of magnitude, and in particular the relation is preserved under all the asymptotic notations.

To add some detail to the above, we use the observation that if e.g. $f(n)\in \Omega(h_1(n))$ and $g(n)\in \Omega(h_2(n))$, then $\max\{f(n),g(n)\}\in \Omega(\max\{h_1(n),h_2(n)\})$. This is relatively easy to prove.


Bounds on "well dispersed" sparse matrices Suppose we have an $n\times n$ zero/one matrix $M$, with $k$ ones. Let us say that the extent of $M$ is the maximum of $i+j$ over all ones at positions $(i,j)$ of the matrix, and the quality $q(M)$ is the minimum of the extent of $PMQ$ taken over all permutation matrices $P$ and $Q$. Let $f(n,k)$ be the maximum of $q(M)$ over all matrices $M$ with $k$ ones. What bounds can we give on $f(n,k)$?

Specifically, I am interested in finding whether there are any matrices $M$ with $k=O(n)$, such that $q(M)\ge (1+\epsilon)n$ for some $\epsilon>0$, i.e. $f(n,k)\ge (1+\epsilon)n$.

  Is it possible to achieve $f(n,k)\ge (1+\epsilon)n$ for $k=O(n)$?

Less formally, we have a grid that we can fill with a small number of dots, and the adversary is allowed to permute rows and columns in order to prevent the bottom corner from being filled. For example, I can have a matrix like

\begin{matrix}
\bullet&\cdot&\cdot&\cdot&\bullet\\
\cdot&\bullet&\cdot&\cdot&\bullet\\
\cdot&\cdot&\bullet&\cdot&\bullet\\
\cdot&\cdot&\cdot&\bullet&\bullet\\
\bullet&\bullet&\bullet&\bullet&\cdot\\
\end{matrix}

and the adversary can permute this to
\begin{matrix}
\cdot&\bullet&\bullet&\bullet&\bullet\\
\bullet&\cdot&\cdot&\cdot&\bullet\\
\bullet&\cdot&\cdot&\bullet&\cdot\\
\bullet&\cdot&\bullet&\cdot&\cdot\\
\bullet&\bullet&\cdot&\cdot&\cdot\\
\end{matrix}
so this matrix gets a quality of $6$. We want to distribute the dots so the quality is as large as possible.

Here are some observations:

$f(n,k)\le 2n$ trivially
$f(n,k)=2n$ only for $k=n^2$. This is because if $M$ has less than $n^2$ ones, then there is a spot containing a zero, which can be moved to the corner by a permutation.
$f(n,n)=n+1$. The identity matrix has $n$ ones, and all permutations of the identity matrix are permutation matrices. The best the adversary can do on a permutation matrix is put all the ones on the antidiagonal, which has $i+j=n+1$ for each of its ones.
$f(n,n+m^2-m)\ge n+m$: Similar to the above, where we use a $m\times m$ block of ones followed by ones on the diagonal. Permutations cannot break up the block, so the best option for the adversary is to put it on the antidiagonal, where it will extend out beyond the antidiagonal by $m$, like so:
\begin{matrix}
\cdot&\cdot&\cdot&\cdot&\bullet\\
\cdot&\cdot&\cdot&\bullet&\cdot\\
\bullet&\bullet&\bullet&\cdot&\cdot\\
\bullet&\bullet&\bullet&\cdot&\cdot\\
\bullet&\bullet&\bullet&\cdot&\cdot\\
\end{matrix}

The answer to the main question is yes, and the key to the construction is the notion of an expander graph.

  A (bipartite $d$-left-regular) expander graph between vertices $\mathcal{I}$ and $\mathcal{O}$ (the bipartition), where $|\mathcal{I}|=|\mathcal{O}|=n$, with expansion factor $c>0$, is a graph which is $d$-left-regular, meaning that each $x\in \mathcal{I}$ has degree $d$, such that for all subsets $A\subseteq I$ such that $|A|\le n/2$, the set $B\subseteq\mathcal{O}$ of neighbors of elements of $A$ has $|B|\ge (1+c)|A|$.

There are many proofs of existence of expander graphs like this by the probabilistic method and some deterministic methods as well; for the present purpose we only need that expander graphs as defined above exist for some constant $c>0$ independent of $n$.

Given such a graph, we can construct a $n\times n$ matrix from the adjacency matrix of the graph, with $\mathcal{I}$ for the rows and $\mathcal{O}$ for the columns. This matrix has exactly $k=dn=O(n)$ ones, because of the $d$ left regular property, and the expander property is unaffected by any permutations performed by the adversary.

Now for $\alpha>0$, let $A$ be the last $\alpha n$ elements of $\mathcal{I}$ and let $C$ be the last $\alpha n$ elements of $\mathcal{O}$, after the adversary has chosen an ordering of the rows and columns. If there is no one in this square in the matrix, then there must correspondingly be no edge between $A$ and $C$, and hence the neighbors $B$ of elements of $A$ must satisfy $B\subseteq C^c$, so by the expander graph property this implies
$$(1+c)|A|=(1+c)\alpha n\le |B|\le |C^c|=(1-\alpha)n\implies \alpha\le\frac{1}{2+c}.$$

Thus any empty bottom right square must be smaller than $n/(2+c)\times n/(2+c)$, so in the language of the OP, $$f(n,k)\ge 2n\left(1-\frac{1}{2+c}\right)=(1+\epsilon)n$$
where $\epsilon=\dfrac{c}{2+c}>0$.


Difference between RAM and buffer I have searched but didn't get any exact difference between RAM and a buffer. If both are used for temporary storage, then why they are named differently while both having same property?

A buffer is usually used only as temporary storage while something is being transmitted or read. For instance, you might be reading data from a slow-response external storage medium (e.g., a CD) and processing it continuously. In this setting, the first process reads chunks of data from the medium and writes it to the buffer on demand, while the latter reads from the buffer as if it were reading from storage directly. This avoids deadlocks in that the latter process does not need exclusive access to the medium.

In contrast, RAM is simply what is used as main memory for the processes in a general-purpose computer. There might be several buffers not only in RAM but also in other memory units. Saying that RAM is used for "temporary storage" can be rather misleading since "temporary" here actually means "until the process using it is inactive or extinct" (and not "until the data is not needed anymore").

In summary, a buffer is an abstracted concept (and only really exists at the software level); RAM is a concrete type of storage technology.


Which optimization algorithm would you recommend for this small multidimensional problem? Which algorithm would be suitable for finding or estimating the vector
$$\mathbf{s}_{opt}=\begin{bmatrix}
s_1 & \cdots  & s_N
\end{bmatrix}=\arg\max_{\mathbf{s}}\sum_{n=1}^{N}p_{s_n,n}$$
under the constraint
$$\sum_{n=1}^{N}l_{s_n,n}\leq L_{max}$$
given known values for the integer $N$, the vector
$\mathbf{p}_n=\begin{bmatrix}
p_{1,n}\\
\vdots \\
p_{M_n,n}
\end{bmatrix}$, the vector
$\mathbf{l}_n=\begin{bmatrix}
l_{1,n}\\
\vdots \\
l_{M_n,n}
\end{bmatrix}$, the integer $L_{max}$ and all integers $M_n$?

Here are some restrictions showing that the size of the problem isn't very big:
$$N\:\epsilon\:\mathbb{Z}\:|\:0<N<50$$
$$p\:\epsilon\:\mathbb{R}\:|\:0\leq p_{m,n}\leq 1\:|\:p_{1,n}=1\:|\:p_{M_n,n}=0$$
$$l\:\epsilon\:\mathbb{Z}\:|\:0\leq l_{m,n}\leq 30\:|\:l_{M_n,n}=0$$
$$M_n\:\epsilon\:\mathbb{Z}\:|\:2\leq M_n \leq 20$$

Another circumstance which may be of interest is that the problem will be solved repeatedly. In the first iteration $N=1$ and then for each iteration $N$ will increase as per the sequence $N=1,2,3,...$. The vectors $\mathbf{p}_n$ and $\mathbf{l}_n$, as well as the other inputs, will remain unchanged for all iterations $N=1,2,3,...$, meaning that the same problem just grows slightly step by step.

I am planning to implement this algorithm in JavaScript.

Edit: Real-world case

The mathematical optimization problem above has its origin in a real world (however, stupid) problem. Assume you need to communicate a text of $N$ words, but you have a limited total amount of characters to use, $L_{max}$. For each word $n$ you have found $M_n$ number of alternative representations (such as acronyms and synonyms) each with a probability of the reader to understand approximated to $p_{m,n}$. Now the goal is to choose which representation $s_n$ of each word should be chosen in order to maximize the probability of the receiver to understand the text. This probability can be approximated to the mean value all individual word probabilities.

This problem is effectively knapsack, where the size of the knapsack is $L_{max}$. The items are $1,\ldots,n$, and for each item $i$ we can select a quantity (to include in our knapsack) of $j\in\{2,\ldots,M_n\}$. Taking quantity $j$ of item $i$ gives reward $p_{j,i}$ and takes up $l_{j,i}$ space in the knapsack.

Let $D(n,r)$ be $max_s \sum_{i=1}^{n} p_{s_i,i}$ under the constraint that $\sum_{i=1}^{n} l_{j,i} \leq r$. $D(N,L_{max})$ (which is the value you're after) can be computed in $O(L_{max}\cdot NM)$ time (where $M$ is $max_i M_i$) using dynamic programming.

Effectively $D(n,r)$ represents the best way (mean probability) to represent the first $n$ words using at most $r$ space. The best way to represent $D(n,r)$ is to combine some choice of representing word $n$ with the best way to represent the remaining $n-1$ words in however many characters are left. This is expressed by the recurrence relation:

$$D(n,r)=max_{s_n\in\{2,\ldots,M_n\}} p_{s_n,n} + D(n-1,r-l_{s_n,n})$$

Where $D(*,r)=-\infty$ if $r<0$ and $D(0,*)=0$.

What is very important is that you store (and reuse) the intermediate values of $D(n,r)$ during the computation, as this will save significantly on computation time. Reusing these values will also allow you to deal with the growing input requirement, since the values encountered when computing $D(n,*)$ can be reused when computing $D(n+1,*)$.


The theoretical upper bounds for duplicate detection in a set of objects? I recently had a lengthy exchange with someone about the most efficient way to remove duplicates from a collection.  The debate was mostly centered around the specific behavior of C# collections, such as HashSet(T) and HashTable(T).

I think we agreed on the fundamentals, but where we couldn’t come to an agreement was what the constraints are with very large sets.

He told me to investigate the theoretical (ie absolute) bounds for duplicate detection in a set of objects… But I don’t really know what that means.  I don’t think there’s an absolute bounds if you can break up the problem sufficiently.

There may be a point at which you can no longer use a HashSet / HashTable in .NET because I know that if you are using the framework au-naturale you are constrained by the number of unique values an Int32 can express and the amount of memory you have available.

But the issue of storage and memory issue comes much sooner than the number of unique values, which is typically what the theoretical is concerned with... For example if the data type is integers for the initial set you're removing duplicates from, you run out of memory before the numeric range of the integer type becomes a problem:

If I am storing integers, I know that there are 2^32 possible integer values.
To store an integer, I need 32 bits of space, so the total memory required to store all distinct integers is 2^32*4 bytes, which is 17.18 gigabytes.
The amount of memory that can be addressed in a 32 bit architecture is 2^32 bytes or approximately 4.295 gigabytes

Even if I’m not using a hashset, I can see that in order to store that many values, I would need at least four times the amount of memory addressable by the architecture for the initial collection.  And that's not even factoring in the duplicates we're seeking to remove.

I would also need memory proportional to the size of the initial set for the hash set implementation and hash set value storage… So the use of a hashset quickly becomes unfeasible when you exceed millions of unique values.

I’ve already asserted to him that if you had a large digit such as a long, and you had billions of values, you would not use a hashset.  Hypothetically I might store the data in distributed nodes that are pre-sorted by the unique field, or implement a distributed mapreduce sort implementation, followed by a mapreduce duplicate value removal algorithm.

He didn’t acknowledge the feasibility of the sort/remove duplicates approach though… And was quite insistent that there is an upper bound for duplicate detection.

Could anyone tell me what the ‘absolute’ bounds for duplicate detection for a set of objects is?  Or what he was was referring to by it?

I think you're asking about the "Element Distinctness Problem."

Assuming you're talking about time complexity (number of comparison operations) rather than space complexity, "lower bound" instead of "upper bound," and that you can't hash elements of your multiset (which gives you $O(n)$ expected time), then the best you can do is $\Theta(n \log n)$.


Why is n log n dominated by n log^2 n? Does the rule of $n ^ a$ dominate $n ^ b$ if $a > b$ apply here as well?

My understanding is that $n \log n$ will be dominated by $n \log ^2 n$ because of $\log$ being raised to the power of $2$.

little-oh proof

An equivalent but more straightforward question would be why $\lg n$ is dominated by $\lg^2 n$, that is why $\lg n \in o(\lg^2 n)$.

Then based on the definition of little-oh we need to show that for any choice of constant $ c > 0 $, we can find a constant $ n_0 $ such that the inequality $ \lg n < c \lg^2n $ holds for all $ n > n_0 $.

We prove that if we pick $ n_0 = \sqrt[c]{b} $ where $ b $ is the base of $ \lg $, then the definition above holds.

If $ n_0 = \sqrt[c]{b} $ then we have $ n > \sqrt[c]{b} $ or $ n > b^{\frac{1}{c}} $.  Now since $\lg n$ with a base $ b > 1 $ is an increasing function, then $ \lg n > \lg b^\frac{1}{c} $ or $ \lg n > \frac{1}{c} $.  If we multiply both sides by $ c > 0 $, we have $ c \lg n > 1 $.  Now we can multiply both sides by $ \lg n > 0$ (Note that for $ \lg n > 0 $ to be true, we must have $ n_0 \geqslant 1 $ which leads to $ \sqrt[c]{b} \geqslant 1 $ or $ b^\frac{1}{c} \geqslant 1$ which results in $ \lg b^{\frac{1}{c}} \geqslant \lg 1 $ or $ \frac{1}{c} \geqslant 0 $ or $ c > 0 $; which is already guaranteed.) to have
$$
 c \lg^2 n > \lg n .
$$
This is what we needed to show.

Big-Oh proof sketch

A slightly different but related question could be why $\lg n$ is bounded above by $\lg^2 n$, that is why $\lg n \in O(\lg^2 n)$.

The answer is that since $\lg n > 1$ for $n$ larger than the base of $\lg$, then if we raise $\lg n$ to any power greater than $1$ (including power of $2$), it will be larger than $\lg n$ itself.

(We could rather argue that since we proved that $ \lg n \in o( \lg^2 n) $, it follows from $ o(f) \subset O(f) $ that $ \lg n \in O( \lg^2 n) $.)

Note

So yes, the rule of $n^a > n^b$ if $a > b $ and $ n > 1 $ does apply here.  Note that this rule is equivalent to the statement that any exponential function with a base greater than $1$ is an increasing function.


Hypothetical Situation for sorting in $O(n)$ using median finding machine that works in $O(\sqrt{n})$ In a hypothetical world, we have a machine that can find median of $n$
  numbers in $O(\sqrt{n})$. (Of course this machine is not real).

  Can we use this machine to sort an array in $O(n)$?

I don't know how can I approach these type of questions which have a wrong statement as given. I know if the machine also partitions the array when finding the median, we can sort the array in $O(n)$ using $T(n) = 2T(n/2) + O(\sqrt{n})$.

But the question didn't say anything about partitioning. So if we assume that it doesn't change the array in any way and just finds the median, Can we use this machine to sort the array in $O(n)$ or not?

We don't have to merge two sorted arrays, if we can simply compute the median information and store it in an auxilliary array; by definition, a median of an array $A[l...r]$ is the element in $A[(l+r)/2]$ when $A$ is in sorted order. Given this definition, we can simply use mergesort-style divide and conquer, while keeping track of another array $A'$ with medians of subarrays of $A$; in the end, $A'$ will be the sorted version of $A$:
Procedure Median-Merge-Sort($A,l,r,A'$) {

If $r-l<2$ then manually update $A'[l...r]$ and return; $\leftarrow$ Basecase.
Let $m:=$Median($A,l,r$); $\leftarrow$ Compute a median in $O(\sqrt{n})$-time using the oracle.
Let $A'[(l+r)/2]:=m$;
Median-Merge-Sort($A,l,(l+r)/2,A'$);
Median-Merge-Sort($A,(l+r)/2+1,r,A'$);

}
The overall running time is $T(n)=2T(n/2)+O(\sqrt{n})$, which solves to $O(n)$ using master's theorem. This also tells us we cannot have a median-finder working in $O(\sqrt{n})$ on the comparison model, otherwise we can sort in linear time, which violates the sorting lower bound on the comparison model.


Algorithm for creating a directed graph using flat data input Given flat data like this:

01001, Butter, salted
01002, Butter, whipped, with salt
01145, Butter, without salt
04601, Butter, light, stick, with salt
04602, Butter, light, stick, without salt

What's the best approach to convert into this:

Butter (01001, 01002, 01145, 04601, 04602) -> salted (01001)
                     -> whipped (01002) -> with salt (01002)
                     -> without salt (01145)
                     -> light (04601, 04602) -> stick  (04601, 04602) -> with salt (04601)
                                                                      -> without salt (04602)

I was thinking of recursive sorting first, but I realized there may be a lot of string comparisons to be efficient.

It looks like you're making a tree based on elements after the first. Some quick pseudocode for this might look like:

 1. Start with a tree containing only the root.
 2. Set the current node to the root.
 3. Read a line of input = (ID, tail)
 4. For each object in tail, do
 5.     if the current node has a child equal to the current object, then
 6.         move to that child node
 7.         add the current ID to the list of IDs associated with that node
 8.     else,
 9.         add a new child node corresponding to the current object
10.         start a list of associated IDs using the current ID as the first entry
11. Repeat from step 2. until there is no more input

Showing this on your example:

Initial:
Root

Pass 1: (ID, tail) = (01001, (Butter, salted))
Root
- Butter (01001)
  - salted (01001)

Pass 2: (ID, tail) = (01002, (Butter, whipped, with salt))
Root
- Butter (01001, 01002)
  - salted (01001)
  - whipped (01002)
    - with salt (01002)

Pass 3: (ID, tail) = (01145, (Butter, without salt))
Root
- Butter (01001, 01002, 01145)
  - salted (01001)
  - whipped (01002)
    - with salt (01002)
  - without salt (01145)

...

Basically, you're constructing a tree, one branch at a time.


Who was the first to define Flow Shop / Job Shop problem? I spent some time to search in internet who was the first to formaly define Flow Shop and Job Shop problems but with no effect. I'm especially interested in article/book so I can mention it in my master thesis.

I'm guessing that there may be no author of this problems but this information also would help me a lot.

Coffman and Demming's famous Operating Systems Theory, 1973, section on Job Shop and Flow Shop problems (pp. 123-128) cites Conway, Maxwell, and Miller, 1967 as "a comprehensive treatment" of Job Shop scheduling.  In the next paragraph, they introduce Flow Shop scheduling as a specialization of Job Shop, and cite

Johnson, S.M.; "Optimal two- and three-stage production schedules with set-up times included."  Naval Research Logistics Quarterly, 1(1):61-68, 1954.

Naval Research Logistics Quarterly seems to be a Wiley pay-walled journal, but my library has a subscription to it.  Johnson's paper begins:

Let us consider a typical multistage problem formulated in the following terms by R. Bellman:
"There are n items which must go through one production stage or machine and then a second one.  There is only one machine for each stage.  At most one item can be on a machine at a given time.
"Consider $2n$ constants $A_i, B_i, i = 1, 2, \cdots, n$.  These are positive but otherwise arbitrary.  Let $A_i$ be the setup time plus work time of the $i$th item on the first machine, and $B_i$ the corresponding time on the second machine.  We seek the optimal schedule of items in order to minimize the total elapsed time."

He doesn't give the full reference to Bellman. Johnson's paper extends the definition in the obvious way to 3 machines.


Algorithm for real time Coordinate smoothing So I get new Coordinates every 10ms even with RTK fixed precision, they jump between 1-3cm. The Coordinates are the current Position of my Vehicle

I have a Vehicle using these Coordinates to follow a drawn Path.

Now as the Coordinates Jump, the Vehicle tries to follow them and is driving in curves instead of a straight line sometimes more sometimes less depending on how sensitive the steering is.

My question now is, what Algorithm is capable of "smoothing" incoming Coordinates in real-time to avoid the jumping around?

Kalman-Filter / Douglas-Peucker or something else?

Does a prediction of the next current position help? -- Maybe with the help of an IMU?

A Kalman filter is a reasonable choice for this.  It is useful for tracking the movement of an object, as it can be used with a model for the physics of the movement of an object.


Elements of Programming Interviews - 16.4 Generate Power Set - solution 1 time complexity question hope you all are doing well.

I have a question about the time complexity of solution 1 for question 16.4 - Generate Power Set from the book Elements of Programming Interviews by Adnan and Tsung-Hsien.

The question instructs the reader to "Write a function that takes as input a set and returns its power set". The input is the set S = {0,1,2}.

I understand that there are at most 2^n recursive calls of the method directedSoFar. However, I don’t understand why we spend O(n) time within a call of directedSoFar. There are no loops inside the method, only 2 lines at the recursive case to add and remove elements into the current selectedSoFar solution, and another 2 lines at the base case. Doesn't this mean that we only spend constant time within a call, and not O(n) time?

I’ve struggled with this for a while, and have posted on the official forum as well as Reddit, but got no responses. I would appreciate it if anyone would be generous enough to help me.

Thank you

Note the following line of code:

powerSet.add(new ArrayList<>(SelectedSoFar);

Whenever we create a subset, we add the subset (list) to a list of list : power set. The size of subset will be $n$ (actually it will vary from $1$ to $n$, but we can take it to be $n$).

Even though adding a list requires one line of code, but it will involve copying all the elements. This is why it will take O(n) time.


What will happen if input is larger than required in a NFA This is my first time in the field of TOC so I am not able to provide any self-approach while asking .In the above example what will happen if input string is "1001" or "1111"?The state q4 can be reached with the first 3 inputs only ,so what will happen after that ?

An NFA accepts a string $w$ if it has an accepting computation. An accepting computation is an expression of the form
$$
q_0 \stackrel{x_1}{\to} q_1 \stackrel{x_2}{\to} q_2 \to \cdots \to \stackrel{x_m}{\to} q_m
$$
where:

Each $x_i$ is either a single letter or $\epsilon$.
$x_1 x_2 \ldots x_m = w$.
For every $1 \leq i \leq m$, $q_i \in \delta(q_{i-1}, x_i)$.
$q_0$ is the initial state, and $q_m$ is an accepting state.

If there are no accepting computations for $w$, then the NFA doesn't accept $w$.

The string $1001$ has no accepting computation. In contrast, the string $1111$ does have an accepting computation:
$$
q_1 \stackrel1\to q_1 \stackrel1\to q_2 \stackrel1\to q_3 \stackrel1\to q_4
$$
Therefore the NFA does accept $1111$.

Another way to define the language accepted by an NFA is through the possible states function. We define $\delta(q,x)$ to be the set of possible states that the NFA is in when it reads the word $x$. You can define $\delta(q,x)$ inductively. The NFA accepts $x$ if $\delta(q_0,x)$ contains an accepting state, where $q_0$ is the initial state. For example, in the case of $1001$,

$\delta(q_1, \epsilon) = \{ q_1 \}$.
$\delta(q_1, 1) = \{ q_1, q_2 \}$.
$\delta(q_1, 10) = \{ q_1, q_3 \}$.
$\delta(q_1, 100) = \{ q_1, q_4 \}$.
$\delta(q_1, 1001) = \{ q_1, q_2 \}$.

Since neither $q_1$ nor $q_2$ are accepting states, the NFA doesn't accept $1001$. In contrast, for the word $1111$ we have:

$\delta(q_1, \epsilon) = \{ q_1 \}$.
$\delta(q_1, 1) = \{ q_1, q_2 \}$.
$\delta(q_1, 11) = \{ q_1, q_2, q_3 \}$.
$\delta(q_1, 111) = \{ q_1, q_2, q_3, q_4 \}$.
$\delta(q_1, 1111) = \{ q_1, q_2, q_3, q_4 \}$.

Since $q_4$ is an accepting state, the NFA accepts $1111$.


Confusion about finite automata construction in Knuth–Morris–Pratt algorithm There is one point I don't understand in the DFA construction for mismatch cases.

Here is the lecture note I watched, which describes how to handle mismatched characters during the DFA construction process.

Some information about the presentation screen shot:

pat is the pattern, string index starts at 0, dfa is the state transition table, in which the row is indexed by the character(eg, "A","B" or "C"), column by state(1,2,3,...).

My question starts:

In the place in the presentation, where starts with "To compute dfa[c][j]", it says run the simulation using the last j-1 chars.

I am confused:

Why run the simulation using the last j-1 chars, rather the last j chars.

What's the intuition of this design?

Say we are at state j (in the question's example, j is 5). This means that so far we have successfully matched j characters (characters 0 to j-1 of the pattern). Now, we receive a new character - call it newChar.

Case 1: newChar is the character we wanted ('C' in the example). All is good and we have now a match of j+1 characters (characters 0 to j of the pattern).

Case 2: newChar is not the character we wanted. Let's assume the most optimistic situation: that we've now matched j characters of our pattern. (We couldn't have a match of j+1 characters in this case, because otherwise we would be in Case 1.) The last of these j characters that we matched is newChar. To have a total of j characters matched, then, we must have matched characters 1 to j-1 of the pattern plus newChar.

Because a mismatch puts us in Case 2, and Case 2 only uses characters 1 to j-1, we need only run the simulation using the last j-1 characters.


Path uniqueness in undirected graph Let's consider an undirected graph with two special vertices: start and finish. The graph is relatively sparse. The edge count is expected to be three times or four times higher than the vertex count.

I am looking for an algorithm that decides whether there exists some path between start and finish and if it is unique. The output of the algorithm is one of the three possible answers:

There is no path between start and finish.
There is exactly one path between start and finish.
There are two or more paths between start and finish. The two paths need not be disjoint. They just must not be identical.

Currently, I have the following algorithm implemented:
I run breadth-first search from start vertex to find the shortest path from start to finish. If the finish vertex is unreachable, I am done. If I find a path, I iterate over its vertices except start and finish. I remove the vertex and run BFS from start vertex again. If the finish vertex can be reached, I am done as I have found another path from start to finish. If the finish vertex is unreachable, I undo the vertex removal and continue with another vertex. If the finish vertex is always unreachable during this loop, the initial path is unique.

I wonder if there is some more efficient algorithm than running BFS for each vertex of the initial path.

EDIT:
As mentioned in the comment, I am interested only in simple paths, i.e. paths without repeating vertices.

I am assuming that you are interested in simple paths only. Otherwise the answer is trivial.

You can solve your problem in time $O(n)$. Let $s$ be your start vertex and $t$ be your target vertex.
Consider the graph as weighted where every edge has weight $0$.

Find any path $P$ from $s$ to $t$ in $G$. This takes time $O(n)$.
If $P$ does not exist then there is no path from $s$ to $t$.
Otherwise set the weight of each edge in $P$ to $1$ and find a shortest path $P'$ in the modified graph. This takes time $O(n)$ using a straightforward modification of Dijkstra's algorithm.

If $P' = P$ then there is a single path from $s$ to $t$ in $G$.
Otherwise there are at least two distinct paths from $s$ to $t$ in $G$.


Compute hash value according to multiplication method In "Introduction to Algorithms" by C. E. Leiserson, R. L. Rivest and C. Stein (ISBN:  978-0262033848), p. 264 they state this:

I get everything but the last part stating $h(k) = 67$

>>> r = 17612864
>>> bin(r) # r's binary representation
'0b1000011001100000001000000'
>>> int(bin(r)[: 14 + 2], 2) # extract 14 most significant bits and convert to int
8600

You haven't extracted the 14 most significant bits. First, you have to write $r$ as a $w$-bit number:
$$
00000001000011001100000001000000
$$
Now you extract the 14 most significant bits:
$$
00000001000011
$$
Converting to decimal, this is 67.


Determining Ambiguity of grammar I read that no LL(1) grammar can be ambiguous.

Can we just make a LL(1) predictive parser table for a grammar to determine whether it's ambiguous? If the grammar is not LL(1), can we say that grammar is ambiguous?

If the grammar is not LL(1), can we say that grammar is ambiguous?

Euh, no. A grammar is unambiguous if for every word in its language there exists exactly one derivation-tree for it in the grammar.

Parsing is a way to find that derivation, given the string, preferably in some efficient way. Several classes of grammars were defined that have efficient parsing methods, for example LL(1) grammars.

A grammar can be non-LL(1), and still be unambiguous. For instance when we reverse an LL(1) grammar (that is, take the mirror image of the RHS of every production) the result still is unambiguous: mirroring the original unique derivation trees. But it cannot be parsed in an LL fashion, rather its reverse...


Mcculloch and Pitts Neurons: Is there errata in this article? The paper A LOGICAL CALCULUS OF THE IDEAS IMMANENT IN NERVOUS ACTIVITY has the following description of neurons, which I question if there is errata or perhaps I need more information to understand this.

Looking at the picture below (b) is described as an OR gate.  I'm confused because with either threshold being met on the $N_1$ or $N_2$ neuron, with thresholds 1 and 2, there are not enough inputs to reach the threshold of 3 for $N_3$.  So how is this an OR gate?

(c) makes sense because the sum of the input to $N_3$ is 3 when both $N_1$ and $N_2$ are at their thresholds.

Any guidance appreciated.

In the article mentioned, the figures each have a threshold of 2 for each neuron.  Therefore there is no errata.


Why does this NFA having an empty symbol I'm trying to understand the difference of DFA from NFA
I have this example in my coursebook

Are the empty symbols at the start necessary?
or can we do away with them to have something like this

Yes, in this example, your solution is fine.

Perhaps the example just wanted to show the use of epsilon transitions. Also, your approach would be more complicated in the case where one of the original initial states would have a loop. We cannot transfer that loop to the common initial state.


Divide $n$ gifts among three people so as to minimize the difference in the total cost of gifts between the most lucky and the most unlucky people Divide $n$ gifts of different values among three people so as to minimize the difference in the total cost of the gifts for the most lucky and the most unlucky persons.

The total value of $n$ gifts is $W$. The most fair division will be to give all of them gifts of the total value $W/3$.

Suppose $W_1, W_2, W_3$ are the total values of the gifts of the first, second and third person.

We want to minimize: $\max(W_1, W_2, W_3) - \min(W_1, W_2, W_3)$.

Using the knapsack problem. Assign to the first knapsack the "weight" $W/3$ and the same for the second knapsack $W/3$. Use double knapsack algorithm and get the for each knapsack the gifts that maximizes the total value but obeys the $W_{i \in {1,2}} \le W/3$ property. Then the remaining gifts give to the third person.

The question is if such kind of algorithm is correct? If so why? If no can you provide your own solution to the problem?

Say your best answer so far has a difference D, and you can give w/3 - a to the first person. The best result you can have is w/3 + a/2 to the other two, giving a difference of 3a/2, so you only proceed if 3a < 2D (actually, you will distinguish cases depending on w modulo 3 if all sizes are integers).

Then you pick items for the second person. If you can give them w/3 - b, b ≥ a, then diff = a + 2b, so you need a + 2b < D, or b < (D - a) / 2; only if a ≤ D/3. If you can give them w/3 - b, 0 ≤ b ≤ a, then diff = 2a + b, so you need b ≤ D - 2a, only if a ≤ D/2. You analyse the case w/3 + b for the second person as well, so you find a range for how much goes to the second person.

Problem is that you waste a lot of time with sets for the first person that are not particularly close to w/3. Based on the number of items and their values I'd make an estimate how good the best solution would be (how much the smallest D will be) and only look for items for the first person that might give a result < 2D, then extending to 4D, 8D etc. if nothing is found.

And you should check the case where one item is > w/3 first, or you might waste a lot of time.


Does n^(1-1/d) always dominate log^d(n) Hi I am currently learning about orthogonal range search and found two data structures with two different runtimes and wanted to proof that one always dominates the other.
So I found out about k-d-trees with a query time of
$$\mathcal{O}(n^{1-\frac{1}{d}})$$
and range trees with a query time of
$$\mathcal{O}(\log^{d-1}n)$$
and would like to show that
$$\mathcal{O}(\log^{d-1}n) << \mathcal{O}(n^{1-\frac{1}{d}}) \quad \forall d \in \mathbf{N}$$
I tried around on Wolfram Alpha and the solutions were of the form
$$ n > \exp\left(-d \cdot W_{-1}\left(\frac{-1}{d}\right)\right) $$
where $W_k(z)$ is the analytical continuation of the product log function. But I wasn't able to proof this always holds. Thank you in adnvance :)

L'Hôpital's rule shows that for $\epsilon > 0$,
$$
\lim_{n\to\infty} \frac{\log n}{n^\epsilon} =
\lim_{n\to\infty} \frac{\frac{1}{n}}{\epsilon n^{\epsilon-1}} =
\lim_{n\to\infty} \frac{1}{\epsilon n^\epsilon} = 0.
$$
In other words, $\log n = o(n^\epsilon)$ for all $\epsilon > 0$.
This immediately implies that $\log^C n = o(n^\delta)$ for all $C,\delta > 0$, taking $\epsilon = \delta/C$.


How to understand the probablistic analysis of skiplist? I've been studying the skiplist analysis from the open data structures book here:
Open Data Structures
I've understood the first 3 lemma's, (after looking at how they use indicator variables in the section 1.3.4 of the book).
However, Lemma 4.4 seems pretty vague. Especially, how is
$$\sum_{r=1}^{\lfloor\log n\rfloor}1 + \sum_{r=\lfloor\log n\rfloor+1}^\infty n/2^r\leq\log n + \sum_{r=0}^\infty 1/2^r\,?$$

The first sum is obviously equal to $\lfloor\log n\rfloor\leq\log n$.

For the second sum, assuming that logs are base-$2$ and using $r>\lfloor\log n\rfloor$,

$$2^r = 2^{\lfloor\log n\rfloor+1}2^{r-\lfloor\log n\rfloor-1} \geq n2^{r-\lfloor\log n\rfloor-1}\,,$$

and the result follows.  If the logs aren't base-$2$, then there'll be a scaling factor but the second sum will still be $\Theta(1)$.


Polynomials - using Newton's method, or not? I have to find a root of polynomial of degree $n\ge2$. I need to write code to calculate the root for different values of $n$. Only 1 real positive solution is needed.

I can use general Newton's method for all degrees, or only for 5th+, and for 2,3 and 4 I can use algebraic formulas that solve quadratic, cubic and quartic equations. Since algebraic formulas need to use sqrt, acos and similar functions - does it make sense at all to use algebraic formulas - or is it better to use Newton's method for all degrees? I guess the latter will actually be faster?

This is my equation:

$$\frac{1}{(b_1x + 1)} + \frac{1}{(b_2x + 1)} + ... + \frac{1}{(b_nx + 1)} -k = 0$$

and constraints:

$$1 \leq k<n \\ b_n>0 $$

e.g. for $n=3$:

$$b_1 b_2 b_3 (-k)x^3 +\left(b_1 b_2+b_3 b_2+b_1 b_3- b_1 b_2 k-b_3 b_2 k-b_1 b_3 k\right)x^2 + \left(2 b_1+2 b_2+2
   b_3-b_1 k-b_2 k-b_3 k\right)x + 3-k =0$$

which can be written as

$$\sum_{i=0}^n(n-i-k)\binom{\{b_1,...,b_n\}}{i}x^i=0.$$

The sum goes to infinity at x = -1 / $b_i$. Between $b_i$ and $b_{I+1}$ it is continuous. So each of these intervals contains a point wher the sum of fractions equals k. Go from there.


Prove: Every decidable set is Turing reducible to the empty set Question-
Prove:  Every decidable set is Turing reducible to the empty set.

Can anyone help me with this please?

All reductions tutorials I've seen use practical examples of reduction such as sipser's introduction to computation theory:

"A reduction is a way of converting one problem to another problem in such a
way that a solution to the second problem can be used to solve the first problem.
...
For example, suppose that you want to find your way around a new city. You
know that doing so would be easy if you had a map. Thus, you can reduce the
problem of finding your way around the city to the problem of obtaining a map
of the city"

I don't see how to use this kind of information as a general proof, or how the empty set is even usable to solve anything else in a practical example even.

You're trying to prove something, so you need to use something closer to an actual definition of Turing reducibility. The statement you quote from Sipser is an intuition about what reductions do, but it's not precise enough to let you solve problems.

Here's an informal definition of Turing reducibility that lets you start to reason about what it can do.

  A set $A$ is Turing-reducible to a set $B$ if, assuming the existence of a subroutine that determines whether its input is in $B$, we can write a program that determines whether its input is in $A$.

We're considering $B=\emptyset$, so we need to assume the existence of a subroutine that determines whether its input is in $\emptyset$. Well, that's not much to assume. Here's the subroutine:

 return false

OK – we don't need to assume anything: we know this subroutine exists.  So now, we just need to show that every decidable set is Turing reducible to $\emptyset$. That is, we need to show that

  For every decidable set $A$, we can write a program that determines whether its input is in $A$.

So... what's the definition of decidable?


What algorithm do computers use to compute the square root of a number? What algorithm do computers use to compute the square root of a number ?
EDIT
It seems there is a similar question here:
Finding square root without division and initial guess
But I like the answers provided here more.
Plus the person asking the similar question had the question formed in a personal way.
My question has an easier to find wording.
The similar one was asked having an insight about the inner mechanics of such an algorithm and was being asked like if it was something that had not yet been solved-found.
I don't know if there is a way for a moderator to merge the two posts.

Have a look at the paper
https://www.lirmm.fr/arith18/papers/burgessn-divider.pdf
which describes the division / square root hardware implementation in some ARM processors.
Roughly the idea: For a division unit, you can look up the initial bits of divisor and dividend in a table to get two bits of result. For double precision with a 53 bit mantissa, you repeat that 26 or 27 times and you have the result. For single precision with 24 bit mantissa, you need to repeat only 12 or 13 times. All the other bits, calculating the exponent etc., can be done in parallel.
Now what does square root have to do with division? Simple: sqrt (x) = x / sqrt (x). You get the square root by dividing x by its square root. Now when you start this division, you don't know the square root yet. But as soon as you have say eight bits and you are very, very careful, you can produce two mantissa bits per cycle. And getting the first say eight bits is not hard, since unlike a division x / y, there is only one operand involved.
The paper describes this in much more detail, and importantly describes why this is superior for example to using Newton-Raphson or similar. Note: It is superior for typical floating-point numbers with 24 or 53 bit mantissa. Since that is what is used 99.9999% of the time it is important, but for different situations things are different.


Collection of meta-reductions in theory of $\mathrm{NP}$-completeness I want to start a wiki post about meta-result of meta-reductions in the theory of $\mathrm{NP}$-completeness.

This can be regarded as a reference request post. Any links are appreciated.

At least, this can be helpful in drastically mitigating the frequently asked questions related to homework assignments that are giving so much credit to @David Richerby, @D.W., @Yuval Filmus.

NODE- & EDGE- DELETION

Here, I start with some links on meta-result on the hardness of node- and edge- deletion to satisfy $\pi$ property for various classes of property $\pi$.

https://dl.acm.org/citation.cfm?id=804355
https://www.cs.umd.edu/~gasarch/TOPICS/ramsey/hered.pdf
https://www.sciencedirect.com/science/article/pii/0166218X83901014


Confusion About Min-Cut Probabilities Currently going through a video on Counting Minimum Cuts by Tim Roughgarden.
$(A_{i},B_{i}) = \big((A_{1},B_{1}), ..., (A_{t},B_{t})\big) \forall i \in \Bbb{R}$
$P\big((A_{i},B_{i})\big) \geq \frac{1}{\begin{pmatrix} n \\ 2 \end{pmatrix}} = p$, which I interpret as the lower bound on the probability of having at least one minimal cut.
In the problem set that follows two answers A and B are highlighted as being correct. I understand why A is correct; but am puzzled why B is also marked as correct.
A: For every graph $G$ with $n$ nodes and every min cut $(A,B)$ (I am assuming same thing as $(A_{i},B_{i})$) $P\big((A,B)\big) \geq p$.
B There exists a graph $G$ with $n$ nodes and a min cut $(A,B)$ (again assuming same thing as $(A_{i},B_{i})$) of $G$ such that $P\big((A,B)\big) \leq p$.

I don't understand what you mean by "$(A_i,B_i) = ((A_1,B_1),\ldots,(A_t,B_t))$", an obviously false statement. Perhaps you meant $(A_i,B_i) \in \{(A_1,B_1),\ldots,(A_t,B_t)\}$?

I don't quite understand your interpretation of the statement $P((A_i,B_i)) \geq p := 1/\binom{n}{2}$. Here is the correct interpretation:

  For any minimum cut $C$, the probability that Karger's algorithm outputs $C$ is at least $p := 1/\binom{n}{2}$.

This is exactly what A states.

For B, you need to give an example of a graph which satisfies $P(C) \leq 1/\binom{n}{2}$ for all cuts $C$. One such example is a cycle, an example you were probably shown in class.


How to prove that matrix inversion is at least as hard as matrix multiplication? Suppose we are given a matrix $A$ over real numbers and we want to computer the inverse of matrix $A$. There are various algorithms to do so and it also turn out that we can use matrix multiplication problem to solve matrix inversion problem.

My question:  How to prove that matrix inversion is at least as hard as matrix multiplication?

If you want to multiply two matrices $A$ and $B$ then observe that
$$\begin{pmatrix}I_n&A&\\&I_n&B\\&&I_n\end{pmatrix}^{-1}=
\begin{pmatrix}I_n&-A&AB\\&I_n&-B\\&&I_n\end{pmatrix}$$
which gives you $AB$ in the top-right block.
It follows that inversion is at least hard as multiplication.
EDIT: I had misread the question, the original answer below shows that multiplication is at least as hard as inversion.
Based on the wikipedia article: write block inverse of the matrix as
$$\displaystyle {\begin{bmatrix}A & B \\C &D \end{bmatrix}}^{-1}={\begin{bmatrix}A^{-1}+A^{-1}B(D -CA^{-1}B)^{-1}CA^{-1}&-A^{-1}B(D -CA^{-1}B )^{-1}\\-(D-CA^{-1}B)^{-1}CA^{-1}&(D-CA^{-1}B)^{-1}\end{bmatrix}}.$$
Note that $A$ is invertible because it is a submatrix of the original matrix (which is invertible). One can prove that $D-CA^{-1}B$ is invertible because of the following identity ($M$ is the original matrix):
$$\det(M)=\det(B)\det(D-CA^{-1}B).$$
Some clever rewriting using Woodbury identity gives
$$\displaystyle {\begin{bmatrix}A & B \\C &D \end{bmatrix}}^{-1}={\begin{bmatrix}X&-XBD^{-1}\\-D^{-1}CX&D^{-1}+D^{-1}CXBD^{-1}\end{bmatrix}}$$
where
$$X=(A-BD^{-1}C)^{-1}.$$
Let $C(n)$ denote the complexity of matrix inversion for a $n\times n$ matrix. Let $\omega$ be the exponent of the best matrix multiplication algorithm, so that we can multiply two $n\times n$ matrices in time $O(n^\omega)$. Using the formula above, we can express the inverse of an $n\times n$ matrix using:

two inverses of half-size ($\frac{n}{2}\times\frac{n}{2}$): $D$ and $X$
six multiplications of half-size: $BD^{-1}$, $(BD^{-1})C$, $X(BD^{-1})$, $D^{-1}C$ and $(D^{-1}C)(XBD^{-1})$
two additions of half-size

This gives the recurrence
$$C(n)=2C(n/2)+6O((\tfrac{n}{2})^\omega)+2O((\tfrac{n}{2})^2).$$
Since $\omega\geqslant 2$, we rewrite the above as
$$C(n)=2C(n/2)+O(n^\omega).$$
We can now apply the Master theorem. Using the notation of the wikipedia article, we have $f(n)=Kn^\omega$ for some constant $K$, $a=b=2$ thus $c_{crit}=\log_22=1<\omega$. On the other we have a regularity condition on $f$ since
$$af(n/b)=2K(\frac{n}{2})^\omega=2{1-\omega}Kn^\omega\leqslant \frac{1}{2}f(n)$$ because $\omega\geqslant 2$. Thus the theorem tells us that
$$C(n)=O(f(n))=O(n^\omega).$$
It follows from that multiplication is at least as hard as inversion.


Algorithmic information theory with stochastic algorithms? Suppose we define a class of algorithms that is allowed to sample i.i.d. Bernoulli bitstrings of arbitrary length, and use these to generate outputs. If we are allowed to use algorithms like this, then intuitively, "white noise" images like this one are easy to generate (i.e they have a low description length algorithm allowing random noise, even though it is essentially maximum k-complexity), namely we just run a for loop width x height times and pick black/white randomly.
I've tried to look online for "stochastic algorithmic complexity" and some other keywords, but haven't found anything relevant. Is there a term that I can search for to read about this idea, of defining an algorithmic complexity measure of objects/classes of objects using algorithms that are allowed to use randomness?

One possible direction is looking at the (computational) hardness of distributions. For example, a family of distributions $\{\mathcal{P}_n\}_{n\in\mathbb{N}}$ where $\mathcal{P}_n$ is a distribution over $\{0,1\}^n$ is called polynomialy-samplable (you can substitute here any other type of time/space restriction) if there exists a probabilistic polynomial time algorithm $A$ such that $A(1^n)\sim \mathcal{P}_n$. Your white noise example translates in this case to the uniform distribution being easy (samplable). These notion often arise  in average case complexity, where one cares about the average hardness of computing a function relative to some backgroud distribution over the inputs. A straightforward generalization of this would be to restrict the distance (total variation/KL) between $A(1^n)$ and $\mathcal{P}_n$.
In any case, whenever one is interested in computational hardness, you would probably have to introduce a family of objects rather than talk about the complexity of a specific member.


Determining properties of linear code from generator matrix I have a problem in error-correcting codes.

Say we have a generator matrix of a linear binary code

$$g=\begin{pmatrix}
10011 \\
01101
\end{pmatrix}
$$

  Q1: How many different codeword do we have? How many code bits can the code correct?

Say the generator matrix of a $(6,2)$ binary code is
$$g=\begin{pmatrix}
101001\\
011111
\end{pmatrix}$$

  Q2: How many errors can it guarantee to detect?

My try:

For Q1:

The way I find the number of codeword is count the number of rows in $g$ and raise it as a power to 2. So the answer is $2^2=4$.

For detecting and correcting I’m not sure, should I find the hamming distance and subtract 1?

I hope someone can explain to me how I can find the number bits I can detect and correct.

If the minimal distance is $d$, then

Up to $d-1$ errors can be detected. This means that if a sent codeword is modified by flipping at least one and up to $d-1$ bits, then the receiver can tell that some bits were flipped.

Indeed, suppose that $w$ is the codeword that was sent, and that $w'$ is obtained from $w$ by flipping at least one and up to $d-1$ bits. Since $1 \leq d_H(w,w') < d$ (where $d_H$ is Hamming distance), we see that $w'$ is not a codeword (since the distance between any two different codewords is always at least $d$), and so we can detect that errors have occurred.

Up to $\lfloor \frac{d-1}{2} \rfloor$ can be corrected. This means that if a sent codeword is modified by flipping at most $\lfloor \frac{d-1}{2} \rfloor$ bits, then the original codeword can be recovered.

Indeed, suppose that $w$ is the codeword that was sent, and that $w'$ is obtained from $w$ by flipping up to $\lfloor \frac{d-1}{2} \rfloor$ bits. I claim that $w$ is the unique codeword at distance at most $\lfloor \frac{d-1}{2} \rfloor$ from $w'$. Indeed, if $z$ were another such codeword then
$$
d_H(w,z) \leq d_H(w,w') + d_H(w',z) \leq 2 \lfloor \tfrac{d-1}{2} \rfloor < d,
$$
contrary to the definition of minimal distance.


Can Turing machines simulate the unbounded minization operator applied to a partial function? I am a little bit confused with the unbounded minimization ($\mu$ operator of the $\mu$ recursive functions).

The $\mu$ operator is $\mu(f)(x) = \min(n | f(x, n) > 0)$ and the operator is said safe if we only apply it to functions such that for every $x$, $f(x, n) > 0$ for some $n$. In that case, every recursive function is total and every such function is computable with a Turing machine. The proof simulates every initial function and every operator with a Turing machine. Particularly, for $\mu$, the machine applies $f(x, n)$ for each $n \in \mathbb{N}$ until $f(x, n)$ is not 0.

This can be done because the operator is safe. The machine halts on every input.

When the operator is not safe, we can create partial functions as $\mu(f)(x)$ may be infinite (and thus undefined). Considering Turing machine, partial functions is not a problem as we can state that the machine does not stop if the input is not defined for the fonction. However, I cannot prove that the unbounded and unsafe minimization operator can be simulated by a Turing machine.

Indeed, if $f$ is partial, we can define $\mu$ as $\mu(f)(x) = \min(n | f(x, n)$ is defined and $f(x, n) > 0)$. In that case, there may exist $n = \mu(f)(x)$ and $m < n$ such that $f(x, m)$ is not defined. And, in that case, the machine that was used on the safe case does not halt anymore. Due to the halting problem indecidability, it is not possible to determine if $f(x, n)$ is defined or not.

So, my question is : Are the partial recursive functions (with unsafe operator $\mu$) equivalent to partial functions computable by Turing machines?

Unsafe $\mu$ is strictly stronger than partial TMs.

Indeed, define $f$ such that $f(x,0)=1$ if the $x$-th Turing machine halts on empty input, let $f(x,0)$ be undefined otherwise, and let $f(x,n)=1$ for all $n>0$. Then $f$ is a computable partial function. Let $g:=\mu(f)$. Then $g(x)=0$ if the $x$-th Turing machine halts and $g(x)=1$ otherwise. Hence $\mu(f)$ is not computable.

[EDIT]

The closure of partial recursive functions under unsafe $\mu$ seems to be the arithmetical hierarchy. (In order to make that statement precise, we have to translate between partial functions and subsets of $\mathbb N$.)


Searching in a Binary Search Tree I'm studying Binary Search Trees (BST) and I would like to verify that my understanding of BSTs is correct.

For example, let S = [17, -10, 7, 19, 21, 23, -13, 31, 59].

Binary Search Tree for S, with S1 as root:

How many comparisons is needed to search this tree for the presence of each of the elements in I = {-13, 31}?

Search for -13:

Since -13 is less than 17: Go to left Child
Is -13 < 17?

Comparisons = 1

Since -13 is less than -10: Go to left Child

Comparisons = 2

Item (13) found with two comparisons.

Search for 31:

Since 31 is greater than 17: Go to right Child

Comparisons = 1

Since 31 is greater than 21: Go to right Child

Comparisons = 2

Sincer 31 is greater than 21: Go to right Child

Comparisons = 3

Item (31) found with three comparisons.

Total number of comparisons to find the presence of each item in I: 5.

Is my understanding correct?

Yes... You can also practice with an implementation of your own. I have created such an implementation and a good test is to compile this with different optimization levels in gcc:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct node {
    int node_id;
    int data;
    char *name;
    struct node *left;
    struct node *right;
} node;

node *newNode(int data, char *name, int node_id) {
    node *new_node = malloc(sizeof(node));
    new_node->data = data;
    new_node->name = name;
    new_node->node_id = node_id;
    new_node->right = new_node->left = NULL;
    return new_node;
}

node *insert_node(node *root, int data, int node_id, char *name) {
    if (root == NULL)
        return newNode(data, name, node_id);
    else {
        node *cur;
        if (node_id < root->node_id) {
            cur = insert_node(root->left, data, node_id, name);
            root->left = cur;
        } else if (node_id > root->node_id) {
            cur = insert_node(root->right, data, node_id, name);
            root->right = cur;
        }
    }
    return root;
}

node *find_node_data(node *root, int node_id) {
    if (root == NULL)
        return NULL;
    else if (root->node_id == node_id)
        return root;
    else if (root->node_id > node_id)
        return find_node_data(root->left, node_id);
    else
        return find_node_data(root->right, node_id);
}

void print(node *np) {
    if (np) {
        print(np->left);
        printf("(%d, %d, %s)", np->node_id, np->data, np->name);
        print(np->right);
    }
}

int main() {
    int T = 1000; //test case 1000 nodes
    int data, r2, r;
    int node_id = 0;
    //printf("Input number of nodes:");
    //scanf("%d", &T);
    node *root = NULL;
    srand(time(NULL));
    while (T-- > 0) {

        //scanf("%d %d", &data, &node_id);
        r = (2 + T) * rand() % 100; //node id
        r2 = (2 + T) * (rand() % 100); // data
        printf("Input data. %d:\n", r2);
        printf("node id. %d:\n", r);
        root = insert_node(root, r2, r, "foobar");
    }
    print(root);
    // printf("\n");
    // printf("Find data at node:");
    // scanf("%d", &T);
    print(find_node_data(NULL, node_id));
    T = r;
    printf("node data %d %s", find_node_data(root, r)->data, find_node_data(root, r)->name);
    root = NULL;
    // find_node_data(root, T)->data;
    print(root);
    return 0;
}


Difference between order of convergence and order of consistency? I understand that, as the time step is reduced:

Consistency: The local error must approach zero.
Convergence: The global error must approach zero.

But why are both the order of convergence and consistency of explicit Euler = 1, if the global error is $O(h)$ while the local error is $O(h^{2})$?

More details: The Euler method is used to approximate an initial value ODE by time stepping using the derivative.

For example, for ODE form:
$y'(t) = f(t,y(t)), \qquad \qquad y(t_0)=y_0 $

The solution at point $n$ is:
$y_{n+1} = y_n + hf(t_n,y_n)$

This formula can be obtained from the Taylor expansion, where $h$ is your time step:

$y(t + h) = y(t) + hy'(t) + \frac{h^{2} y''(t)}{2!} + ... $

So the local error is of order $O(h^{2})$. Now the global error is one order less which is why Euler is called a first-order method. So my question is: Why is the order of consistency also 1, even though the local error is of order 2?

A quick and dirty answer: by definition.

Let's use the definition from Wikipedia.
Let $\delta^h_{n+k}$ be the local error.
A method has order $\textbf{p}$ if
$$\delta^h_{n+k} = O(h^{\textbf{p+1}}) \text{ as } h \to 0.$$

Notice $p$ and $p+1$ in the definition. Since the explicit Euler method has local error of order $O(h^2)$, $p+1 = 2$, hence $p = 1$.

On the other side, if you want to know the reason behind such definition, then I think it is about showing you the part of the solution's Taylor polynomial which the method reproduces correctly (by giving you the degree of the last correct term).


For every context-free grammar, is there an equivalent grammar in Chomsky normal form? I thought that, for every CFG, there is an equivalent grammar in CNF. I was told this is false. Can someone explain to me why this is false and possibly provide a counter example?

Depends on how strict you interpret "equivalent". A CFG in ChNF cannot generate the empty string. If you want to have a more precise statement:

  For every CFG $G$ there is a grammar $G'$ in ChNF such that
  $L(G) = L(G') - \{\varepsilon\}$.

So now we have two choices.

Either to accept the loss of the empty string, which in practise is not a big deal. Or we have to adapt the definition to make room for generating the empty string in a special way. This usually means we allow a production $S\to \varepsilon$ where $S$ is the axiom, provided $S$ does not occur as right hand side of productions.

This is a matter of taste: there is no "best" definition. Personally I think having a special production for $\varepsilon$ is not elegant, and prefer a notion of equivalence "upto the empty string".


Hardness of mixed 3-SAT and 2-SAT formula It is well known that 3-SAT is $\sf NP$-complete , but 2-SAT is in $\sf P$. Let there be a formula with $n-1$ clauses with 2 literals each and only 1 clause with 3 literals.

We can solve this case in polynomial time, separating and solving in a brute force manner the 3 literal clause and then for each satisfying assignment try to solve the rest $n-1$ 2-literal clauses. This method can work till $O(\log n)$ clauses with 3 literals.
If we consider a more general case with e.g $\frac{n}{2}$ clauses with 2 literals and  $\frac{n}{2}$ clauses with 3 literals does the problem remain $\sf NP$-complete?

It is a bit confusing because we have a subproblem approximately the same size, implying it is difficult and another one roughly the same size implying it is easy. Is there probably a better method than the one I proposed?

First of all, these are not subproblems but different types of problems. In one your promise me that $n/2$ of the clauses only have 2 literals, and in the other your promise me that only $\log n$ of the clauses have 3 literals. These are simply different problems.

For the general case, it is easier to think about if you let $n = n_2 + n_3$ with $n_2$ being the number of 2-literal clauses, and $n_3$ being the number of 3-literal clauses. Let $f$ be a function such that $n = f(n_3)$. If $f$ is polynomial then the question is $NP$-complete by padding. If $f$ is super-polynomial (but not exponential) then we do not know the complexity of the problem. If $f$ is exponential then your approach of brute-force shows that the problem is in $P$.

Note that for every $f$ you could choose, you have a different problem. They just look similar.


Condition in Arden's rule According to Arden's rule, the language equation $X= AX\cup B$, with unknown $X$, has the solution $X=A^*B$, provided $A$ does not contain the empty string.

My question: what is the problem with the empty string here? Can you illustrate this with a concrete example (which lacks in Wikipedia on this topic).

Consider, for instance, $A = \{ \varepsilon \}$. Then $X = AX$, so $X = AX \cup B$ holds for any $X$ with $B \subseteq X$.


What is the difference between a function and a procedure In general, what is the difference between a function and a procedure when talking about programming languages?

This is rather old distincion (from pascal - which is the most recognisable for this - see vonbrand's answer).
Function returns value, procedure does not.
This is only naming convention, the more common is just calling the both function, and if needed say that one does not return value.
Some programming languages always return value (like the last statement is sent) or get returning cell on stack and does not use it.
Other languages explicitly return empty value, so still you can assign it to variable, so there is no point of this distinction.


Does a proof using the well-ordering principle need a base case? For proofs by well-ordering principle the general template is to consider the negation of some predicate $P(n)$. Then assume the set of all elements that fulfill $\lnot P(n)$, i.e.

$\qquad N = \{ n \mid \lnot P(n) \}$

has a smallest element according to WOP, say $m = \min N$, and if we manage to prove that there is another element $m' \in N$ that is less than $m$ that also negates  then we contradict our assumption that $m$ is the smallest element.

My question is that should we be proving some sort of a base case as well for the above mentioned template. As in proving that for some base case, $P(\mathrm{base})$ is true?

In the Wiki page,

  In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element.

Pay attention to the word non-empty.

Consider the negation of P(n). Before you assume the set that satisfying P(n) is false has a smallest element m, you already assume that the set is non-empty. You prove that there is another element that is less than m. This contradicts the assumption that the set is non-empty. Thus, the set is empty which means P(n) is true.


NFA not accepting a certain string I am trying to make a non-deterministic NFA that does not contain a string "101".

How do I make my NFA so that it does not have this string?

My attempt:

I'll give you a recipe for constructing automata for $\Sigma^* \setminus F$ for any regular $F \subseteq \Sigma^*$.

Construct a (complete) DFA $A_F$ for $F$.
Construct the complement automaton $\overline{A_F}$.
Optional: minimise.

The first step is particularly easy (if maybe time consuming) for finite $F$. The second one is standard (flip accepting and non-accepting states) and should be covered by any textbook on this subject.

Of course, step 1 may blow up the size of the automaton (going from an easy-to-design NFA to DFA); this can in particular be the case for finite sets. In your particular case, though, you never get more than five states.


What is the peak in fitness landscape I have just started reading about fitness landscapes and I couldn't understand what the peak means. What does the peak mean?

It's just the ordinary English-language meaning of the word:

  peak, n.
  [...]
  4 a (1) : the top of a hill or mountain ending in a point
  Merriam-Webster

See, for example, Wikipedia:

  Fitness landscapes are often conceived of as ranges of mountains. There exist local peaks (points from which all paths are downhill, i.e. to lower fitness) and valleys (regions from which many paths lead uphill).


What complexity class is this set of grammars? RE? Given a grammar where every rule has the form $X \to YZ$, $XY \to Z$, $X \to a$, or $X \to \epsilon$ where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, determine whether $S$ can derive $a$.

(Thanks Yuval Filmus for pointing out this characterization - see first comment in linked question)

What complexity class does this correspond to? RE?

Related questions:

What complexity class does is this set of grammars? L-complete?

What complexity class does is this set of grammars? NL-complete?

What complexity class is this set of grammars? In between NL and P?

What complexity class is this set of grammars?

That grammar is unrestricted (not context free, as there are right hand sides shorter than the corresponding left hand side). The languages they generate are recursively enumerable, recursive only in special cases.


Existence of functions that only tests memberships without revealing any information about the members Given a set of strings $\{s_1, s_2, \cdots, s_n\}$, is there a way to encode them to a program $P$, such that given some string,$s$, the program can test the membership efficiently (deterministically or probabilistically), BUT no adversary can ever learn/extract any (member) strings from the program (in polynomial time)?

Can we have such functions with computational assumptions (such that they are secure even in the post quantum regime)?

Note: We can also entertain a program that takes, as input, a valid $s$ that is a member of P, to verify the membership of $s'$.

Yes.  This is known as the problem of obfuscating a point function.  There are standard schemes.  See, e.g., the following papers:

On Obfuscating Point Functions.  Hoeteck Wee.  STOC 2005.

Technically, a point function is a function $f_s(x)$ given by $f_s(x)=1$ if $x=s$ and $f_s(x)=0$ for all $x \ne s$.  There are standard schemes for obfuscating point functions.  This corresponds to the special case of your problem where $n=1$ (hiding a single value $s$).  However, the techniques all generalize to arbitrary $n$, as long as the number $n$ of values is exponentially small compared to the size of the domain of the function.


How do we adjust a model to fit our own dataset? Often, I see people using networks like AlexNet, GoogLeNet, etc to train it on their dataset. These networks are trained or pretrained with a specific dataset, and people fine-tune it to their dataset.

However, is this really suitable? What if the custom dataset had a lot more images than the original or is detecting completely different classes?

In which ways could we modify the networks so they would fit our dataset better?

*one example is faster-rcnn, where lots of people have done this

Is this really suitable?

Well, it works.  At least, in some situations.  And in machine learning, there's a sense in which that is the bottom line: is it useful?  And yes, this approach does appear to be useful, in at least some situations.

Beyond that, I'm not sure what you mean by "suitable".

  What if the custom dataset had a lot more images than the original or is detecting completely different classes?

Sure.  There will cases where fine-tuning probably isn't what I'd recommend you try first.  Look at it this way.  Fine-tuning is one thing you can try.  It's not a silver bullet.  It may work well in some situations.  No one is claiming it will work well in all situations.  There are plenty of situations where it might work poorly.

Fine-tuning is probably most useful if your training set is small (or, at least, not very large), and if there is a pre-trained network that solves a task that is somehow similar to the task you're trying to solve.  The classes don't have to be identical -- for instance, if you are solving some kind of object detection task, but your classes aren't identical to ImageNet, then starting with a pre-trained network that was trained on ImageNet can still be useful, as the image features learned for ImageNet are likely to be useful for other object detection tasks as well -- but the task probably needs to be somehow similar.

If your training set is very large, then fine-tuning might not be the best answer.  You might do better to train a network from scratch, yourself.

Finally: Machine learning is ultimately a pragmatic field.  Don't try to look for the one right answer that works in all situations, and don't expect there to be some theory that can predict what the most effective approach to your problem will be.  Instead, understand that it's a bit of an art; trial and error is often needed; and the ultimate metric is whether it works well enough for the particular problem you are facing right now.


Longest common subsequence with at most one swap Is there a good algorithm for calculating the longest common subsequence where we consider two sequences identical if they can be transformed to one another with at most 1 swapping of subsequences (i.e. taking two non-overlapping subsequences of the same length and substituting them for each other)? For example ABCDEFGHIJ would be considered identical to EFGHABCDIJ but not to ABCDEHFGIJ. Or is there such an algorithm for subsequences of length one?

Swapping two non-overlapping subsequences is same as swapping two non-overlapping substrings of one of the input strings.

A simple algorithm would be to guess the start and end points of the substrings that we want to swap, let them be (s1,t1) and (s2,t2), and run LCS using this swapped string. There are O(m^2*n^2) such guesses and each one takes O(m*n).


Comparison between MA and $P^{NP}$ I am aware that $MA \subseteq ZPP^{NP} \subseteq \Sigma_2^{P}\cap \Pi_{2}^{P}$ and also $NP^{BPP} \subseteq MA \subseteq AM \subseteq \Pi_{2}^{P}$.

My question is: In this whole thing, where does $P^{NP}$ lie? (Obviously, $P^{NP} \subseteq ZPP^{NP}$) But, what about the relationship between $MA$ and $P^{NP}$? Which is contained in which one?

Intuitively, It is known that $MA_{EXP} \not\subset P/poly$, but for $EXP^{NP}$, no polynomial size circuit lower bound is known. Does that mean $P^{NP}$ is contained in $MA$?

Apparently, no relationship is known between $MA$ and $P^{NP}$. Even $BPP$ ($\subseteq MA$) vs $P^{NP}$ problem is still open. It is conjectured though that $MA = NP$ (Under standard hardness assumptions). So, it is likely that $MA \subseteq P^{NP}$.


If $L$ is a regular language, how to prove $L_1 = \{ uv \mid u \in L, |v| =2 \}$ is also regular? If $L$ is a regular language, prove that the language
  $L_1 = \{ uv \mid u \in L, |v| =2 \}$
  is also regular.

My idea: $L$ can be represented as a DFA and then you could add 2 consecutive transitions from every final state for the letters of $v$, creating a new NFA diagram. Is that correct? I'm not sure how to make this a formal proof.

Your idea is correct.

You should take the following path to formally write it up/prove it. First assume that $L$ is accepted by some DEA $M=(Q,\Sigma,\delta,q_0,F)$ then define a new NEA $M'=(Q',\Sigma,\delta',q'_0,F')$ based on $M$. Just express you ideas formally, for example start with

$Q'=Q\cup\{q_\text{new1},q_\text{new2}\}$,
$F'=\{q_\text{new2}\}$,
....

Then you should prove, using the acceptance criteria for $M$ and $M'$, that $w\in L(M) \iff wv\in L(M')$, for all $v\in \Sigma^2$.

Alternative approach

The following idea will also prove the statement but results in an easier proof. First show that the language of words with exactly two characters is regular, and then argue with the closure properties for regular languages.


Computer vision: object detection with labels that are single coordinates Are there papers in the literature that address the following object detection task ?

The task can be described as follows:

Given a set of images, the labels are just coordinates (x,y) that represent the object locations that we wish to detect. A coordinate is not necessarily at the centre of the object and the object can be of any size.
The task is to detect an object that is either a person, a boat, or a car. However, the labels do not state the category of the objects, the labels are simply coordinates that are close to the objects of interest.
The images are taken every hour and they are snapshots of the same scene; therefore, background subtraction techniques might help.
There are around 2000 images of the same scene and each image usually has 2 objects of interest.

I am wondering if such task has been approached before ?

Hog features and SVM have shown great success in detecting humans in images. But the relevant literature use training data where the objects of interest are labelled using a bounding box instead of a single coordinate.

The three main challenges are:

Choosing the bounding box for the classifier is difficult since objects can be of any size.
snapshots of the scene is taken every hour (camera can move slightly as well); so using background subtraction isn't straightforward.
we don't have much labelled data.

It would be interesting to see how people dealt with these challenges.

Thanks!

The state of the art in such problems is done these days via deep neural networks. Among others, two popular and recent approaches for solving the problem of detection and localization of objects are the YOLO paper, and the faster-RCNN, which run a classifier over many variously sized regions in an image.

As humans, boats and cars are popular object classes, I'd first attempt to see what existing pre-trained networks can do for your problem, and then, if needed, try and re-train them using your data.


Datatypes as initial algebras I'm refining my understanding of the connection between initial algebras and datatypes. This paper suggests that one could even represent the categories corresponding to datatypes definitions:

as follows:

Where $1$ is the terminal object of the category.

My question is, how can I justify that $1$ is the terminal object of the category? Do I have to postulate that any type has a unique morphism to $1$? This morphisms would be different that the datatype definitions which would not be nice...

An empty product is the same thing as a terminal object by definition of the product: it's an object $1$ such that for every object $A$, there is a unique morphism $1_A : A \rightarrow 1$. ($1$ is a product of a family indexed by an empty set iff there exists an empty family of morphisms such that for every object $A$ and every empty family of morphisms, there is a morphism $1_A : A \rightarrow 1$ satisfying an empty family of properties.)

An empty product has a simple computational interpretation: it's a type with a single element. Haskell writes () for both the type and its value. ML calls the type unit and the value (). A function whose interpretation is $1_A$ is a constant function taking an object of type $A$ as its argument and returning the value () of type $1$. It's the only total function of this type.

Likewise an empty coproduct $0$ is an initial object: an object such as for every $A$ there is a unique morphism $0_A : 0 \rightarrow A$. The computational interpretation is an empty type. Writing a function whose denotation is $0_A$ is tricky: most programming languages don't allow it without using features that don't fit well in a simple categorical semantics such as exceptions or recursion.

When you're building the categorical semantics, you do need to define everything, including “trivial” cases like terminal objects. You can't just assume that one exists. To give a concrete example, if you take a simple subset of the types of the C programming language allowing only basic types such as int and char and compound types built with struct, you can build binary products using struct, but you cannot build an empty product, because C forbids objects of size 0 and an object whose type is an empty struct would have the size 0.


Finding vertices of a maximum clique in polynomial time Say you were given a black box that solves a clique problem in constant time.

You give the black box an undirected graph G with a bound k and it outputs either "Yes" or "No" that the graph G has a clique with at least k vertices.

How would you use this black box to find the vertices of a maximum clique in polynomial time?

You first give it $(G,k)$, and if it says yes, you do the following.  You pick an arbitrary vertex $v$ and call your oracle with $(G-v,k)$.  If the oracle says yes, throw away $v$ and forget about it.  If it says no, then $v$ is in every clique of size at least $k$.  Output $v$ and decrease $k$ by one and lather, rinse, repeat.


Raising to the T in machine learning What does it mean when in a machine learning paper there is
$(arg)^{T}$, what does the T does to an arg  in this 3b1b video on neural networks he puts the: $(w^{l-1})^{T}$

The notation $A^T$ stands for the transpose of a matrix. It is not specific to machine learning, but rather standard notation in linear algebra. Other notations are sometimes used, for example $A'$.
A related operation is the adjoint $A^*$. The transpose and adjoint are equal for real matrices.


Problems that are hard in the best case? Are there any problems that are hard in the best case? In particular, I was wondering if there are problems that are NP-hard or #P-hard in the best case.

To answer the question, one must first define what is meant by "best case".

One possible definition of "best case" complexity is, what is the running time for the best input?  In other words, take the minimum over all instances, of the running time for that instance.

With that definition, there are no decision problems (problems with a yes/no answer) that are hard in the best case.  That's because I could write a stupid algorithm that knows how to solve one particular problem instance efficiently (it has the solution for that instance hardcoded) and is slow on all else -- in the best case, this would be efficient.

For instance, consider 3-colorability problem, where given a graph we have to determine whether it is 3-colorable.  Let's fix a single graph $G_0$ that we know is 3-colorable.  Now consider the following algorithm:

Algorithm:
Input: a graph $G$
 1. If $G=G_0$, output "Yes".
 2. Otherwise, do something very slow to try to test whether $G$ is 3-colorable.

This algorithm is very slow in the worst case (and typical case), but it is fast in the best case: when the input is $G_0$, it immediately outputs the correct answer.  The existence of such an algorithm shows that 3-colorability is easy in the best case.

There was nothing special about 3-colorability that I used there.  You can apply the same reasoning to any decision problem (or any problem where the output size is not too long).

In retrospect, that was probably the wrong definition.  A better definition would be: for a fixed algorithm, let $T(n)$ denote the minimum over all instances of size $n$, of the running time of that instance.  Then, the function $T(\cdot)$ is the best-case complexity of that algorithm (and of course we want to know the minimum over all algorithms, or a suitable lower bound that holds for all algorithms).  This prevents hardcoding a single instance, because there will be a different best instance for each $n$.  I don't know whether there are any problems that are hard, for this best-case complexity measure.

It's more interesting to look at average-case hardness.  While many problems are hard in the worst case but easy on the average case, there are some problems that are both hard on the worst case and hard on the average case.  One tool used to prove average-case hardness is random self-reducibility.  For instance, the discrete log problem is believed to be hard on the average case.  In particular, it is believed to be hard on the worst case, and we can prove that if it is worst-case hard, then it is average-case hard, too, using a random self-reduction.


Lambda Calculus as a branch of set theory This answer to a question about whether C is the mother of all languages contained an interesting tidbit that I am curious about:

  The functional paradigm, for example, was developed mathematically (by Alonzo Church) as a branch of set theory long before any programming language ever existed.

Is this true?  What is the link between these topics that is so fundamental as to make lambda Calculus an outgrowth of set theory?  The best I can come up with is that standard mathematical functions possess domains and codomains.

It's false. The $\lambda$-calculus arose through efforts to understand foundations of mathematics. Nowadays some people mistakenly equate foundations with set theory. The Stanford Encyclopaedia of Philosophy has a very good writeup on the $\lambda$-calculus, as well as its history, I recommend it.


Building non-deterministic automata I'm trying to make non deterministic automata for specific language .
I cant understand my mistake!
Rules:
1){a,b,c}
2) if I have the sequence "bb" and later in the word I have the sequence "cc" so this is not possible that I have the sequence "cba" between them.
Thank you !

I have tried this question to the best of my ability. Feel free to ask for any clarification or raise any doubts in the comments.

Apart from issues like nullifying the effect of some useful transitions, the problem in your solution is that you've started out at a rejecting state, but unless the string has encountered $bb$ and then $cba$ and subsequently $cc$, it should be accepted.
I've laid out the transitions in a step wise manner, jumping about the states to "reset" the logic that proceeds to rejecting state.
Update:
You can think about the automata as comprising of $3$ parts. q0,q1 check for first occurrence of $bb$. q2,q3,q4 detect the string $cba$. Finally, q5,q6,q7 test for the string $cc$.


If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n)))? I guess this is true, because log is a strictly increasing function, but how do I prove it formally?

I tried something like:

Let $f(n)$ and $g(n)$ be monotonically increasing functions, $c \in \mathbb{R}$ and $n_0 \in \mathbb{N}$, such that $0 \leq f(n) \leq c g(n)$, for all $n \geq n_0$. We must find $c'$ and $n_0'$ such that $$\log(f(n)) \in \{h(n) \mid 0 \leq h(n) \leq c' \log(g(n)), \forall n \geq n_0'\}\,.$$

I got as far as
$$f(n) \leq c g(n) \implies \log(f(n)) \leq \log(c g(n)) = \log(c) + \log(g(n))\,.$$

Then I got stuck.

Thanks in advance!

You need to find a number $n'_0,c'$ such that

$$\log(c) + \log(g(n)) \le c' \log(g(n)) \text{ for all $n \ge n'_0$,}$$

and such that $n'_0 \ge n_0$.

So, see what you can find.  Note that it's ok for $n'_0,c'$ to depend on $c$ and on $g(\cdot)$.

Hint: If you can find $n'_0,c'$ such that $\log(c) \le \log(g(n'_0))$, does anything good happen?  Can you find such a $n'_0,c'$?


How does the double rotation in AVL tree work? I am trying to find out from this visualization how does the AVL trees work. But I am not able to find out how is the algorithm choosing which vertex is the right one to use as "partial root".

The simple rotation is actually very simple, but when it comes to the double rotation it is much worse.

There are some tricks with signs of vertices when inserting a new vertex, but I don't completely understand that either (and also I am not sure if it is important for the rotation).

EDIT:
I add a drawing of my Insertion. I would expect that the double rotation will choose the purple (left) variant (it seems simplier), but the visualization choose the brown one. Why is that?

At the drawing is correct the brown variant. The purple isn't binary search tree (thanks, Hendrik Jan for this clarification) at all.
Why? Because it is not in the right order (for all nodes in a BST must be true, that all nodes in its right subtree have bigger value and all nodes in the left subtree have a smaller value than the node).

About the double rotation itself:
The problem was that I didn't know how to choose the correct vertex, the right answer is that you have to take the middle one as the root of the new subtree (11 from the set 10, 11, 14 on my drawing) and the rest must fit the rules for the binary search AVL trees.


Prove the existence of a proposition logical formula so that following conditions are fulfilled For two proposition logical formulas $\phi$ and $\chi$ so that $\phi\implies\chi$ is generally valid. How can I prove that there is a formular $\psi$ with $var(\psi )\subseteq var(\phi )\cap var(\chi )$ so that $\phi\implies\psi$ and $\psi\implies\chi$ are generally valid?

The formula $\psi$ is called an interpolant and the method of finding such an interpolant is called Craig interpolation. On the Wikipedia article you can find more information about it, including a proof that interpolants always exist in propositional logic.


Conversion from nondeterministic PDA to deterministic PDA Why is the conversion from nondeterministic PDA to deterministic PDA not possible?

There are languages accepted by nondeterministic PDAs that cannot be accepted by deterministic PDAs. Perhaps the easiest way to see this is to consider inherently ambiguous context-free languages. As context-free languages, they are accepted by some nondeterministic PDA. On the other hand, every language accepted by a deterministic PDA has an unambiguous grammar, so they cannot be accepted by any deterministic PDA.


Closure property and undecidability I know that if a language class is closed under operation X then the problem  is decidable.

for eg: "Intersection of two CSL is CSL"? this problem is decidable because it is already proved that CSL follow intersection closure property.

But what if language is not closed under the operation.
for eg: problem: Is intersection of two CFL is CFL or not?

as CFL/DCFL is not closed under intersection. then is this true saying that not following closure opertion implies Undecidable problem?

My approach:This problem is same as saying that "A given CSL is CFL or not?" because intersection of two CFL's is CSL for sure. as every CSL is RE then can we also say this problem as "A RE is CFL or not"? if my last statement is true then by using rice theorem this problem must be undecidable and even not RE.

how to approach these type of question when a language is not closed under the given operation?

I don't think closure property implies decidability. Consider r.e. languages and intersection. R.e. languages are closed under intersection, e.g., if $L_1$ and $L_2$ are r.e. languages then $L_1 \cap L_2$ is also r.e. but may be undecidable.

On the other hands, CFLs are not closed under intersection. However, a language which is intersection of two CFLs is not CF but may be decidable. For example $L_1=\{a^ib^ia^j |i,j \geq 1 \}$, $L_2=\{a^ib^ja^j |i,j \geq 1 \}$ are both CF, however $L_1 \cap L_2 = \{ a^ib^ic^i | i,j \geq 1\}$ is not CF, but it is still decidable.


What is the optimal strategy for filtering a large collection of items with multiple filter functions? I have a large collection of items, and a list of independent filters (boolean functions). I want to find the collection of items that pass all of my filters as quickly as possible. This must involve looping over every item in the collection and applying each filter to each item. An item will be rejected early if any one of the filters fails during this process.

Each filter has a runtime that varies significantly. And, we know a-priori what percent of the collection each filter will filter out. Given this, how do I find the ordering I should apply my filters to each item with the fasted expected run-time overall?

For example, filter A runs in 5 ms and filters out 50% of the collection on average. Filter B runs in 1 ms and filters out 25% of the collection on average. From this, we know that ordering A,B gives 5 + 0.5 * 1 = 5.5 ms average runtime, and B,A gives 1 + 0.75 * 5 = 4.75 ms average runtime. So B,A is our fastest ordering.

I think this admits a dynamic programming solution (since fastest ordering is runtime of first filter + (1 - filter fraction) * (optimal ordering of the rest), but I was wondering if this problem has a name and has been studied before? Could somebody point me to any papers?

EDIT: also, I forgot that the probability of filtering and the run-times will be correlated between filters, so my analysis above is wrong and the problem is harder. I think I can solve this with enough time but I want to catch up on prior-work before I start, if there is any (it seems like it could be a common problem). I haven't had any luck finding anything so far though.

Independent filters

If the filters are independent, a greedy algorithm can be used to find the optimal order.  Sort the filters by increasing value of $t/p$, where $t$ is the time to run the filter and $p$ is the fraction of items that are filtered out by the filter.  This gives the optimal order.

To give some intuition for why this might be a plausible answer: ideally, we'd prefer filters that take less time; and ideally, we'd prefer filters that filter out a higher fraction of items.  Intuitively, you can see how $t/p$ somehow incorporates both of those.

A formal proof of optimality involves an exchange argument.  I won't detail the proof here, as it can be derived easily using standard techniques.  For a detailed writeup of the proof, see Determine what is the best order for running filters on a dataset.

Correlated filters

If there can be correlations between the filters (i.e., they are not independent), the optimal order cannot be determined from the information provided without knowledge of the correlations.

Here's an example, based on making a small modification to your example.  Suppose we have two filters, filter A and filter B.  Suppose filter A runs in 4.5ms and filters out 50% on average; filter B runs in 1ms and filters out 25% on average.  Also suppose that anything filtered out by filter B is also filtered out by filter A.  Then the optimal order is to just do filter A.  Your formulas give A,B: $4.5+0.5 \times 1 = 5.0$ and B,A: $1 + 0.75 \times 4.5 = 4.375$, so your formulas might make B,A look like the best choice -- but in fact just doing A alone is even better.

Unfortunately, in practice I would expect that filters might often be correlated.  To deal with this, you'd need to know some information about the correlation structure.  If you don't have any information on the correlation structure, one possible approach is to use the greedy strategy, recognizing that it might not be optimal for your particular situation.  Another possible approach is to gather data on the correlation structure and then use that additional information to try to find a better order, though this may not admit as clean of an answer.


How are image files, sounds, data, etc. compiled/linked in to a single file? I'm both asking for me & future readers as to how pictures, sounds, textures, assets, and such are compiled and linked in to one binary/program, and how that process works.

I have seen this in standalone programs I have downloaded on Windows, and I'm fairly certain any OS can implement this. It appears that, instead of keeping the data stored separately as individual files within the filesystem, all data is converged in to one file. When you run the program, it's as if the data could have just, instead of requiring multiple scattered files through the drive, directories, subdirectories, etc., been bound to one program with everything in it; no need for fragmentation, missing files, etc.

So, to sum this question up, let me first illustrate some key points:

I had originally thought that, since all files on the computer are basically high-and-low voltage sources at the lowest level, files can be converged together, being similar to "zipping/unzipping files." Using this common ground, it's easy to see how the data of a file, any file, could be bound/binded together with other data, and act, from the scope of the filesystem and GUI, as "just a file." But many things are actually in it that don't have to only represent just a typical idea of a "program" with some people's view of it as only instructions like adding, moving data around, etc.

I am not sure of this, but I have a good sense that it's similar, so this why I'm asking for clarification.

When you see a standalone program from one file that contains external assets when you run it (texture files, video data format, image data, sounds, other resources, etc.),  it's clear that the single executable file has all the data necessary "packed" in to one somehow, or the such.

How does the compiler/linker do this, how would the program/library/etc. access the data converged in it as opposed to differing from separate "files" independently, and how are compiler's/linker's settings adjusted to do this in any general sense?

NOTE: Programmers, StackOverflow, Superuser, and few others deny this question, and give no reason why, so I figured this area might see it fit.

A file is just a file. Any given sequence of bytes can be interpreted as instructions for the CPU, pixels of a graphics file or anything else. And a file can contain sequences of bytes that should be interpreted as instructions and sequences of bytes that should be interpreted as graphics. If the executable part has been written correctly, it will never try to interpret the graphics part of the file as CPU instructions; when it needs to refer to the graphics, it knows where they are in the file (and, hence, the memory image) and starts reading from the appropriate address. In principal, the operating system doesn't even need to know it's doing this.