Why this greedy algorithm fails in rod cutting problem? Recall the rod cutting problem.

  Given a rod of length $n$ inches and a table of prices $p_{i}$ for $i=1,2,3,4,\,.\,.\,.$ determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces.
  You may assume no cutting cost.

The following is a question from CLRS 15.1-2.

  Show, by means of a counterexample, that the following ‘greedy’ strategy does not always determine an optimal way to cut rods. Define the density of a rod of length i to be p_i/i, that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length i, where 1≤i≤n, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length n-i.

Consider prices up to length $4$ are $p_1=1, p_2=5, p_3= 8, p_4 = 9$ respectively.
So, densities are $d_1=1, d_2 = 2.5, d_3= 2.67, d_4 = 2.25$ respectively.

If we are given a rod of length $4,$ then an optimal way of cutting the rod to maximize revenue is $2$ pieces of length $2$ each, generating $5+5 = 10.$

However, greedy algorithm above will suggest cutting the rod into 2 pieces of length $3$ and $1$, generating revenue $8+1=9.$

I obtain this example by merely following the same prices given in CLRS but do not understand why such greedy algorithm fails to provide optimal way of cutting  the rod.

Because a local maximum is not always a global maximum.

The length 3 rod is the most price-for-length effective single rod piece. But the optimization goal isn't to find the best price-to-length ratio for a single piece, it's to find the best total price for how much rod we actually have! Once the greedy algorithm chooses the shiniest, most appealing first piece, it is now stuck for the rest of the problem with a highly suboptimal remaining length according to the highly nonlinear price table.

In general, most optimization problems cannot be solved optimally by a greedy strategy. Those that can tend to have some exceptional property that guarantees that a local maximum will also be a global maximum.


Complexity/Hardness of a generalization of an Inclusion/Exclusion problem I would appreciate some help in determining the complexity/hardness of an inclusion/exclusion problem described in Wikipedia: https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle#A_generalization

Namely, given a family of subsets $A_1$, $A_2$, ..., $A_n$ of a universal set $S$, I need to calculate the number of elements of $S$ which appear in exactly some fixed $m$ of these sets.

Would that be #P?

Thank you.

For each element in $S$, count the number of times it is a member of $A_i$, $1\le i\le n$. If that number is $m$, we add 1 to the tally. The final tally is what we wanted.

The above algorithm takes $O(tn)$ time if the computational cost to check membership is $O(1)$. It takes $O(ttn)$ time if the computational cost to check membership proportional to the size of the set, which is at most $t$.

So you can see the problem is in $P$. It has nothing to do with that general inclusion–exclusion principle.


Find all the cumulative sums in a DAG Let's call G a DAG (directed acyclic graph) with N nodes labeled with a natural value.

We define the cumulative sum of a node v as the sum of the value of all the ancestor nodes of v (including v).

For example, the cumulative sum of d in the following DAG is 7:

      a (2)
     / \
    v   v
(1) b   c (3)
     \ /
      v
      d (1)

Is it posible to compute the cumulative sum for a set of M nodes in G, in less than O(M*(N + E))?

Clarification: computing the cumulative sum for a set of nodes refers to computing the cumulative sum for each node of the set.

Further clarification: for a given cumulative sum, each ancestor is counted only once (notice that the ancestors of $u$ include $u$):

$cumsum(v) = \sum_{u \in \text{ancestors of } v} \text{value of } u$

Which does not imply:

$cumsum(v) = \text{value of } v + \sum_{u \in \text{direct ancestors of } v} cumsum(u)$

because this last formula may count ancestors multiple times. For example, in the diamond example we have:

$cumsum(d) = 7$
$cumsum(b) = 3$
$cumsum(c) = 5$
so $cumsum(d) \neq 1 + cumsum(b) + cumsum(c)$

Solution in O(M*(N + E)):

  To compute the cumulative sum of a single node v in O(N + E), sort the
  DAG topologically and traverse the sorted list of vertices backwards,
  tainting all ancestors of v with the back edges, and adding the values
  of all the ancestors. (You could also just do a DFS for the same
  price).

  Doing this for each node in the given set of M nodes gives a running
  time of O(M*(N + E)).

  Although it doesn't affect the final running time, the topological
  sort could be done only once before looping through each cumulative
  sum calculation.

It's possible to do slightly faster, by using sophisticated algorithms for transitive closure based on fast matrix multiplication, but apparently it is not known how to do this much faster than the naive solution.  See https://cstheory.stackexchange.com/q/553/5038 and https://cstheory.stackexchange.com/q/736/5038 and https://cstheory.stackexchange.com/q/4258/5038.


Incorporating newline-as-statement-terminator heuristics into context-free languages Several block structured languages (Scala, Go, Ruby, Julia, Quorum, ...) use semicolons as statement terminators, but allow newlines instead of semicolons under certain circumstances.

My question is: how can I represent Scala-like optional semicolons in a context free grammar?  The specific issue is that some kinds of nesting delimiters "enable newlines" while others "disable newlines," so you need to pay attention to what kind of delimiters you are most immediately inside of.

I'm specifically asking about Scala's heuristic, because Julia and Quorum don't have specs.  Ruby has a spec, but handles the problem by scattering "[no line-terminator here]" throughout the formal grammar and I've been unable to find a general rule.  Go has a well described heuristic but it's lexical only, which makes it obvious how to specify and implement, but its usability is somewhat disappointing.  (Go inserts a semicolon even if you haven't closed the most recent ( token.)

Scala goes well beyond the Go lexical rule with a nesting rule (cf reference, Section 1.2).  In addition to lexically ensuring that both the token before and after the newline are consistent with the insertion of a statement terminator, newlines-as-statement-terminators are disabled between matching ( and ) parenthesis and [ and ] brackets, but then re-enabled between matching { and } braces.

I can figure out how to implement a simple pre-processor as a push-down automaton.  The automaton starts with enabled on the stack.  As you process the token stream, when you see a ( or [ push disabled onto the stack, when you see { push enabled onto the stack, and when you see ), ] or } pop the top of the stack.  Then when you see a newline that otherwise satisfies the lexical rules for the insertion of a statement terminator, you insert the terminator if and only if enabled is on the top of the stack.
So Scala's newline-to-statement-terminator rule is "context free" in some sense, but I haven't been able to figure out how to incorporate this push-down automaton in with the rest of the language grammar.

The basic problem we have to solve is how to separate sequences of statements

(A)
statement1
statement2

from multi-line statements

(B)
state
ment

Dedicated separators such as semicolons are a time-honored way to do this clearly
but some people dislike them. An alternative is to require some kind of syntax
for triggering (B) (I think I've seen state \ \nment) which is likely to be
rejected for similar reasons.

So, one way to do this is to ensure that the set of statements is prefix-free,
that is no statement of the form (B) can parse as (A) ever. Of course, that is
rarely possible as you want to allow (improperly parenthesised) statements like

x = 3 - 2 + x

and at the same time blocks like

x = 3
- 2 + x
[returns 1]

Such languages (e.g. Scala) are inherently ambiguous on a syntactic level (without dedicated statement separators). On a semantic level, you may be able to resolve the ambiguity, e.g. you might figure out during name analysis that x is not initialised in reading (B) or during type analysis that the block should return an integer, which reading it as (B) may not do.

Needless to say that many dynamic languages don't even allow for this because all variables may be implicitly initialised or every statement returns something or what not.

In other words, I think this language "feature" is beyond the capabilities of PDAs if you don't want rigid precedences. You need backtracking, look-ahead,
semantic analysis and even guesswork.


Does this LCS algo generate all the CS or only all the LCSs? The Wikipedia article on LCS has an algorithm that backtracks all the LCS strings. This link redirects to the desired bulletin in the article. The C table in the backtrackAll function is pre-calculated, if you go up a tad bit. C[i][j] stores the LCSLength for given str1[1...i], str2[1...j].

(screenshot, for a quicker reference)

My understanding is that it generates all the common sequences since either or both if conditions at the end are satisfied, which runs the program for the sub-cases. Once the last letters are matched, every string upto that point (with the current X[i] as the last letter) is printed.

I somewhere fail to digest the algorithm properly and completely. An explanation might help me very much.

In the penultimate if, does changing writing the piece of code as  R := R $\cup$ backtrackAll(C, X, Y, i, j-1) (instead of  R := backtrackAll(C, X, Y, i, j-1)) change anything? I feel that it doesn't, given it's a top down approach and it only unions with the empty set R = {} above. Note that R is already defined above and the if is reached only after going through that empty set definition step, which rules out the possibility of having an error output.

Wikipedia is being sloppy. The procedure returns all LCSs of $X[1..i]$ and $Y[1..j]$, which corresponds to $C[i,j]$. It should mention that in order to obtain all LCSs, we need to set $i=m$ and $j=n$.
If $X[i] = Y[j]$, then every LCS of $X[1..i]$ and $Y[1..j]$ is obtained by taking an LCS of $X[1..i-1]$ and $Y[1..j-1]$, and adding to it $X[i] = Y[j]$.
If $X[i] \neq Y[j]$, then every LCS of $X[1..i]$ and $Y[1..j]$ must be either an LCS of $X[1..i-1]$ and $Y[1..j]$, or an LCS of $X[1..i]$ and $Y[1..j-1]$ (or both). If $C[i-1,j] > C[i,j-1]$, then only the former are LCSs of $X[1..i]$ and $Y[1..j]$. If $C[i-1,j] < C[i,j-1]$, then only the latter are LCSs of $X[1..i]$ and $Y[1..j]$. If $C[i-1,j] = C[i,j-1]$, then both types are LCSs of $X[1..i]$ and $Y[1..j]$.
This recursive procedure could count the same sequence more than once — this happens for example for the arrays $ab$ and $ac$, where $a$ will be reached twice.


How many Turing machines are there with $c$ characters and $n$ states? By $c$ character I mean the numbers $0,\dots,c-1$ and the blank symbol $b$, and by $n$ states I mean $n$ non-accepting states, reject and accept.

We can assume every $n$-state Turing machine has $(c+1)n$ transitions going to either another non-accepting state, reject, or accept, that is that it has a transition for every state and character on the tape. It can either move to the left, right or not shift each transition. I tried some myself to figure out how many Turing machines there were and got the two following incompatible results.

We have $(c+1)n$ transitions and each transition has $3(n+2)(c+1)$ different options. Encoding it as a 5 tuple I get $3n(n+2)(c+1)^2$, but taking from options for transitions for each transition gives me $((c+1)n)^{3(n+2)(c+1)}$

Is either of these correct and if so why?

The answer is $(3(c+1)(n+2))^{(c+1)n}$. You get this by considering all functions of the type $(Q \setminus F) \times \Gamma \to Q \times \Gamma \times \{L, R, N\}$. Where $Q$ is the set of states, $F$ is the set of final states, $\Gamma$ is the alphabet including the blank character, and $L$, $R$, $N$ are the left shift, right shift, and no shift respectively. You can view this as a problem of picking $|(Q \setminus F) \times \Gamma| = (c+1)n$ elements from a set of cardinality $|Q \times \Gamma \times \{L, R, N\}| = 3(c+1)(n+2)$ with replacement.


Why are Linearly Bounded Turing Machines more powerful than Finite State Automata? I was under the impression that our computers, being finite, are ultimately no more powerful than (extraordinarily large) Finite State Machines.  However, Linearly Bounded Turing Machines are also finite, but it seems that Regular Languages are strictly an improper subset of Context-Sensitive Languages.

Obviously, I'm missing something here.  What is going on?

The linear bounded Turing machine is restricted to a tape whose length is a linear function of the length of the input.

If the length limit were a constant, then the machine would be no more powerful than a DFA. However, a DFA cannot grow more states to cope with a longer input, which in effect the LBTM can do (taking the state to be the entire machine configuration.) So the LBTM is strictly more powerful.


Can the unbounded knapsack problem be described as a matrix exponentiation? It seems that the general approach to a dynamic programming problem is to formulate a recurrence relation and then either implement a top down recursive solution or a bottom up iterative solution.

But if there's a recurrence relation I think that means we could potentially represent the problem as a state vector and a matrix updates the state through a multiplication. This approach can be used to generate the Fibonacci sequence for example.

Can this linear algebra approach be applied generally to any dynamic programming problem such as the unbounded knapsack problem?

For the Fibonacci sequence, the recurrence relation is linear.  That's why it can be represented as a matrix representation, i.e., using linear algebra.  If the recurrence relation isn't linear, you can't do something like that.

So, no, you can't always do that.


Minimize the maximum Hamming weight of basis vectors spanning a binary subspace In the course of my research, I stumbled upon a problem which can be recast as the following decision problem:

First some notation:

Let $\mathbb{F}=\{0,1\}$ be the binary field. For $x\in\mathbb{F}^N$, $N\in\mathbb{N}$ arbitrary, let $w(x)$ denote the Hamming weight of $x$, i.e., the number of non-zero components.

Let $B\subset \mathbb{F}^N$ be an arbitrary set of binary vectors. Define the Hamming weight of $B$ as $w(B)\equiv \max_{b\in B}w(b)$.

Now the problem:

  Given a linear subspace $V\leq \mathbb{F}^N$ and a positive integer $C\leq N$.

  Is there a basis $B$ of $V$ such that $w(B)\leq C$ ?

The "size" of a particular instance is the dimension $\rm{dim} V=K\leq N$, as the brute-force solution requires the computation of $w$ for all possible bases of $V$.

Clearly, the evaluation of $w(B)$ requires $\mathcal{O}(KN)$ steps; therefore the problem is in NP.

As an example: If $V=\mathbb{F}^N$ and $C\geq 1$, the answer is positive as the standard basis ($e_i=(0,\dots,1,\dots,0$) has hamming weight 1. Obviously this is not the case for generic, non-trivial subspaces $V$.

I think the problem is closely related to the theory of linear binary codes (in fact, $V$ is one). In this context, however, people seem to be more interested in the minimum Hamming weights as these relate to the Hamming distance of the code.

As my understanding of and experience in complexity theory is rather sparse (my background is condensed matter physics), I do not know wheter this problem is known in complexity theory. If so, what is its complexity class (time complexity) ? Are there any relevant publications for this particular problem?
Maybe it's even a simple textbook problem?

Any hint is welcome. Thanks in advance.

This is background, rather than a complete solution of your specific question.

What you're looking at are called linear anticodes in the literature, while Ahlswede uses the term "diameter" for the maximum distance of a code. Like normal codes, there are some bounds on maximum size, given length and distance.

The problem may also be stated in terms of the minimum number of coordinates where two codewords agree. If the alphabet is nonbinary, it gets much more complicated, and [1] has an upper bound for that case, but also discusses the result from [2] which is the following:

Given a binary anticode with diameter (maximum distance) $n-t$ over the binary alphabet (which need not be linear), letting $N_2(n,t)$ be the maximum cardinality of such a code we have
$$N_2(n,t)=\left\{
\begin{array}{lrr}
\sum_{i=0}^{(n-t)/2} \binom{n}{i},&\quad& if~n-t~is~even,\\
 & & \\
2 \sum_{i=0}^{(n-t-1)/2} \binom{n-1}{i},&\quad& if~n-t~is~odd.
\end{array}
\right.
$$

See the reference [1] for details. Apparently the binary diametric theorem above was proved by Kleitman in [2]. This bound applies to all anticodes and would apply to your linear anticode as well.

Farrell had an earlier article on anticodes which considered linear anticodes obtained by deleting columns from a simplex code, which may also be of interest, it shouldn't be hard to locate the reference.

[1] Ahlswede and Khachtarian, The Diametric Theorem in Hamming
Spaces:Optimal Anticodes, Adv. Appl. Math:20, 429:449 1998.

[2] D. J. Kleitman, On a combinatorial conjecture of Erdos, J. Combin. Theory, Volume 1, pp.209-214, 1966.


Model Checking CTL* algorithm Currently I'm trying to understand the CTL* model checking algorithm from this book. The basic idea is clear to that we can use the LTL algorithm to whenever we have a subformular $E\phi$ or $A\phi$ but I have still a question I can't figure out:

Why is there no case for $\phi_1 U \phi_2$ in this algorithm? Of course we can write the until modality as a release modality but this case isn't here either. So is this algorithm incomplete or have I missed something?

The algorithm is full and correct. If you look back to definition 6.80 in the same book, you will see that the until operator is part of path formulae, which in the CTL* MC algorithm are checked via a standard LTL model checker as written in the last switch case ($\exists \varphi$). The $\varphi$ stands for any path formula.

The algorithm also states that you take the negation of $\varphi$. So then you need to take the complement of the satisfaction set.


Proving equivalency of regular expressions x,y are regular expressions, prove this:
(xy+x)$^*$x = x(yx+x)$^*$*
(* in this expression is kleene star)

I am looking for a method that is applicable to prove such questions.
I know that proof needs to show that:

1) (xy+x)$^*$x => x(yx+x)$^*$

2) x(yx+x)$^*$ => (xy+x)$^*$x

My attempt is like this:

1) (xy+x)$^*$x =

= x(y+epsilon)$^*$x  by pulling x out -the x on the left is the one pulled out

= x(yx+x)$^*$    by distributing the last x

2) x(yx+x)$^*$

= x(y+epsilon)$^*$x   by pulling the x out -the right x is the one pulled out

= (xy+x)$^*$x         by distributing the first x

Does this make sense?
Thanks!

Conceptually, the simplest approach is:

Convert both regular expressions to NFA.
Determinise both NFA.
Minimize both DFA.
The regular expressions are equivalent if and only if the minimal DFA are isomorphic.

The requisite algorithms and theorems are taught in (about) every introducory class to formal languages resp. automata and can be found in (every) textbook on the topic. In fact, the point of this exercise probably was to come up with this approach, combining results from the course. Sorry for spoiling it.


The "CPS" approach has done great harm to performance in SML/NJ; reasoning desired In a comment to Learning F#: What books using other programming languages can be translated to F# to learn functional concepts? Makarius stated:

  Note that the "CPS" approach has done great harm to performance in
  SML/NJ. Its physical evaluation model violates too many assumptions
  that are built into the hardware. If you take big symbolic
  applications of SML like Isabelle/HOL, SML/NJ with CPS comes out
  approx. 100 times slower than Poly/ML with its conventional stack.

Can someone explain the reasons for this? (Preferably with some examples) Is there an impedance mismatch here?

At first approximation, there is a difference in "locality" of memory access, when a programm just runs forward on the heap in CPS style, instead of the traditional growing and shrinking of stack.  Also note that CPS will always need GC to recover your seemingly local data placed on the heap.  These observations alone would have been adequate 10 or 20 years ago, when hardware was much simpler than today.

I am myself neither a hardware nor compiler guru, so as second approximation, here are some concrete reasons for the approx. factor 100 seen in Isabelle/HOL:

Basic performance loss according to the "first approximation" above.
SML/NJ heap management and GC has severe problems to scale beyond several tens MB; Isabelle now uses 100-1000 MB routinely, sometimes several GB.
SML/NJ compilation is very slow -- this might be totally unrelated
(note that Isabelle/HOL alternates runtime compilation and running code).
SML/NJ lacks native multithreading -- not fully unrelated, since CPS was advertized as "roll your own threads in user space without separate stacks".

The correlation of heap and threads is also discussed in the paper by Morriset/Tolmach PPOPP 1993 "Procs and Locks: A Portable Multiprocessing Platform for Standard ML of New Jersey" (CiteSeerX) Note: PDF at CiteSeerX is backward, pages from from 10-1 instead of 1-10.


Finding maximal factorization of regular languages Let language $\mathcal{L} \subseteq \Sigma^*$ be regular.

A factorization of $\mathcal{L}$ is a maximal pair $(X,Y)$ of sets of words with

$X \cdot Y \subseteq \mathcal{L}$
$X  \neq \emptyset \neq Y$,

where $X \cdot Y = \{xy$ | $x \in X, y \in Y\}$.

$(X,Y)$ is maximal if for each pair $(X',Y') \neq (X,Y)$ with $X'\cdot Y' \subseteq \mathcal{L} $ either $X \not \subseteq X'$ or $Y \not \subseteq Y'$.

Is there a simple procedure to find out which pairs are maximal?

Example:

Let $\mathcal{L} = \Sigma^∗ab \Sigma^∗$. The set $F = \{u, v, w\}$ is computed:

$u =(\Sigma^∗, \Sigma^∗ab\Sigma^∗)$
$v = (\Sigma^∗a\Sigma^∗, \Sigma^∗b\Sigma^∗)$
$w = (\Sigma^∗ab\Sigma^∗, \Sigma^∗) $

where $\Sigma = \{a,b\}$.

Another example:

$\Sigma = \{a, b\}$ and $\mathcal{L} = \Sigma^*a\Sigma$
Factorization set $F = \{q, r, s, t\}$ with

$q = (\Sigma^*, \mathcal{L})$
$r = (\Sigma^*a, \Sigma + \mathcal{L})$
$s = (\Sigma^*aa, \epsilon + \Sigma + \mathcal{L})$
$t = (\mathcal{L}, \epsilon + \mathcal{L}) $

As suggested in the comments to the question, I will try to give an (unfortunately partial) answer to the question, at least to the extent that I have understood the problem myself (this implies that you may well find mistakes, and if you find a way to more briefly or clearly explain one of the below points, feel free to edit the answer accordingly):

First, one should note that we do not actually have to compute the universal automaton of a language if we want to compute the factorizations of a language.

From the paper mentioned in my comment¹, there is a 1-1 correspondence between left and right factors of a regular language, that is, given a left factor of the language, the corresponding right factor is uniquely determined and vice versa.
More precisely, we have the following:

Let $(X,Y)$ be a factorization of $L$. Then
$$Y = \bigcap_{x \in X}x^{-1}L, X = \bigcap_{y \in Y}Ly^{-1},$$
that is, any left factor is an intersection of right quotients, and any right factor is an intersection of left quotients. Conversely, any intersection of left quotients of $L$ is a right factor of $L$, and any intersection of right quotients of $L$ is a left factor of $L$.

Note that for a regular language, there is only a finite set of left and right quotients, and thus or problem reduces to computing the left and right quotients of a language, and then to compute their $\cap$-stable closure, that is, a minimal superset of the quotients that is closed under intersection. These are then precisely the right factors and left factors, and then it is usually easy to see which pairs are subsets of $L$.

Example

In order to illustrate the above points, consider the first example in the question (of which I also think that it is incorrect in the paper):

Let $L = \Sigma^\ast ab \Sigma^\ast$. Now, the left quotients of $L$ are the sets $x^{-1}L$ for $x\in \Sigma^\ast$, that is, those words $u$ in $\Sigma^\ast$ that can be prefixed with $x$, i.e. $xu \in L$. When is $y^{-1}L=x^{-1}L$ for distinct $x,y$? This is the case if and only if $x$ and $y$ can be augmented to words in $L$ with precisely the same suffixes. This means, to put it into more familiar terms, they are Nerode-equivalent, and the suffixes that are needed to append to words in a Nerode class are precisely the respective left quotients.

For $L$, we see that our Nerode-equivalence classes are

$N_1$, the set of words not containing $ab$ as a factor and ending with $a$,
$N_2$, the set of words ending with $b$ and not
containing $ab$ as a factor, and
$N_3$, the set of words
containing $ab$ as a factor, that is, $N_3 = L$

They can be augmented with the following sets (that is, these are the left quotients of the words in the respective classes):

$S_1 = x^{-1}L$ for $x$ in $N_1$ consists of all words in $L$ (any word can be augmented with a word containing $ab$ as a factor and thus becomes a word in $L$) and $b\Sigma^\ast$, that is $S_1 = L \cup b\Sigma^\ast$
$S_2 = x^{-1}L$ for $x$ in $N_2$ is the language itself, that is, $S_2 = L$ and
$S_3 = x^{-1}L$ for $x$ in $N_3$ is obviously $\Sigma^\ast$. That is, we have found three right factors of $L$. As $S_2\subset S_1\subset S_3$, their $\cap$-stable closure is trivially ${S_1,S_2,S_3}$, and those are then precisely the right factors.

Hence, our factorization set $\mathcal{F}_L$ is of the form $(P_1,S_1),(P_2,S_2),(P_3,S_3)$.

Now, for the left factors $P_i$, we use the equations of the beginning of this answer:

$$ P_i = \bigcap_{x\in S_i} Lx^{-1} $$.

For $P_1$, this yields $L \cup \Sigma^\ast a$, for $P_2$ we get $\Sigma^\ast$ and for $P_3$, we obtain $L$. You can see this by inspection (the most popular excuse for being too lazy to state a formal proof) or by explicitly computing the right quotients (which is fairly analogous, although not completely, to computing the left quotients).
Our factorizations are thus given by $\mathcal{F}_L = {u,v,w}$ where

$u = (P_1,S_1) = (\Sigma^\ast ab \Sigma^\ast \cup \Sigma^\ast a, \Sigma^\ast ab \Sigma^\ast \cup b\Sigma^\ast)$
$v = (P_2, S_2) = (\Sigma^\ast, \Sigma^\ast ab \Sigma^\ast)$ and
$w = (P_3, S_3) = (\Sigma^\ast ab \Sigma^\ast, \Sigma^\ast)$

Summary

To summarize (as you were asking for a simple procedure):

For computing the factorizations of a language $L$, first compute the left quotients of $L$.
You can do so, in the language of the paper, by constructing a minimal DFA $A$ for $L$ and then for each state $q$ in $A$ (corresponding, as a Nerode-equivalence class, to a left quotient) compute the future of $q$ in $A$, thus obtaining one left quotient of the language for each state.
The collection of left quotients obtained in this way yields, in general, a subset $S_R$ of the right factors.
Compute then the $\cap$-stable closure of $S_R$, which can be done in practice by forming the intersection of any subset of $S_R$ and adding any subset obtained in this way to $S_R$.
The set $S_R$ together with all the intersections from the previous step is then the set of right factors of $L$.
In order to obtain the left factors, we can compute the right quotients of $L$.
These are sets of the form $Ly^{-1}$, for $y\in \Sigma^\ast$. Now, these are again only finitely many, and for $x\neq y$, we have $Ly^{-1} = Lx^{-1}$ if and only if  for all $u\in \Sigma^\ast$, $ux \in L \Leftrightarrow uy \in L$, that is they can be prefixed to words in the language with precisely the same set of strings.
To compute $Lx^{-1}$, consider those states $q$ in $A$ such that $x$ is contained in the future of $q$. The union of the pasts of those states constitute one right quotient. Find all these quotients.
You know you are done when you have found as many left factors as you have right factors.
Find those pairs of left and right factors $X,Y$ such that $X\cdot Y \subseteq L$. This is $\mathcal{F}_L$.

The Universal Automaton by Lombardy and Sakarovitch (in Texts in Logic and Games, Vol 2:  Logic and Automata: History and Perspectives, 2007)


What are differences between Static Scope and Dynamic Scope? My teacher has provided the following pseudo-code, and says that the output using static scope is 1 2 3, but the output using dynamic scope is 2 3 4.

void fun1(void);
void fun2(void);

int a = 1, b = 2, c = 3;

int main() {
    c = 4;
    fun1();
    return 0;
}

void fun1() {
    int a = 2, b = 3;
    fun2();
}

void fun2(){
    printf("%d %d %d", a, b, c);
}

Which variable we use in Static Scope? $c=3$ or $c=4$? (by Static Scope Rule and without considering C Rules).

In static scope the $fun2$ takes the globally scoped $c$ which comes from scope where function is defined (opposite to dynamic, where it traverses scopes of execution), so $c = 3$.
With dynamic scope traverses up the chain of scopes until it finds variable it needs, which reflects the fact that scopes are:
Global($a=1, b=2, c=3$) -> main($c=4$) -> fun1 ($a=2, b=3$) -> fun2.
fun2 in the way up finds $a=2, b=3$ in fun1 and $c=4$ in main.
By the way: C has static scope rules.


Machine learning algorithm for predicting binary decisions on a large, underrepresented dataset I would like create a classifier which works on a relatively large (about 30k samples) dataset with circa 20 attributes and a binary decision, however such, which contains relatively small amount of samples with, say, "Yes" decision. That is, the data for building a classifier seems underepresented.

My question is, are there any algorithms which work well with these kinds of datasets? So far I have tried C4.5 (J 48 actually), some basic SVM algorithms, Naive Bayes and MLP, hovewer each method failed to learn the dependencies in the data well (accuracy was at the level of about 90% and this underrepresented decision was... unrepresented by the classifier too). I'm using Weka if this makes any difference.

When you have many more "No" samples than "Yes" samples, this is known as the "class imbalance" problem.  Dealing with class imbalance is challenging: many machine learning algorithms don't work as well in this situation.

There are many techniques for dealing with class imbalance, including using class weights, oversampling the "No" samples, or undersampling the "Yes" samples.  I suggest doing a little bit of reading about techniques for dealing with class imbalance on Stats.SE, then trying them to see if they help.  Their effectiveness may depend on the data set and on which type of classifier you use.


Integer linear programming formulation of formula in DNF I have multiple sets, e.g.,

$$\{1, 2\}, \{2, 3, 4\}, \{1, 4\}$$

Each variable $1, 2, 3, 4$ is binary. I need to represent the following condition without additional variables

$$(1 \land 2) \lor (2 \land 3 \land 4) \lor (1 \land 4)$$

Basically, I need to enforce that either $1$ and $2$ are 1s, or $2$ and $3$ and $4$ are ones, or $1$ and $4$ are 1s, but not all of them. Constants can be added as needed, as well as equalities, inequalities, etc. How can I do that?

You are looking for a four-dimensional convex polytope that contains all of the points $(x_1,x_2,x_3,x_4)$ that satisfy your condition, and but not any point $(x_1,x_2,x_3,x_4)$ that doesn't satisfy your condition.  (That's because any system of linear inequalities forms a convex polytope.)

It's not quite clear to me from your question about what your condition is, so I'll try answering your question with both plausible interpretations I see.

Interpretation #1:

In the first possible interpretation, the boolean formula is $(x_1 \land x_2) \lor (x_2 \land x_3 \land x_4) \lor (x_1 \land x_4)$.  This means the polytope needs to contain all of the following seven points:

$$(0,1,1,1), (1,0,0,1), (1,0,1,1), (1,1,0,0), (1,1,0,1), (1,1,1,0), (1,1,1,1)$$

and not any of the other nine points where the formula is false.

There are various ways to check whether there exists such a polytope.  One way is to enumerate all possible inequalities $c_1 x_1 + c_2 x_2 + c_3 x_3 + c_4 x_4 + c_5 \ge 0$ and look for combinations $(c_1,\dots,c_5)$ such that this inequality is true for all of the seven points listed above.  Then, we check whether a system of constraints obtained by using all of those inequalities has the desired property (in particular, each of the other nine points violates at least one of these inequalities).  You can then minimize the set of constructed inequalities, to remove redundancies.

Here is one such system of constraints that works:

$$\begin{align*}
x_2+x_4-1 &\ge 0\\
x_1+x_3-1&\ge 0\\
x_1+x_2-x_3+x_4-1 &\ge 0
\end{align*}$$

Another way to have obtained this system of constraints would be to convert the DNF formula you listed to CNF, and then translate each "OR" constraint into a single inequality using the techniques from Express boolean logic operations in zero-one integer linear programming (ILP).  The formula $(x_1 \land x_2) \lor (x_2 \land x_3 \land x_4) \lor (x_1 \land x_4)$ is equivalent to $(x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_1 \lor x_4) \land (x_2 \lor x_4)$.  That then yields the following system of constraints, which also works:

$$\begin{align*}
x_1+x_2-1 &\ge 0\\
x_1+x_3-1 &\ge 0\\
x_1+x_4-1 &\ge 0\\
x_2+x_4-1 &\ge 0
\end{align*}$$

Interpretation #2:

In the second plausible interpretation, you want the boolean formula

$$(x_1 \land x_2 \land \neg x_3 \land \neg x_4) \lor (\neg x_1 \land x_2 \land x_3 \land x_4) \lor (x_1 \land \neg x_2 \land \neg x_3 \land x_4).$$

Thus, you want the polytope to contain only the three points

$$(1,1,0,0),(0,1,1,1),(1,0,0,1).$$

We can apply the same methods to get a system of inequalities for this formula.  Here is one solution that works:

$$\begin{align*}
-x_1-x_3+1 &\ge 0\\
-x_2+x_3-x_4+1 &\ge 0\\
x_2+x_4-1 &\ge 0\\
x_1+x_3-1 &\ge 0\\
x_1+x_2-x_3+x_4-1 &\ge 0
\end{align*}$$


Solving $T(n)=3T(\lfloor \frac{n}{3}\rfloor) +2n\log n$ I want to solve $$T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n,$$
with base case $T(n) = 1$ if $n \leq 1$.
I am sure that the Master Theorem does not work. I am trying a lot with the substitution method, but I am very frustrated since I can't find a solid expression. Does any one have a good "hint" or good idea on how to solve this in a nice way?

Ignoring floors (see, e.g., the paragraph "Ignoring Floors and Ceilings Is Okay, Honest" in Chapter 1 of Algorithms for a discussion), your recurrence is of the form
$$
T(n) = aT(n/b) + f(n),
$$
with $a=b=3$ and $f(n) = 2 n \log n$.
You can then immediately apply the master theorem since, for $k=1$, $f(n) \in \Theta(n^{\log_b a} \log^k n) = \Theta(n \log n)$.
The solution to the recurrence is then:
$$
T(n) \in \Theta(n^{\log_b a}  \log^{k+1} n) = \Theta(n \log^2 n).
$$


Lookahead in LL(k) parsing I'm having difficulty understanding what lookahead is $\mathrm{LL}(k)$ parsing. Does $k$ lookahead mean I consume $k$ symbols at a time and then process them?

Any help is appreciated.

No, you still consume one symbol at a time. However, you are allowed to consult the next $k$ symbols in order to decide what to do before consuming the symbol.

Here's a simple example: the grammar of context-free grammars. Informally, a CFG is a sequence of productions, where each production consists of a non-terminal, the derives symbol ($\to$) and a replacement list, which is a possibly-empty sequence of non-terminal and terminal. Formally, we have

$$\begin{align}
Grammar &\to \lambda \\
Grammar &\to Nonterminal \ Arrow \ Derivation \ Grammar \\
Derivation &\to \lambda \\
Derivation &\to Nonterminal \ Derivation \\
Derivation &\to Terminal \ Derivation \\
\end{align}$$

That's not an LL(1) grammar, because when $Derivation$ is on top of the stack and the next input symbol is $Nonterminal$, then there are two possible actions:

Predict $Derivation \to \lambda$, which means popping the $Derivation$ off the stack without consuming the input token.
Predict $Derivation \to Nonterminal Derivation$, which means popping the $Derivation$ off the stack and replacing it with $Derivation \  Nonterminal$; then matching the $Nonterminal$ from the input and the $Nonterminal$ on top of the stack, discarding both.

How can the parser decide which action to take? If it can only see one input symbol, then it has no way to decide. But if it can see 2 input symbols, then it can choose action 1 if the second next input symbol is $Arrow$ and action 2 in any other case.

So we can conclude that our grammar for grammars is LL(2).


find the missing number in a block of 3 numbers Given a contiguous sequence of numbers in which each number repeats thrice, there is exactly one missing number. Find the missing number.

eg: 11122333 : Missing number 2
11122233344455666 Missing number 5

I think we can't do better than just going from beginning to the end and checking the count if a specific number count is less than 3.

s = "11122233344455666"
count = 1
flag = 0
for i in range(0, len(s), 3):
    if i+2 < len(s) and s[i] != s[i + 2]:
        print s[i]
        break
    elif i+2 >= len(s):
        print s[i]
        break

Your current algorithm is linear in the size of your array $A$, which I'll call $n$. We can do a bit better, by observing the following: If some index $3i-1$ comes before the missing number, then $A[3i-1]=i$. Otherwise, $A[3i-1]=i+1$. (I start indexing at $0$)

So, we can do a binary search on $i$, as we always can see whether the index of the missing number is larger or smaller than $3i-1$. This gives an $O(\log n)$ algorithm, which is an improvement on your linear time algorithm.


NP-hard proof: Polynomial time reduction As I understand, to show that a certain problem $P$ is NP-hard we can reduce a known NP-hard problem $Q$ to a problem in $P$. This reduction, say $f$, has to be polynomial time.

Could someone please explain is it necessary that $f$  maps each instance of $q\in Q$ to $P$ or can we map a selected  subset of $\tilde Q \subseteq Q$ to $P$? i.e. does pre-image of $f$ has to be be all of $Q$ or can it be a subset of $Q$?

Thanks

Yes and no. To cut a long story short, it's enough that the pre-image of $f$ is NP-hard.

Intuitively, the point of NP-hardness is that, if you had an efficient algorithm for an NP-hard problem, then you would have an efficient algorithm for all problems in NP. Let's suppose you've come up with a new problem, Triomphe's Problem (TP), and you want to prove that it's NP-hard. You need to show that every problem in NP can be reduced to TP.  There are, on the face of it, two ways of doing this.

The direct way. Show that there is a polynomial-time computable function $f$ with the following property: for any nondeterministic polynomial-time Turing machine $M$ and every input $x$, $f(M,x)$ is an instance of TP and $f(M,x)$ is a "yes" instance of TP if, and only if, $M$ accepts $x$. This is how Cook proved NP-completeness of Boolean satisfiability and how Fagin proved NP-completeness of evaluation of formulas of existential second-order logic.

The indirect way. Show that there is an NP-hard problem $P$ and a polynomial-time computable function $f$ with the following property: for any instance $x$ of $P$, $f(x)$ is an instance of TP and it is a "yes" instance of TP if, and only if, $p$ is a "yes" instance of $P$. This is how just about every other NP-hard problem, apart from the two listed above, was proven NP-hard.

The indirect way works through a chain of reductions.  We need to establish that every problem in NP can be reduced to TP. So, we start with our nondeterministic polynomial-time Turing machine $M$ and its input $x$.  We convert that to an instance of Boolean satisfiability. Then we convert that into, say, an instance of 3-SAT. Then we convert that into, say, an instance of 3-colourability. Then maybe we convert that into an instance of $P$ and, finally, convert that into an instance of our fictional problem TP. Because all of these reductions work for every instance of the problem, we have a reduction from our generic NP problem to TP.

Both in theory and in practice, that is how reductions are done: you need to translate every instance of the problem. But we don't actually need that much. Look at the first step of the chain of reductions in the previous paragraph. We started with any Turing machine at all, and we converted it into a Boolean formula. Without looking closer, all we know is that we've produced some Boolean formula, and we don't know any details about it. However, looking more closely at the reduction, we see that the formula is in conjunctive normal form (CNF) (or that the proof can easily be modified to make it so). For the next step, converting to 3-CNF, the definition of reductions tells us that we have to be able to translate every Boolean formula into one in 3-CNF, but we know we don't need to do that much. It would suffice to translate only the formulas that are already in conjunctive normal form, because those are the only ones that the translation from Turing machines will produce. And that's actually what the standard proof does.

Normally, when a new problem is proven NP-hard, a full reduction is given from some known NP-hard problem to the new problem, which translates all instances. However, in principal, you could get away with a reduction that does less than that, as long as it covers enough instances to establish the chain back to the generic Turing machine $M$ and its input $x$. To give another example, 3-colourability is NP-hard because of a standard reduction from 3-SAT. You could prove a new problem to be NP-hard by a reduction that only translates the instances of 3-colourability that could be produced by that reduction from 3-SAT. This works because 3-colourability is already NP-hard when its input is restricted to be from the class of graphs that can arise from the reduction from 3-SAT.

However, if you're a student doing exercises and exam questions, I'd recommend that you always produce reductions that map the whole problem, rather than just a subset of it.


Does a greedy task selection algorithm find a c-approximate solution? I was told this question may be better suited here.

  A scheduling problem can be stated as: Given a set
  $\{(s_i,f_i)\}_{1\le i\le n}\}$ of tasks identified by their start and
  end times, choose the maximum size subset of non-overlapping tasks.
  Choosing tasks greedily by earliest finishing time gives an optimal
  solution, but what about heuristics: earliest starting time, shortest
  length, and fewest incompatibilities? Does each heuristic find a
  $c$-approximate solution, for some constant $c$?

How do you typically solve problems like this? How can we know whether a $c$-approximate solution is found (i.e. a subset of tasks whose size is at least 1/$c$ of the optimum)? I don't see how we can bound a heuristic, it seems like there are a lot of possibilities for the answers that it will return.

For example, in the earliest start time heuristic, we can always guarantee that it will select one task (the first one- with earliest start time), but it doesn't seem like we can guarantee anything more.

For the shortest length, it seems like we can get closer to the optimal solution, and to me it seems like we can always guarantee that if the optimal solution is $m$ tasks, shortest length will select $m-1$ tasks.

The shortest-task-first heuristic is a 1/2-approximation algorithm.

For a tight example, image that a compatible set $\{T_i\mid 1\leq i\leq m\}$ sorted by their finish time and the other shorter tasks $Y_i$, $1\leq i\leq m/2$, such that $Y_i$ overlaps with $T_{2i-1}$ and $T_{2i}$ for each $i$. The shortest-first heuristic finds $m/2$ tasks while the optimal solution contains $m$ tasks.

To show the approximation ratio:
For any compatible set $T$ sorted by their finish time, a task in the approximation solution overlaps with at most two tasks in $T$ since it cannot contain any task as a sub-interval of it. In fact, you can always obtain a 2-approximation if you select no tasks ``covering''  another task.


Why do the definitions of non-deterministic Turing machines look strange? I read some definitions of the NDTM in several books. Something makes me confused.

Some definitions say that the NDTM $M$ makes an arbitrary choice as to which of its transition functions to apply.

So, if $x \in L(M)$, then $M$ can always guess a branch which leads to $q_{accept}$. And if $x \not\in L(M)$, then $M$ just chooses an arbitrary branch until it enters $q_{reject}$. It seems that $M$ knows the result after reading $x$ because the rule which tells $M$ how to guess depends on whether $x$ is in $L(M)$.

It looks so strange!

Another definitions say that $M$ executes all branches in parallel.

That looks better. And it shows that if $x \in L(M)$, then $M$ halts when it enters $q_{accept}$ at the first time. However, the running time of NDTM is defined as the maximum number of steps that $M$ uses on any branch of its computation on any input. I am not sure if the definitions of the running time of NDTM are equivalent.

Basically, a NDTM on input $x$ may have more than one computation branches. If at least one of these branches accepts the input then we say the NDTM accepts the input $x$, otherwise it rejects.

You can consider a NDTM as a finite number computation branches such that branch on input$x$ may halt with accept or reject, or run forever. If at least one branch halts with accept then the NDTM accepts that input no matter other branches halts or run forever. If no branch accepts (halts with in ACCEPT state) then we say the NDTM does not accept the input. And if every branch halts and rejects then we say that NDTM rejects the input.

Do not try look for a real life model of a NDTM. It is just a conceptual computation model which allows to define a complexity class known as $\mathrm{\mathbf{NP}}$ class.

This post has more.


Finding the shortest sublist that contains all search terms I've been trying to get better at writing algorithms and came across a problem that was something like this:

Given a list of words:

search_list = ["this", "is", "an", "issue"]

Find the closest occurrences of all of these words in another list, and return the first occurrence and last occurrence:

given_list = ["this", "tv", "is", "an", "state", "node", "is", "this", "issue", "issue", "an"]

Given these two lists, the correct result would be [6, 10], because the closest occurrences of the search_list, would start with the "is" at index 6, and finish with "an", at index 10.

Having said that, here are more details:

closest occurrences - definition

closest occurrence is the smallest subset of given_list in which all of the words occur. By "smallest subset", I simply mean the smallest absolute difference between the smallest occurring index, and the largest occurring index.

allowed inputs

1) search_list - a list or set of words that will only contain unique words. Again, no repeating words will be in this input parameter. This is the set of words that will be used to search given_list to find the shortest/closest subset or occurrences of.
2) given_list - a list or array of words that may contain duplicate words. This is the list that we need to find the smallest/closest subset of search_list in.

expected output

Find the closest occurrences of all of these words in another list, and return the first occurrence and last occurrence.

Here is what I've tried so far: To start, I thought it'd be helpful to find all of the occurrences of each word.

def find_sub_list(search_list, given_list):
    result_list = []
    for value in search_list:
        inner_list = [i for i, val in enumerate(given_list) if val == value]
        result_list.append(inner_list)
    return result_list

Given the variables above, this would result in:

[[0, 7], [2, 6], [3, 10], [8, 9]]

From these results, the correct answer would be [6, 10], because 4 is the shortest distance in which the words occur. However, I can't seem to find a better way to find the closest occurrences without checking every possible outcome. Is there a particular data structure that would make this process faster?

Edit

To further define "closest occurrences", I'll give an example.

search_list = ["one", "two", "three"]
given_list = ["one", "black", "two", "blue", "three", "green", "two", "three"]

The correct answer in this case would be [0, 4]. "two" and "three" occur at indices 6 and 7. However, "one" occurs at index 0, and "two" and "three"'s also occurs at 2 and 4. This subset with indices 0, 2, 4 is a smaller or closer subset than that of 0, 6, 7. Hopefully that makes more sense?

Other notes:

search_list cannot have repeating words. Items must be unique.

Go over the list, and maintain the last occurrence of each word in the search list. Whenever you find a word in the search list, find the minimum last occurrence among all other words in the search list - this gives you a candidate closest occurrence, which you take note of if it's the best seen so far. In the end, return the best closest occurrence observed.

To execute this algorithm efficiently, you need an efficient array-like data structure which supports the following operations:

Change the value of item $i$.
Return the minimum value of all items other than item $i$.

When the search list is very short, you can just use an array. For large search lists, you can probably use a modified heap to support all of these operations in $O(\log m)$ time, where $m$ is the size of the search list. The end result is an $O(n\log m)$ algorithm, where $n$ is the size of the main list.


Proving that PP is closed under symmetric difference I want to prove that PP is under symmertic difference.
let A be a language in PP and B likewise.
I tried showing that : (A\B) U (B\A) in PP , so by show each in PP and then showing that it's closed under union , I should be done.
How do I show A\B in PP?
Am I on the right track? Maybe there is an easier way?

As stated in the Wikipedia article about PP, a proof that PP is closed under symmetric difference was a PhD thesis by David Russo Structural properties of complexity classes. Proving that PP is closed under union was also open for a long time until it was answered by R. Beigel, N. Reingold, and D. A. Spielman, "PP is closed under intersection", Proceedings of ACM Symposium on Theory of Computing 1991


Finding a match in two collections Let $A$ and $B$ be two one-dimensional, finite collections of unsigned integers (e.g. arrays). Furthermore, $card(A) = a < b = card(B)$. Both collections are sorted in ascending order. There is at least one item ${x}$ which is contained both in $A$ and $B$.

Question: what is the fastest algorithm to find the smallest $x$ and what is its $T(n)$ in Big O notation?

Note: card() means the size of array (say: card(A) = 10 means a declaration in C/C++ would be int[10] A with indices 0...9).

Note 2: as I am new to CS.SE and learn CS as enthusiast, so far I have not been exposed to any fancy algorithm to solve this. My initial (naive) guess would be brute-search approach, but this is obviously not efficient for large $A$ and $B$. Your thoughts and pieces of advice would be then highly appreciated.

The priority is practical efficiency, so something around polynomial time-algorithm would be nice. Note, that the number of elements in both collections will be very substantial (above 10^30).

Some ideas for a special case.

If all the elements have a limited range N (all the elements in A and B are bigger than zero and smaller than N), then you can accomplish this task by O(N*log(|A| + |B|)) as following:

for i <- 0, 1, ..., N:
    binary search in A to see whether i is in A
    binary search in A to see whether i is in B
    if i is both in A and B then
        x <- i
        break

This solution will be practically efficient if the N is not so big (for example 10^7) then it will solve the problem even when |A| and |B| are as large as 10^30 (though it is not practical to store them in any place).

The calculation: $N*\log{(|A| + |B|)} = 10^7 * \log{(2*10^{30})} \approx 3*10^8$

Besides, I do not think you can find a practically efficient algorithm for general case for card(A) and card(B) as much as 10^30. The general algorithm, in my opinion, is at least O(|A|+|B|) as following:

ia <- 0
ib <- 0
while A[ia] != B[ib] do
    if A[ia] > B[ib] then
        ib <- ib + 1
    else
        ia <- ia + 1
x <- A[ia]


Relation/use of irrational or transcedental numbers in computer science? I'm wodering about the relationship between the theory that studies irrational/transcendental numbers and computer science. For example, I found this paper (but was unable to get the full text)
Pseudo-random number generator based on irrational numbers

I found the paper because I started looking for a RNG that uses the property that irrational/transc. numbers don't have repeating decimals.
I wanted to know in what other ways we can use or have a motivation to study irrational/transcendental numbers, because of their use in CS.

I'm ignorant on the matter, so I appreciate if someone more knowledgeable can provide examples when the two subjects connect themselves. Like the paper above.

On the surface that does not strike me as a high-quality paper.  I wouldn't recommend it.

I don't think irrational/transcendental numbers are a good approach to building PRNGs.  Building PRNGs is tricky business.  There are standard PRNGs; I suggest using one of them, rather than trying to invent your own.  They all ensure that the output is extremely unlikely to repeat within any reasonable time period.

There is no one theory of irrational/transcendental numbers, and not just one connection to CS; irrational numbers show up in a variety of areas of CS.  It's not feasible to give you a complete list; such a list would be far too long.  If you just want one example, you might read about the Fibonacci numbers and their connection to the golden ratio (which is an irrational number).


Conditional RB Tree union Input: 2 RB Trees A B, so that both values in a certain range, so that B's range is smaller than A in both sides.  Ex. B's range can be [100...200] and A's range is [0...1000]
Output: Unite A and B to one RB Tree AB.

How can I unite these 2 trees in $O(log(n))$ time and with additional space $O(1)$?

I have tried splitting tree A into 3 trees A1,A2,A3, so that:   A1 < A2 , B < A3
A2 contains all that values that are equal-bigger than Min(B) and smaller-equal to Max(B).
I did it using the RB Tree Split algorithm, and all the splitting sums up to $O(log(n))$ time.

Now I know what to do with A1 and A3 but what should I do with A2 and B?  I know I should use the fact that B contains A2's range but how does it help me?

You can't. As shown by Brown and Tarjan on the first page of "A Fast Merging Algorithm", merging two sequences with overlapping ranges has a worst-case bound of $\Theta (m \lg (n/m))$ comparisons.


Dependency Graph - Acyclic graph I have a directed acyclic graph where edge (A,B) means that vertex A depends on vertex B.

Vertex deletions have the following restrictions:

When vertex B is removed, all dependent vertexes should also be removed.
When vertex  A is removed and vertex A was the only vertex that depends on B, vertex B should also be removed.

I need to list the vertixes which are deleted when

Vertex B is deleted. My solution is B, E and J because

B -- deleted
E -- because of condition 2, B is removed and B was the only vertex that depends on E
J -- because of condition 2

Vertex C is deleted. My solution is C, F, A, G, ... ?

C -- deleted
F -- because of condition 2 (C is the only vertex to F)
A -- condition 1 (depends on C)
G -- condition 2 (C is the only vertex to G)
I think here the process goes on and cascades. Is that correct?

What could be an algorithm for such vertexes dependency network which allows for the vertex deletion?

PS: this is an old exam exercise (2008/09); I use it as exercise for my one middle of June.

The deletion process has two phases, one for each condition.

Delete the specified node and all nodes that have a directed path to it.
Delete all nodes that have no incoming edges anymore and are no sources (iterate).

There are two imporant observations that make this correct:

During phase two, we create no new nodes with dangling outgoing edges, that is we do not break more dependencies that would cause nodes to be removed by condition 1.
Phase two is a fixed-point iteration.

How you would implement this depends on your graph representation. For example, if graphs have a node list, a list of sources and every node has lists of incident nodes via incoming (pred) and outgoing (succ) edges, respectively, you can do it like this:

  void removeFancy(g : Graph, n : Node) {
    rem = collectReverse(g,n)
    g.removeAll(rem)
    removeRedundant(g)
  }

  Node[] collectReverse(g : Graph, n : Node) {
    result = [n]
    foreach ( n' in n.pred ) {
      result ++= collectReverse(g,n')
    }
    return result
  }

  removeRedundant(g : Graph) {
    oldSize = 0
    while ( oldSize != g.size ) {
      oldSize = g.size
      for ( n in g.nodes ) {
        if ( n.pred.empty? && !g.sources.contains(n) ) {
          g.remove(n)
        }
      }
    }
  }

You can also do it in a more recursive fashion:

  void removeFancy(g : Graph, n : Node) {
    for ( n' in n.pred ) {
      removeFancy(g, n')
    }

    succ = n.succ.copy
    g.remove(n)

    for ( n' in succ ) {
      if ( n'.pred.size == 0 ) {
        removeFancy(g, n')
      }
    }
  }

Here it is more challenging to see correctness because the two phases are interleaved. The essential argument is that nodes deleted in the second loop never cause new dependency breaks, therefore all nodes that have to be deleted because of condition 2 are identified thus by recursion spanned by the calls in the first loop.

If you apply any of those to your second example, you will see that in addition C, F, A and G also D will be deleted, but no other nodes.


Explaining regular expressions folks. My question is about explaining the each step of regular expressions. The task is to find the regular expression that contains 101 as a substring. I already know that the regular expression for this is

$$ (0 + 1)^*101(0 + 1)^*. $$

The question is that how we should show each step for explaining the regular expressions.

You have to show two things:

Every word in the language of your regular expression contains 101 as a substring.
Every word containing 101 as a substring belongs to the language of your regular expression.

You can prove both of these using the definition of the language of a regular expression. It is a bit tiring but otherwise requires little creativity.


Solving for the minimum cost, colored, set cover Formulation
This problem has four entities:

A universe: $U = \{1, 2, ..., n\} $ of $n$ elements, indexed with $u$
A set of available colors: $C \in \{1, 2, ..., m\} $ with $m$ colors, indexed with $c$
A collection of sets: $S = \{s_1, s_2, ..., s_k\}$ where there are $k$ sets, indexed with $i$. These sets contain elements of the Universe. $\bigcup S = U$.
A cost function: $cost(u, c)$ where $u$ is the element, $1 \le u \le n$, and $c$ is the color of that element $1 \le c \le m$

We must assign a single color to each element such that the overall cost of the color assignment is minimized AND such that a valid set cover exists such that all elements in each set of the set cover have the same color. That is:
$$min \sum\limits_u cost(u, c) x_{u,c}$$
subject to

$0 \le x \le 1$. That is, $x_{u,c}$ is a binary decision variable which indicates that a particular element ($u$) is a particular color ($c$).
$\sum \limits_c x_{u,c} = 1 \quad \forall u \in U$. That is, an element may only have one color.
$\sum \limits_{s:u\in S} y_s \ge 1 \quad \forall u \in U$. That is, every element must be in the set cover.
$0 \le y \le 1$. That is, $y_{s}$ is a binary decision variable which indicates that a particular set ($s$) is included in the set cover.
$ x_{s_{i_1},c} = x_{s_{i_2}, c} = ... = x_{s_{i_l},c} \quad \forall s_i \in S \bigm| y_s = 1$. That is, given that a set is included in the set cover, everything in that set must be the same color.

Example
$U = \{1, 2, 3, 4, 5, 6, 7, 8\}$
$C = \{r, g\}$
$S = \{\{1, 2\}, \{1, 2, 3\}, \{2, 3, 4\}, \{3, 4, 5\}, \{4, 5, 6\}, \{5, 6, 7\}, \{6, 7, 8\}, \{7, 8\}\}$
$cost_{r} = \{0, 0, 2, 1, 2, 1, 1, 0\}$
$cost_{g} = \{1, 0, 1, 2, 0, 0, 0, 3\}$
Optimal solution:
$= \{r, r, g, g, g, g, r, r\}, \quad cost=4$
That is, the set cover is $\{\{1, 2\}, \{3, 4, 5\}, \{4, 5, 6\}, \{7, 8\}\}$.
Typically, $U$ consists of 100-2000 elements, $C$ consists of 3 - 10 colors, $S$ consists of 200-4000 sets of 5-25 elements.
Context
Perhaps one way to think about this, is that you have a paint brush of a certain size that is larger than an element - that is it can only paint a collection of elements in one stroke. The allowed places to 'stroke' are overlapping - they are the sets in S. When you paint a particular set a particular color there is a cost associated with it that you would like to minimize. When you paint an area, you can paint the overlapping areas the same color only paying for the 'difference' in cost (kinda).
Questions

Is the formulation above well formed, and understandable? Is there a better formulation more related to an already existing problem?
Can this be expressed as an integer linear programming problem?
How would you solve this problem?

I have constructed an algorithm to solve this problem that first tries to use branch and bound to construct the optimal solution - it does quite well, but as the problem gets larger it slows down. If it starts to take too long I stop the branch and bound and use a random search to improve a solution. I think that having a better mathematical understanding of the problem will help me solve it better - I would also like to prove that this is NP-Hard.
One idea I have toyed with is to construct a new collection of sets $S'$ which consists not only of all the original sets but all of their combinations / unions (I understand this will be a lot, $2^k - 1$ right, but for at least proving the complexity of the problem it should be ok..) and then duplicating those sets once for each color, and then solving for the weighted exact set cover. Does that 'reduction' prove that this is NP-Hard? Is that even a reduction?
I've also thought about thinking about the problem the other way around, that is thinking about it in terms of the sets being assigned a certain color - but then I don't know exactly how to account for the overlapping of the sets in the minimization, also there will be some sets that do not have a single color so long as the sets that do have a single cover form a covering of the universe.
Thanks in advance.

Unfortunately this is NP-hard (even if we use only the costs 0 and 1), so it's very unlikely that there exists a polynomial-time algorithm that will solve every instance.  I'll show this by reducing the NP-hard problem Exact Cover to your problem.  I'll work with the decision variant of your problem, in which we are given a number $q$ in addition to $U$, $C$, $S$ and $cost()$, and the task is to report whether or not there is a solution with cost at most $q$.  (With an algorithm that answers the decision problem, minimisation/maximisation can then be accomplished efficiently with binary search, and an actual solution realising that optimal solution size can also be recovered without too much extra difficulty.)

Recall that in the Exact Cover problem, we are given a collection $A = \{a_1, \dots, a_r\}$ of sets, each of which is a subset of some ground set $B$, and our task is to report whether or not it is possible to choose a subset $X \subseteq A$ of sets in $A$ such that every element in $B$ belongs to exactly one set in $X$.  To encode an instance of the Exact Cover problem as an instance of your problem:

For each set $a_i$ in $A$:

Add the set $a_i$ to $S$, as $s_i$.
Add a new colour $c_i$ to $C$.
Set $cost(b_j, c_i) = 0$ for every $b_j \in a_i$.
Set $cost(b_j, c_i) = 1$ for every $b_j \notin a_i$.

Set $U = \cup_{s_i \in S}s_i$ as usual.
Set $q = 0$.

Basically, we create a colour $c_i$ for each set $a_i$ in $A$, and set the costs of that colour so that ground elements from the corresponding set ($a_i$) get no cost, while every other ground element gets a positive cost.  This means that whenever there does exist an exact cover for $A$, it is possible to create a zero-cost solution to the corresponding constructed instance of your problem: just assign every ground-set element the colour corresponding to the unique set that contains it.  Thus, a "YES" answer to the Exact Cover problem implies a "YES" answer to the constructed instance of your problem.

In the other direction, we would like to show that a "YES" answer to the constructed instance of your problem implies a "YES" instance to the original Exact Cover problem instance.  So, we start by assuming a "YES" answer to the constructed instance of your problem.  This means that there exists a zero-cost assignment of colours to ground-set elements that could be produced by choosing a set cover from $S$, then choosing a colour for each set in the cover, and assigning that colour to all ground-set elements belonging to that set.  We can represent such a solution as a pair $(X, f)$, where $X \subseteq S$ is the set of ground-element sets chosen for the cover, and $f : X \to C$ is a function that maps a set in $X$ to a colour in $C$.  (Even though it is individual ground-set elements that we colour and not sets of them, $f$ is still well-defined for a feasible solution, since we require of every set $x \in X$ that every $e \in x$ is assigned the same colour.)

In order to easily build a solution to the original Exact Cover instance from $(X, f)$, we want the ground-set elements having some particular colour to be exactly the ground-set elements in some set in $A$: then we can simply go through each colour present in the solution to the your problem (i.e., in the range of $f$) and include the corresponding set from $A$ in the Exact Cover solution.  So in other words, we would like to have a solution $(X, f)$ that has $f(x_i) = c_i$ for each $x_i \in X$.  But this is complicated by the fact that $X$ could contain sets that overlap, which is of course forbidden in an Exact Cover solution.  Between any pair $x \in X, x' \in X$ there are two kinds of potential overlap: containment (either $x \subset x'$ or vice versa), and "proper overlapping", where $x \cap x' \neq \emptyset$ but neither set contains the other.

To address the problem of containment, it is easy to see that, whenever there exists a solution $(X, f)$ that contains a pair of sets $x \in X$ and $x' \in X$, one of which contains the other, then there also exists another solution $(X', f')$ with the same cost and in which the smaller of the two sets has been removed.  (If $x = x'$, then just remove either one arbitrarily.)  Iterating this process until we cannot apply it any more ensures that there must exist a solution $(X'', f'')$ in which no set in $X''$ contains any other set in $X''$.  (Note that all we care about is the fact that such a solution must exist; for the purposes of answering the YES/NO question about the original Exact Cover instance, we don't need to know a specific solution.)

This leaves the problem of "properly overlapping" sets.  I'll now show that these cannot occur in any zero-cost solution to your problem.

Suppose towards contradiction that there is some chosen set $x_i \in X''$ such that $f(x_i) \neq c_i$.  Then $f(x_i) = c_j$ for some $j \neq i$, with $x_j \in X''$ also.  But because there is no other set in $X''$ that contains $x_i$ as a subset, there must be at least one ground-set element $b \in x_i$ that is not also in $x_j$.  Thus assigning $b$ the colour $x_j$ incurs a cost of 1, which cannot be recouped via any other means.  Since we know that $(X'', f'')$ has a cost of 0, this is a contradiction.  Thus it follows that if there exists a zero-cost solution $(X, f)$ to the constructed instance of your problem, then there must also exist a zero-cost solution $(X'', f'')$ to it in which no chosen set contains any other chosen set and in which no set properly overlaps any other set.  $X''$ is, thus, an exact cover -- so the answer to the Exact Cover instance must also be "YES".

We have established that a "YES" answer to the constructed instance of your problem implies a "YES" answer to the original Exact Cover instance, and vice versa.  This implies that a "NO" answer to either instance implies a "NO" answer to the other, which in turn implies that the two problems are equivalent.  Since the construction of instance of your problem took only polynomial time and space, an algorithm that solves your problem in polynomial time could also be used to solve Exact Cover in polynomial time.  Since Exact Cover is NP-hard, it follows that your problem must be NP-hard too.


Why do OS and DBMS have their own synchronisation mechanisms, when OS can alone do it and it sits at the bottom of DB? I know that synchronization is important in the OS, but why do we need a separate topic synchronization and concurrency in the DBMS? The OS concentrates on program synchronization while the DBMS concentrates on data synchronization. Why can't the OS take responsibility for data synchronization?

Program synchronization is a very different beast compared to transaction synchronization. The objective of your Operating System is to have multiple applications working in sync to maximize the utilization of your CPU. A couple of reasons I can think of as to why OS' are not equipped to handle transaction synchronization are as follows.

Your DBMS is a self contained application. Allowing a 3rd party software (i.e. your OS which may be open source or owned by some corporation) direct access to the data is a no-go for business.
There maybe multiple DBMS' with different architectures (relational, non-relational, written in different languages, using different standards) installed on a single Operating System. OS designers usually ignore deadlock recovery because it becomes too complicated for them to handle efficiently. Accounting for applications across the board will mean worse performance issues for the OS, ultimately defeating the purpose of having one in the first place.


Understanding proof of upper bound on complexity of recursive computation of graph chromatic polynomial This question is about section 2.3 of Wilf's ``Algorithms and Complexity''

https://www.math.upenn.edu/~wilf/AlgoComp.pdf

in which he analyses the complexity of a recursive computation of the chromatic polynomial of a graph, based on the relation
\begin{equation}
\label{eq: recurrence}
P(K;G)=P(K;G-\{e\})-P(K;G/\{e\}) \qquad (1).
\end{equation}
Here $P(K;G)$ is the number of ``proper colourings'' of $G$ with (as I understand it) at most $K$ colours (that is, colourings of the vertices using at most $K$ colours, such that no adjacent pair of vertices shares the same colour). The graph $G-\{e\}$ is the result of deleting edge $e$ from graph $G$, and the graph $G/\{e\}$ is the result of contracting edge $e$ in graph $G$. It turns out that $P(K;G)$ is indeed a polynomial in $K$, of degree equal to the number of vertices of $G$.

By defining $F(V,E)$ as the maximum cost (over all such graphs) of applying to a graph $G$ with at most $V$ vertices and at most $E$ edges, this recursive algorithm to compute $P(K;G)$, Wilf deduces from (1) that
\begin{equation}
\label{eq: F recurrence}
F(V,E) \leq F(V,E-1)+cE+F(V-1,E-1) \qquad (2),
\end{equation}
with $F(V,0)=0$. Here the term $cE$ accounts for the effort of contracting the edge $e$, which requires us to modify the descriptions of any edges adjacent to the vertex that gets deleted.

Wilf seeks an upper bound of the form $F(V,E)\leq f(E)c$, and notes that the unique $f$ satisfying $f(E)=2f(E-1)+E$ and $f(0)=0$ will provide such a bound. He computes the exact solution $f$ of this last recurrence relation, which solution he approximates by $f(E)\sim2^{E+1}$.

He then derives another upper bound on $F$, by defining $\gamma(G)=|V(G)|+|E(G)|$, the sum of the number of vertices and the number of edges of $G$, and observing that $\gamma(G-\{e\})=\gamma(G)-1$ and $\gamma(G/\{e\})\leq \gamma(G)-2$. Then, letting $h(\gamma)$ denote the maximum amount of work done by the algorithm on any graph $G$ for which $\gamma(G)\leq \gamma$, Wilf claims that
\begin{equation}
\label{eq: h recurrence}
h(\gamma)\leq h(\gamma-1)+h(\gamma-2) \qquad (3)
\end{equation}
for $\gamma \geq 2$.
With $h(0)=h(1)=1$, the solution of this last recurrent inequality is that $h(\gamma) \leq F_{\gamma}$, the Fibonacci number.

Finally, combining the two bounds, he obtains that the time complexity of the algorithm is
\begin{equation}
O \left ( \min(2^{|E(G)|}, \phi^{|V(G)|+|E(G)|}) \right ),
\end{equation}
where $\phi$ is the golden ratio. Provided the ratio of $|E(G)|$ to $|V(G)|$ is large enough, the second bound is sharper than the first.

My question is, how in (3) was Wilf able to omit a term like $cE$ from (2) ?

You are correct that a term was omitted in the RHS of (2.3.10), but the final asymptotic bound $O(\phi^n)$ holds for the augmented RHS also. Perhaps it might be easier for you to see this if you just work out the solution for the nonhomogeneous recurrence relation from scratch rather than use Wilf's Theorem 1.4.1 on the epsilons, as shown below.  Essentially, we are  adding a linear term $an+b$ to the exponential $\phi^n$, which gives $\phi^n + an+b = O(\phi^n)$, where $\phi$ is the golden ratio.

More specifically, suppose that before the two recursive function calls to the chrompoly function, the edge set needs to be modified, and for the given value of $\gamma = |V|+|E|$, the cost for modifying the edge set is $\gamma$.  (You can also take this cost to be $c \gamma$ for some other $c$, if you wish.)

Then, the recurrence $h(n) = h(n-1)+h(n-2)+n$ needs to be solved.  From the theory of linear nonhomogeneous recurrence relations, the solution $h(n)$ is the sum of a generation solution and a particular solution, where (1) the general solution has the form $h_1(n) = c_1 \alpha^n + c_2 \beta^n$, where $\alpha , \beta$ are roots of the characteristic equation (one of them containing the golden ratio), and (2) the particular solution has the form $h_2(n) = an+b$ because the nonhomogeneous part is polynomial of degree $1$. (If the nonhomogeneous part was $7n^2 3^n$, then the particular solution would take the form $(an^2+bn+c)3^n$. If $3$ was a single root of the characteristic equation, then the particular solution would take the form $n(an^2+bn+c)3^n$. If $3$ appeared as a root with multiplicity $m$, then the extra factor would be $n^m$.)

Thus, $h(n) = O(c \phi^n +an+b) = O(\phi^n)$ because the linear terms grow more slowly than the exponential and can be ignored in asymptotic notation.


Are interrupts needed for a computer system to work? Are interrupts needed for a computer system to work? Could you have a computer system
(hardware and software, including the OS) that worked without an interrupt mechanism?

No, they're not needed for a computer to work.  For instance, you can use polling to interact with devices, instead of interrupts, and you can use cooperative multitasking for scheduling multiple processes, rather than preemptive multitasking.

(Thank you, @Paul A. Clayton!)


How to calcualte the Big-O complexity of the following algorithm? I have been trying to calculate the Big-O of the following algorithm and it is coming out to be O(n^5) for me. I don't know what the correct answer is but most of my colleagues are getting O(n^3).
for(i=1;i<=n;i++)
{
    for(j=1 ; j <= i*i ; j++)
    {
        for(k=1 ; k<= n/2 ; k++)
        {
        x = y + z;
        }
     }
}

What I did was start from the innermost loop. So I calculated that the innermost loop will run n/2 times, then I went to the second nested for loop which will run i^2 times and from the outermost loop will run i times as i varies from 1 to n. This would mean that the second nested for loop will run a total of Sigma(i^2) from i=1 to i=n so a total of n*(n+1)*(2n+1)/6 times. So the total amount that the code would run came out to be in the order of n^5 so I concluded that the order must be O(n^5). Is there something wrong with this approach and the answer that I calculated?
I have just started with DSA and this was my first assignment so apologies for any basic mistakes that I might have made.

for(i=1;i<=n;i++)
{
    for(j=1 ; j <= i*i ; j++)
    {
        for(k=1 ; k<= n/2 ; k++)
        {
        x = y + z;
        }
     }
}

The triple-nested loop is equivalent to the summation
$$\sum_{i=1}^{n}\sum_{j=1}^{i^2} \sum_{k=1}^{n/2} 1$$
$$=\frac{n}{2}(\sum_{i=1}^{n}\sum_{j=1}^{i^2}1)$$
$$=\frac{n}{2}(\sum_{i=1}^{n}i^2)$$
$$=\frac{n}{2} \cdot (\frac{1}{6}n(n+1)(2n+1))$$
$$=O(n^4)$$

In terms of actual code efficiency, since x=y+z is invariant in the loop, any good optimizing compiler will extract the statement out of the loop (in compiler-speak, hoist the statement to loop preheader), hence making the compiled code run in $O(1)$.


Transmission (Store and Forward) Delay The Kurose & Ross book uses "store-and-forward delay" as a synonym for the transmission delay of a packet over a network link.

As a newcomer to computer networks, it isn't immediately obvious to me how these two terms are synonymous. My current understanding is that if not for the store-and-forward behavior of packet switches, the transmission delay of a link would be negligible as it would be pipelined with the propagation delay of the previous link; i.e. as the bits propagate across Link A, they are transmitted and stream into Link B. However, due to store-and-forward, no bits are transmitted onto Link B before all the bits have crossed Link A, and hence, we need to add the transmission delay of Link B.

Is this correct?

I haven't read that book, so I may be off the mark.

Usually the transmission delay on a direct link is negligible compared with the processing delay at the endpoints and at each hop. In concrete scenarios, going via a geosynchronous satellite is the only way you have significant transmission delays on a link (about 0.2s to go up and down).

So when you have a network link that consists of a chain of direct links with a router at each hop, the total transmission delay is the sum of the store-and-forward delays on the routers. Strictly speaking, it's that plus the total length of the link divided by the speed of light (if the signal propagates at light speed), but that second part is usually negligible.


Compare phase and magnitude spectrum results of 2 Images I have read that from Fourier transform we obtain magnitude and phase spectrum. The magnitude spectrum tells you how strong are the harmonics in a image and the phase spectrum tells where this harmonic lies in space.

I have used Matlab to compute the magnitude and phase spectrum of the 2 grayscale images of babies using fftn function, but the all spectrum are difficult to understand.

Can anyone please explain the features given in 1st paragraph by comparing the spectrums of both images of babies?

1.phase spectrum

and

2.magnitude spectrum

(If you have results other than in Matlab, explaining with your method is also okay)

image1=imread('D:\baby1.jpg');%Read colour image
image1=rgb2gray(image1);%covert colour image into Gray scale

image2=imread('D:\baby2.jpg');%Read colour image
image2=rgb2gray(image2);%covert colour image into Gray scale

figure,
subplot(1,3,1);
imshow(image1);
title('Gray scale Image of Baby1');

%Apply Fourier transform on Gray scale image
fft1=fftn(image1);
fft1=log(1+fftshift(fft1));%Use log function for scaling

%Find the magnitude spectrum
magnitude1=abs(fft1);
subplot(1,3,2);
imshow(magnitude1,[]);
title('Amplitude Spectrum 1');

%Find the phase spectrum
phase1=angle(fft1);
subplot(1,3,3);
imshow(phase1,[]);
title('Phase Spectrum 1');

figure,
subplot(1,3,1);
imshow(image2);
title('Gray scale Image of Baby2');

%Apply Fourier transform on Gray scale image
fft2=fftn(image2);
fft2=log(1+fftshift(fft2));%Use log function for scaling

%Find the magnitude spectrum
magnitude2=abs(fft2);
subplot(1,3,2);
imshow(magnitude2,[]);
title('Amplitude Spectrum 2');

%Find the phase spectrum
phase2=angle(fft2);
subplot(1,3,3);
imshow(phase2,[]);
title('Phase Spectrum 2');

The images are mostly noise with a recognizable cross in the middle, that means that there is nothing in the image that repeats. The first image however shows some patterns (circles), not just the cross, those are probable the wall on the top-left which has some repeating pattern on it.


Need clarification about the use of Big-O to describe matrix sparsity In one of my courses, Big-O notation was used for defining what a sparse matrix is, under the context of qualifying for suitability for a particular set of linear algebra algorithms. I looked around on the net, and only found more such uses that I have an issue with.

To say a matrix is sparse if it has O(n) non-zero elements, for example, is illogical. The sentence doesn't even parse right? When we talk about Big-O, we are talking about functions. So it would make sense to say for example, as a way to describe a property of a set of matrices, maybe produced by a function that builds or bounds particular types of matrices, parameterized by the dimensions. In this case however, it really would not say anything about a particular matrix in the set in terms of sparsity. For example, in such a O(n) set, every matrix of size less than 1 trillion^2 could have no non-zero elements.

I have the same logical problem with qualifications for graphs sparsity.

But I cannot seam to find any precise explanation for why Big-O is used in such ways, or whether it is used the correct way or is an abuse of notation.

What you have encountered is a very common convention. The sparsity assumption is probably in some algorithmic context: given a sparse matrix, here is an efficient algorithm that solves some problem. For example:

  Given a matrix with $O(n)$ non-zero elements, there is an algorithm to do X in $O(n^2)$.

What this really means is:

  For every $C > 0$ there is an algorithm that, given a matrix with at most $Cn$ non-zero elements, does X in $O(n^2)$.

The constant hidden inside the big O depends on $C$.

A similar convention explains the following sentence:

  There is a function $f\colon \{0,1\}^n \to \{0,1\}$ whose maximal influence is $O(\log n/n)$.

(The meaning of maximal influence is not important here.) What this really means is:

  There is a sequence of functions $f_1,f_2,\ldots$ such that $f_n\colon \{0,1\}^n \to \{0,1\}$ and the maximal influence of $f_n$ is $O(\log n/n)$.

Once you get used to this convention, all these seemingly meaningless sentences will acquire their full meaning.


Are there complete problems for P and NP under other kinds of reductions? I know that the complexity class $\mathsf{P}$ has complete problems w.r.t. $\mathsf{NC}$ and $\mathsf{L}$ reductions.

Are these two classes the only possible classes of reductions under which $\mathsf{P}$ has complete problems?

Also, what classes of reduction can be used for $\mathsf{NP}$ beside polynomial-time reductions?

Your questions contain a few incorrect or unclear phrases.  Neither “complexity class X has Y reduction” nor “we can use Y reduction for complexity class X” makes sense.  In addition, there are at least two definitions known under the name “polynomial-time reductions,” both of which are used to study NP-completeness: polynomial-time many-one reductions and polynomial-time Turing reductions.  But in this answer, I will ignore the difference between many-one reductions and Turing reductions, and I will focus only on the resource restrictions of reductions, because otherwise the answer will become too long and unfocused.

Now I will restate what you might want to ask, and answer them.

Are there any definitions of reductions with respect to which NP-completeness can be defined, other than polynomial-time reductions?  Are there any definitions of reductions with respect to which P-completeness can be defined, other than NC reductions and log-space reductions?

As Artem and Raphael said, you can define whatever you like.

Are there any definitions of reductions actually used to study NP-completeness in the literature, other than polynomial-time reductions?  Are there any definitions of reductions actually used to study P-completeness in the literature, other than NC reductions and log-space reductions?

Yes.  For example, Papadimitriou uses log-space reductions throughout his textbook [Pap94], including the definition of NP-completeness.  (Note: in [Pap94], the term “L-reduction” means something completely different from log-space reduction.)  As for P-completeness, NCk reductions are mentioned in [GHMRSS00].  This is a special case of NC reductions, and more general than log-space reductions for k≥2.

But are they really different notions, or just different definitions for the same notion?

Currently, no one knows.  For example, log-space reducibility and polynomial-time reducibility are equivalent if and only if L=P.

[GHMRSS00] Raymond Greenlaw, H. James Hoover, Satoru Miyano, Walter L. Ruzzo, Shuji Shiraishi, and Takayoshi Shoudai.  The Parallel Computation Project: Volumes I–III, 2000.  http://www.cs.armstrong.edu/greenlaw/research/PARALLEL/

[Pap94] Christos H. Papadimitriou.  Computational Complexity.  Addison-Wesley, 1994.


Which of the common sorting algorithms can be parallelized? I want to know that whether which of the following algorithm can be parallelized?

Bubble Sort,
Insertion Sort,
Selection Sort,
Shell Sort,
Quick Sort,
Merge Sort,
Radix Sort.

Those which can't be, please explain me briefly that how? Or please try to tell me in simple words that what is parallelism in sorting algorithms.

Check this link.
Parallelism can be achieved by using  pipeline of processing units or using multiple processor link.

For comparison based sorting lets take an example of quick sort , in quick sort after we find the pivot then we can process two parts in parallel.

quicksort(A)
if |A| = 1 then return A
i := rand int(|A|)
p := A[i]
in parallel do
 L := quicksort({a : a ∈ A | a < p})
 E := {a : a ∈ A | a = p}
 G := quicksort({a : a ∈ A | a > p})
return L ++ E ++ G

Another example we can take is of Radix sort which does not directly compare keys to determine ordering.The basic radix sort algorithm (whether serial or parallel) examines the keys to be sorted one “digit” position at a time, starting with the least significant digit in each key.For implementation in parallel see this tutorial Parallel In-Place Radix Sort


Rank athletes by weighted criteria I have a structure. that consist of the following:

Athlete A         Athlete  B     Athlete C
speed=10          speed=12       speed=6
endurance=60      endurance=59   endurance=64

I would like to rank the strength of those three Athletes based on their speed and endurance. I would like to give a slightly greater weight (0.6) to the endurance. Is there any algorithm that have a good complexity to solve this problem?

I would like to rank the strength of those three Athletes based on their speed and endurance.

There is an infinite number of ways of doing that. The two lexicographic orders and weighted sums are only a few examples.

What do you really want?

  I would like to give a slightly greater weight (0.6) to the endurance.

This suggests that you want (linear) weighted sums. If that is to make sense, you need to normalize your values to a shared scale. You don't give units or ranges, so I'll have to guess.

Normalizing with the maximum values in the sample and assuming that values $0$ are possible, a weighted sum that gives weight $p \in [0,1]$ to endurance and $1-p$ to speed looks like this:

$\qquad\displaystyle w(a) = p \cdot \frac{\operatorname{end}(a)}{64} + (1-p) \cdot \frac{\operatorname{speed}(a)}{12}$.

Implementing this is so straight-forward that it's barely worth being called "algorithm"; you'll certainly find nothing in a textbook that lays out the details for your. Just code it down.


Data transfer at certain frequencies I am curious as to what the maximum data transmission rates are to a given frequency.

Say you have a com channel with a frequency of 10 khz. How many bits/s would you be able to send?

Thanks!

Channel Capacity or maximum data rate is the maximum rate at which data can be transmitted over a given communication link, or channel.

In general, information is conveyed by change in values of the signal in time. So more the frequency of a signal, more is the achievable data rate.

For a communication channel,

Δf⋅Δt≈1

To transmit one signal, a pulse of length Δt (in time) is required. If one signal represents one bit, then the data rate is about 1/Δt. So the maximum data rate in bit/second is about the same as the band width Δf in Hertz.

But this is an incredible underestimate of the information capacity of a transmission system. It assumes that you are sending rectangular shaped pulses.
Using different encoding schemes, more than one bit can be represented by one cycle of signal.

The channel capacity of a channel increases proportionally with the bandwidth. But in practice, we cannot keep increasing the signal bandwidth infinitely. Apart from this, there are other standard transmission constraints in the form of different channel noise sources that strictly limit the signal bandwidth to be used. According to Shannon Hartley equation, the only limit to data rate in a given bandwidth is, the Signal to Noise Ratio.

Using Shannon formula we can obtain an absolute limit of the maximum data transmission rate.

$C = B + log_2(1 + S/N)$

C - Channel capacity
B - Bandwidth
S - Average received signal power over the bandwidth
N - Average noise over the bandwidth


Complexity of algorithm to find number of elements > element index i in an array The question is:

Given an array of size N, arr, create another array whose index i = number of elements in sub-array(arr, i+1, N-1) that are greater than arr[i].

Eg. if input array is,
5 3 9 8 2 6
output array is
3 3 0 0 1 0

O(N^2) is simple just two for loops.

I think a O(N*logN) is possible by starting from last element and adding each element to a height-balanced BST with a size element.

Any thoughts on if we can do O(N)?

Your problem is very related to that of computing the number of inversions in a permutation, or (equivalently) the Kendall tau distance between two permutations; this is the sum of your vector. In fact, your vector (with a very superficial change in the definition) is known as the inversion vector.

There is a classical data structure of Dietz that can be used to compute the inversion vector in time $O(n\log n/\log\log n)$; the $O(n\log n)$ solution you mention is the baseline here. Fredman and Saks proved a matching lower bound showing that the time complexity of Dietz's data structure is optimal. Computing the insertion vector can however be done faster: Chan and Pătraşcu give an $O(n\sqrt{\log n})$ algorithm (see under "Offline dynamic ranking and selection").


How to prove certain parts of one regular language restricted by another regular language is also regular? I’ve encountered the following difficult question that I don’t know how to solve.

$L_1$ and $L_2$ are regular languages over the same $\Sigma$. $$\begin{align}L^\wedge=&\{σ_1σ_2...σ_n\mid n\ge1, \sigma_1, \sigma_2, \cdots, \sigma_n\in \Sigma, \\
&\exists \mu_1, \mu_2,\cdots,\mu_n,\zeta_1,\zeta_2,\cdots\, \zeta_n
\in\Sigma, \\
&\mu_1\mu_2\cdots\mu_n\in L_2,\sigma_1\mu_1\zeta_1\sigma_2\mu_2\zeta_2...\sigma_n\mu_n\zeta_n\in L_1\}\\
&\cup\{a\mid a\in L_1, a\in L_2, a=\epsilon\}\end{align}$$
where the second set on the right hand side just says that $\epsilon\in L^\wedge\Leftrightarrow \epsilon\in L_1\land \epsilon \in L_2$.

How can we prove $L^\wedge$ is regular using closure properties or a product automaton?

What i tried to do is:

Since $n \geq 0$, we can build $\Sigma^* = \{ \sigma^* | \sigma \in \Sigma \} $ $(\Sigma \cup \Sigma) \to \Sigma^*$, then for some function h we can assign $h(\sigma)=\sigma$ (also $h(\sigma')=\sigma$), so because of homomorphism $h^{-1}(L_1 \cup L_2) = \{ \sigma_1...\sigma_n |\forall 1 \leq i \leq n \to \sigma_i \in \{ \mu_i,\mu_i' \}, \mu_1...\mu_n \in L_1 \cup L_2 \} $,

So if $(L_1 \cup L_2)' = h^{-1}(L_1 \cup L_2) \cap ( \sigma'\Sigma \Sigma')*=\{ \sigma_1'\sigma_2\sigma_3'...\sigma_{n-2}'\sigma_{n-1}\sigma{n}' | \sigma_1... \sigma_n \in (L_1 \cup L_2)$ is also regular

So if for some function $f$, $f(\sigma)=\sigma$ and $f(\sigma')=\epsilon$ $(f|f:(\Sigma' \cup \Sigma) \to \Sigma^*)$

Then $f(L_1' \cup L_2') = \{ \mu_1...\mu_n | σ_1μ_1ξ_1...σ_nμ_nξ_n∈L_1 \cup L_2 = L^∧$ and if regular because of regular languages closure to homomorphism

I know it’s complicated and would appreciate help with it, seeing how to do it correctly (pretty sure I've made some mistakes along the way).

Let me point you to the proper tools.

The operation of (perfect) shuffle takes two languages $K,L\subseteq \Sigma^*$ and alternatingly takes a symbol from one of them:

$sh(K,L) = \{ a_1b_1a_2b_2 \dots a_kb_k\mid k\ge 0, a_i,b_i\in\Sigma,\text{ where }  a_1a_2\dots a_k\in L\text{ and } b_1b_2\dots b_k\in K  \}$

This operationhas been discused various times, using both automata and closure properties:
Proving regular languages are closed under a form of interleaving,
Show that regular languages are closed under Mix operations, and
Closure of regular languages to shuffle using closure operations, but probably more.

Then there is the kind-of reverse of this operation, given a language $K\subseteq \Sigma^*$, keep every second letter of its strings:

$2nd(K) = \{ a_2a_4 \dots a_{2k} \mid k\ge 0, a_i\in\Sigma,\text{ for some }  a_1a_2\dots a_{2k}\in K  \}$

An example for that is is:
If L is regular, show that even(L) is also regular. Both solutions there are enlightening.

Also in your case one needs some shuffling (to move the letters from $L_2$ within two other letters in order to compare with $L_1$) and some unshuffling (to keep every first letter of three for $L^{\land}$) but now with three letters/languages rather than two.


Intersection of Deterministic Context-Free Languages If deterministic context-free languages (DCFLs) are not closed under intersection, does this mean that the intersection of two DCFLs will always be context free but may not be deterministic? Or does it mean their intersection may not be context-free?

The statement itself doesn't imply that.  It just means that the intersection of two DCFLs might or might not be a DCFL; and thus presumably could be a DCFL; could be a CFL but not a DCFL; or could be not context-free.
However, we know more actually.

The intersection of two DCFLs could be, of course, a DCFL. For example, you can let both of them be the same DCFL. For another example, just take any two regular languages. Every regular language is a DCFL and the intersection of two regular language is still regular.

Here is an example of two DCFLs the intersection of which is not a CFL.  The intersection of $\{a^{n}b^{n}c^m \mid n\ge0, m\ge 0\}$ and $\{a^{n}b^{m}c^m \mid n\ge0, m\ge 0\}$ is the most classical non-CFL, $\{a^{n}b^{n}c^n \mid n\ge0\}$.

Exercise. Find two different non-regular DCFL the intersection of which is a DCFL.
Deeper fact. Given any natural number $n$, there is a language that is the intersection of some $n+1$ DCFLs, but it is not the intersection of any $n$ DCFLs.


What does Harper mean by "class"? I've been teaching myself type theory on and off over the past couple years. I've reach large sections of Pierce's Types and Programming Languages and Harper's Practical Foundations for Programming Languages, but there are still sections I need to either read for the first time or really understand.

In Harper's section on classes, this is his introduction:

  It frequently arises that the values of atype are partitioned into a variety of classes, each classifying data with distinct internal structure. A good example is provided by the type of points in the plane, which may be classified according to whether they are represented in cartesian or polar form. Both  are represented by a pair of real numbers, but in the cartesian case these are  the x and y coordinates of the point, whereas in the polar case these are its distance, r, from the origin and its angle, θ, with the polar axis. A classified  value is said to be an object, or instance, of its class. The class determines the  type of the classified data, which is called the instance type of the class. The classified data itself is called the instance data of the object.

As far as I can tell, this does not align closely with objects as they are commonly understood in programming languages today. When I think of classes, I think primarily of encapsulation and inheritance, not of classifying different representations of a value.

Am I right in believing this is not the same definition of classes that is commonly used? Is this definition common in the academic community? Are there any programming languages where these kinds of classes are used?

Update

Since this question seems to have attracted some recent activity, I'll update with my current understanding.

We start with the general, abstract notion of a two-dimensional table. Each cell in the table specifies a function acting on a specified type. Thus, the rows are "classes" and the columns "methods" with dynamic dispatch.

If we take the row-oriented view, then we have the standard notion of a class in mainstream OOP languages: a record of functions acting on a specified type of data. If we instead take the less commonly considered column-oriented view, we have a function that uses case analysis on the type of its first argument. The fundamental take-away is that neither the row or column-oriented view is more natural; we must understand classified values as a two-dimensional table.

It does turn out that we need need sum types to implement this realization, but that is only one aspect. We also need product types, and then to view these product and sum types in the right light.

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

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

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