Weight functions in graph algorithms In text books, for instance in the 3rd edition of Introduction to Algorithms, Cormen, on page 625, the weights of the edge set $E$ is defined with a weight function $w:E\rightarrow \mathbb{R}$.

Why is it defined in this way? Why do we need a function? I mean, we all know when working with a graph, that the meaning is just that an edge $(u,v)$ has a weight $w$. So, why is it written with a function? I remember the first time I saw this definition I was very confused. Only after actually going through an algorithm and reading it again, I realized that it really just means that every edge has its weight.

So, I still don't fully understand why it is written in this complicated way and what exactly it means though, and it would be very nice if someone could tell me that in a understandable language.

Here is the original statement in CLRS.

  Assume that we have a connected, undirected graph $G$ with a weight function $w: E\to\Bbb R$, and we wish to find a minimum spanning tree for $G$.

It is pretty good to understand "a weight function $w:E\rightarrow \mathbb{R}$" as "an edge has a weight". In fact, that is how I would interpret that notation in a rush or subconsciously. It is good enough in most situations. I would encourage you to keep this primitive understanding, as it may help forming the most compact and natural representation of knowledge in your mind.

Should we read aloud that notation, we can say "$w$ from $E$ to $\Bbb R$" or "$w$ from capital $E$ to bold $\Bbb R$" literally. Adding a bit of interpretation, we can also say, "function $w$ from edges to real numbers", "function $w$ that maps each edge to a real number", or, even more explicitly, "function $w$ whose domain is the set of edges and whose codomain is the set of real numbers".

While the simple and natural understanding, "an edge has a weight", is probably enough to understand the setup for that section of the book, that mathematical notation has some distinct advantages.

In general, although expressive and colorful, natural languages or thoughts, are more complex and abound with ambiguity and arbitrary vagueness. If "an edge $(u,v)$ has a weight $w$", is weight something like "2 miles", "5.0 dollars", or "approximate 7.7 pounds"? Could the edge $(u,v)$ also have an extra weight? Should I use the same symbol $w$ for the weight of edge $(u,v')$ that is not edge $(u,v)$? While these questions may or may not pose a problem for you, it might for other readers of the book.

On the other hand, the notation "$w: E\to\Bbb R$" defines exactly what is the domain, codomain and the kind of correspondence of a relation. To be pedantic, it means the symbol/entity $w$ associates to every element of $E$, i.e, an edge of $G$ exactly one element of $R$, i.e, a real number. There is no room to err.

Moving down the road, page 648 of the book presents the following formula.

  $\begin{aligned}
w(T') &= w(T)  - w(x,y)  + w(u,v)\\
      &\le w(T)
\end{aligned}$

If you try to express the facts embodied in the above formula in plain English, more than two or even five times longer statements may be needed to attain the same rigor and clarity. The result can hardly be more visually appealing. That is how the notation $w:E\to\Bbb R$ shines.

The power of mathematics notations, including notations in computer science, is what you would like to master if you want to dive further into the mathematics, computer science and many other subjects where symbolic computations are needed and useful. In a sense, notations like this are beautiful data types. You can get familiar with them. You can become comfortable with them.


IDE and EIDE data transfer speed Why are data transfer speeds faster with EIDE than IDE? Wouldn't it be slower with the additional conversion of logical block addressing? What did they change to make it faster?

tl;dr: 25 times the clock frequency and two transfers per clock cycle equals 50 times the data rate.
First of all, let's forget about the terms IDE and EIDE. They were never specified in any standard or reference, and they were used in widely different manners by different people.
Some people use the term IDE (Integrated Drive Electronics) for any interface where the drive controller is integrated into the drive hardware, i.e. they use the term IDE to refer to any ATA, SATA, SCSI, SAS, IEEE1394, USB, or Thunderbolt drive. Some use it to refer to ATA-1 and the proprietary predecessors only, some use to refer to all ATA versions. Some people use the term EIDE to exclusively refer to ATA-2, some use it to refer to ATA-2 and ATA-3, some to any standard starting with ATA-2, excluding SATA, and some to any standard starting with ATA-2 including SATA.
So, let's stick to just official ATA versions, and let's call the proprietary versions before ATA-1 pre-ATA.
(Almost) every new ATA version has introduced new transfer modes, starting with the very simple PIO 0 transfer mode of pre-ATA. Each transfer mode has its own maximum transfer rate and cycle time.
Looking at Wikipedia, those were:

pre-ATA:

PIO 0 [3.3 MB∕s | 660 ns]

ATA-1: adds

PIO 1 [5.1 MB∕s | 383 ns]
PIO 2 [8.3 MB∕s | 240 ns]
Single-word DMA 0 [2.1 MB∕s | 960 ns]
Single-word DMA 1 [4.2 MB∕s | 480 ns]
Single-word DMA 2 [8.3 MB∕s | 240 ns]
Multi-word DMA 0 [4.2 MB∕s | 480 ns]

ATA-2: adds

PIO 3 [11.1 MB∕s | 180 ns]
PIO 4 [16.7 MB∕s | 120 ns]
Multi-word DMA 1 [13.3 MB∕s | 150 ns]
Multi-word DMA 2 [16.7 MB∕s | 120 ns]

ATA-3: drops all Single-word DMA modes
ATA/ATAPI-4: adds

Ultra-DMA 0 [16.7 MB∕s | 240 ns ÷ 2]
Ultra-DMA 1 [25.0 MB∕s | 160 ns ÷ 2]
Ultra-DMA 2 [33.3 MB∕s | 120 ns ÷ 2]

ATA/ATAPI-5: adds

Ultra-DMA 3 [44.4 MB∕s | 90 ns ÷ 2]
Ultra-DMA 4 [66.7 MB∕s | 60 ns ÷ 2]

ATA/ATAPI-6: adds

Ultra DMA 5 [100 MB∕s | 40 ns ÷ 2]

ATA/ATAPI-7: adds

Ultra DMA 6 [133 MB∕s | 30 ns ÷ 2]

Note that the Ultra DMA 4, 5, and 6 transfer modes required 80-wire ribbon cables instead of the older 40-wire ribbon cables. The 80-wire ribbon cables still had 40 connectors with the same pinout and semantics as the older cables, every other wire was a ground wire that was intended to provide physical separation as well as reduce capacitative coupling between the signal wires.
Also note that the Ultra DMA modes have two transfers per clock cycle, hence Ultra DMA 0 has the same maximum transfer rate as PIO 4 at half the clock speed.
Also, later versions introduced independent device timing, which allowed the host adapter to talk to each of the two devices on the bus with a different timing, whereas before that, it had to use the timing of the slower of the two devices.
Other than improvements to the transfer mode, there were also improvements to the command set that improved performance especially with multiple drives per bus. Originally, commands were completely serialized. The host adapter was only allowed to send a new command once the previous command was finished. ATA/ATAPI-4 introduced overlapped commands and queued commands as optional extensions to the ATA Command Set (ACS).
Overlapped commands allow the host adapter to send overlapping commands to both Device 0 and Device 1 on the bus, i.e. it allows the host adapter to parallelize communication with the two devices. Queued commands allow the host adapter to place multiple commands in a queue on the device, thus allowing the device to schedule the commands in a way that makes most sense for the device.
E.g. imagine, there is a WRITE command to write A into block 23, another WRITE command to write B into block 23 and a READ command for block 23, the drive could just throw away the first WRITE command, have the READ command immediately return B without even moving the read head, and only execute the second WRITE command.
However, neither overlapped nor queued commands were actually widely implemented because they caused a large load on the host CPU due to the way they were designed for backwards-compatibility with the ISA bus (from which the original pre-ATA bus was derived in 1986 and even the very latest version of Ultra DMA 6 in 2005 still had to be compatible with). Placing this large load on the host CPU meant that in most cases, while raw drive performance might have slightly increased depending on workload, the overall system performance didn't improve.
So, performance improvements were mostly made by improving the transfer mode, mainly by increasing the clock frequency (from 1.67 MHz in pre-ATA all the way up to 41.67 MHz in Ultra DMA 7), and later making two transfers per clock cycle (Ultra DMA). The command set added (optional) features for performance improvements as well, but those features were widely ignored.
Using DMA transfer as opposed to Polling I/O also helped, especially reducing load on the host CPU.


Constructing deterministic PDA for not regular language Let the input alphabet be $\Sigma = \{a,b,c\}$ and L be the language of all words in which all of the a’s come before all of the b’s and there are the same number of a’s as b's and arbitrarily many c’s that can be in front, behind or among the a’s and b’s.
Some words in L are: abc ccacaabcccbccbc

I know that the language is not regular but how can I find a deterministic PDA (in a drawing fashion) that accepts L?

Edit: So far I've ended up with this which takes care of having the same number of a's as b's and all a's come before all b's. However I cannot figure out how to account for the arbitrary amount of c's in-between b's. Any ideas?

Sorry for the horrible drawing in advance.

Recipe in shorthand. Ignore $c$'s. Use a bottom fo stack symbol $Z$ that stays there. Keep the surplus of $a$'s on the stack. So $ZAAA$ (top of stack right) means three $a$'s more than $b$'s. If we read another $a$ push $A$, if we read another $b$ pop an $A$ (and move to another state to indicate we have now seen $b$).


Proving complexity of $T(n)=2T(n/3 + 1) + n$ non-Akra-Bazzi We know that the complexity of $T(n)=2T(n/3 + 1) + n$ is $\Theta(n)$, as has been proved on this exchange before. However, what about proving it inductively? I believe that this method might work.

Guess $T(n) \leq cn-d$. Assume true for $m < n$. Specifically, $m = n/3 < n$
Then, $T(n) \leq cn-d$.

$T(n) \leq 2(cn/3 - d + 1) + n$ $= 2cn/3 - 2d + 2 + n$  $=n(2c/3+1)+2(1-d)$. Then for values of $c \geq 1$ and $d \geq2$  we have $T(n) \leq cn - d$. Then $T(n)=\Theta(n)$.

What does everyone think?

You can use the variant by Leighton "Notes on Better Master Theorems for Divide-and-Conquer Recurrences". Lehman, Leighton and Meyer in "Mathematics for Computer Science"
on page 1019 state a simplified version: If you have $T(n) = \sum_{1 \le i \le k} a_i T(b_i n + h_i(n)) + g(n)$, where $a_i > 0$, $0 < b_i < 1$, $g(n) > 0$ such that $\lvert g'(x) \rvert$ is bounded by a polynomial, and $\lvert h_i(n) \rvert = O(n / \log^2 n)$, then is $p$ is the unique real such that $\sum_{1 \le i \le k} a_i b_i^p = 1$, then:

$$
T(n) = \Theta\left(
               n^p \left(
                      1 + \int_1^n \frac{g(u)}{u^{p + 1}} d u
                   \right)
             \right)
$$

Your $g(n) = n$ certainly qualifies. With $a_1 = 2$, $b_1 = 1/3$, $h_1(n) = 1$ satisfies the condition, you get:

$$
  2 \cdot 3^{-p} = 1
$$

from which $p = \log_3 2$, so that:

$$
T(n) = \Theta\left(
               n^{\log_3 2}
                  \left(
                      1 + \int_1^n u^{- \log_3 2} d u
                   \right)
             \right)
     = \Theta(n)
$$


Tag-free garbage collection for object oriented languages I'm looking around for a good garbage collection technique for my language and found this paper, where Benjamin Goldberg describes a garbage collection technique for strongly typed languages, which removes the need for type information during runtime.

Briefly, this is done by placing a pointer to a garbage collection function right after a function call, directly in the compiled code. They then extend this to support ML-like parametric polymorphism.

Now my question: Has there been any work on how this technique could be implemented in an object oriented language, where much functionality is implemented through indirect calls using pointers in a virtual table?

Like Häagen-Dazs ice-cream, Object Orientation comes in many flavor,
though with more nuts and bananas. Hence it is hazardous to answer
your question stated in very general terms. Specific OO languages
could have unexpected features that might raise problems with virtual
methods. I fear that trying to imagine what kind of features could make
things go wrong is a bit of a fruitless exercise. It is better to try
answering precise questions.

The basic principle of tag-free GC is that, at any time, you should be
able to inspect the memory starting from the stack, and know the
actual type of all chunks of live allocated memory (because that is
precisely what the GC will need to work). This implies also to know,
at each call point of a function/method, the current state of
activation block of the caller, whether on the stack or on the heap,
i.e. the current variables of the block and their state of
initialisation. The necessary structural information can be stored as
data descriptors to be interpreted, or as executable gc-routines for
better GC efficiency. The important point of tag-free GC is that this
information can be determined statically, in order to be stored once
with the code rather than with each instance of a type or class or of
function activation. When this information can change dynamically, as
is the case with polymorphic types, it must be possible to compute it
by tracing and compounding static type information through the dynamic
call sequence.

The fact that a method is virtual and called through a virtual table
is not in itself a problem. A caller does not need to know what it is
calling as it has no importance regarding GC for its own activation
record. The callee is supposed to know itself (the compiler sees to
it), and carry whatever information it need. The information may be
incomplete as in the case of polymorphism, and must be completed from
other type information available in the call sequence. Actually, in
a language like ML, where functions can be passed as parameters, or put
in tuples, the
caller may not know what function it is actually calling.

What matters is that the caller knows where in its code it calls the
callee, so as to determine the state of its activation block during
the call. This is
statically dependent on the call point, and can thus be inferred from
the callee return address,(in various ways depending on technical
variations used by different authors). The corresponding gc-routine
can thus be found in some way from that return address. For example,
it can be in the code right after the call, but other equivalent
techniques could be considered. So if the callee is interupted by
GC, it will be possible to do the GC for the callers activation
record. The caller does no GC work for the callee, only for its own
activation record.

What may be a problem is making sure that the callee does know the
actual type of all the values that are passed to it (as in polymorphism).
More precisely, it must be possible to find that information when the
GC occurs and must deal with the activation record of the actual
method that is access through a virtual.

I believe that being more precise on this last issue is dependent on the actual features
and classe/objects structures of the OO language, on its typing
organization.

But, as the caller does not need to know the callee, I do not see that
indirect calls can be a problem.

Another point (answering the OP's comment) is that the issue here is
not whether GC is performed from compiled code or interpreted from
descriptors, but whether it needs dynamic tag for type information.

Suggestion: to find more work on this, take your favorite search
engines (and other web resources) and look for papers
citing the Goldberg papers or its mains references. Apply the
procedure recursively, adding occasional keywords such as object
oriented or virtual.


Intuition of lower bound for finding the minimum of $n$ (distinct) elements is $n-1$ as dealt with in CLRS I was going through the text Introduction to Algorithms by Cormen et. al. where there was a discussion regarding the fact that finding the minimum of a set of $n$ (distinct) elements with $n-1$ comparisons is optimal as we cannot do better than it, which means that we need to show that running time of algorithm which finds the minimum of a set of $n$ elements is $\Omega(n)$.
This is what the text says to justify the lower bound.

We can obtain a lower bound of $n - 1$ comparisons for the problem of determining the minimum. Think of any algorithm that determines the minimum as a tournament among the elements. Each comparison is a match in the tournament in which the smaller of the two elements wins. Observing that every element except the winner must lose at least one match, we conclude that $n-1$ comparisons are necessary to determine the minimum.

Now I could make the thing out in my own way as:

What I have done is a top down comparison, but the authors by their words "Observing that every element except the winner must lose at least one match, we conclude that $n-1$ comparisons are necessary to determine the minimum." seems they are pointing to some bottom up approach which unfortunately I cannot make out.
How,
"That every element except the winner must lose at least one match" $\implies$ "$n-1$ comparisons are necessary to determine the minimum".

Every match has exactly one winner and one loser. If every element except the winner must lose at least one match, there must be at least $n-1$ matches, as otherwise there would be a match with two losers. So, at least $n-1$ matches are nessecary to determine a winner, i.e. $n-1$ comparisons are nessecary to determine the minimum.

The explanation given in the book is valid, but I personally prefer another approach. (which does require some elementary graph theory) Suppose you draw the graph with the elements as nodes and you draw an edge for each pair of elements that your algorithm compares. Note that it is impossible to know which of a pair of elements is smaller if there is no path between them in this graph. So, if we have determined the minimum, this graph must connected. Any connected graph on $n$ nodes has at least $n-1$ edges, so there must have been $n-1$ comparisons.


A term for two algorithms which give same results but differ in complexity Is there a technical term for a pair $(u,v)$ of algorithms, such that $u$ and $v$ have an identical output for each input (I include the option if not halting as a possible output), but they have different complexity (either time or space) as a function of their input?

An example of such a pair is (bubble sort, quicksort)

What you are talking about is very narrow, there is no term† that describes it exactly.

However, a closely related concept that you might be interested in is extensional equivalence as opposed to intensional equivalence. Intuitively, two objects are extensionally equivalent if they have the same external properties, and intensionally equivalent if they have the exact same definition.

Generally, mathematics and logic define equality as (some form of) extensional equivalence; for instance, the Zermelo-Fraenkel set theory includes some form of the following axiom:

$$
\forall x \forall y [\forall z (z \in x \Leftrightarrow z \in y) \Rightarrow x = y]
$$

Since functions are really relations, and relations are really sets, two functions that are point-by-point identical are literally the same function. But still, I believe that most of us would agree that even though quicksort and bubblesort are somewhat related, they are not the same thing.

So the real question here is what is the thing you call "the algorithm quicksort"? It's certainly more than just a program: quicksort written in C is not the same program as quicksort written in Haskell, but we would still call both quicksort. But at the same time it's not really just a function, defined by its input and output: in order to deserve the name "quicksort" you also have to operate in a certain way.

It's not a question I have a good answer for, there is no† precise and universal definition of "algorithm" (yet).

In the meantime, I would say that quicksort and bubblesort are extensionally equivalent but not intensionally equivalent.

† (or, at least, none I'm aware of)


How can GIF compression be lossless if the maximum # of colors is 256? I'm reading "Computer Science Made Simple" by V. Anton Spraul, and in the chapter about Graphics, he describes GIF files as follows:

  A GIF file uses lossless compression to store an image with a maximum of 256 different colors.

The way I read this, it sounds like the book is saying it stores the image, but the stored image will have a maximum of 256 colors.  If this interpretation is incorrect, and the author means that the GIF format only works with original images that have a max of 256 colors, then let me know since this makes my question redundant.

With that out of the way, let's assume the following scenario:

1) I have an arbitrary image with more than 256 colors.
2) I open the file in Photoshop or some other advanced image editor.
3) I save it as a GIF.

My question is, wouldn't this result in a loss of information, or artifacts in the new GIF?  I'm capped at 256 colors when using the GIF format, and therefore would lose data, right?

GIF is only capable of storing images with at most 256 different colours. If you have such an image, the compression used by GIF is lossless. If you have an image with more than 256 different colours, you must first reduce the number of colours, which does indeed lose data but that's a preprocessing stage that isn't part of the compression process. Once you've preprocessed, the compression occurs without further loss.

You should parse the sentence quoted in the question as "If you have an image with at most 256 colours, GIF will compress it losslessly", rather than "If you have an image, GIF will losslessly produce a compressed version with at most 256 colours."


Constrained optimization topics Given functions $f, p, c$, a matrix $X$, and vectors $C,D,E$.

I want to maximize the multivariable function $f(X)$, where $X$ is a $p \times q$ binary matrix ($X_{ij}$ is 0 or 1). So, $p\cdot q$ variables. The function $f(X)$ is given by
$$ f(X) = \sum_j \sum_i C_{ij} X_{ij} - \sum_j p(X,j), $$
where $C$ is a matrix of constants and $p$ is a penalty function (basically could be rewritten as a loose constraint as far as I can tell):
$$p(X,j) = \max(0, \sum_i X_{ij} - D_j)^2,$$
where $D$ is a vector of constants.

As hard constraints we got that $X_{ij}$ is binary, and
$$c_i(X) = \sum_j X_{ij} \leq E_i,$$
where $E$ is a vector of constants

I found linear programming is a topic that solves problems like this, and then found constrained optimization which would be more or less what I want, although I don't know how to write max() into inequalities. I suppose I could try to split the solution if the conditional branch was enforced on a single variable, but there are several conditionals at the same time anyway. Out of my searches the penalty method looks extremely similar to my equations, but there's the hard constraints that haven't been merged into the main function.

I request the exact topic I can research, I'm a bit confused as all of this is new to me and I'm not sure I'm studying the right topics.

This can be formulated as a mixed-integer quadratically constrained quadratic programming (MIQCQP) problem, integer programming with quadratic constraints and a quadratic objective function.   You can find off-the-shelf  solvers out there, and I think some of them support MIQCQP.  Unfortunately MIQCQP is a pretty hard problem, so it's hard to know whether this will be effective, for the size of problem you have.  But it could be worth a try.

You can encode the max by the two constraints $p_j \ge 0$, $p_j \ge (\sum_i X_ij - D_j)^2$, where $p_j$ is a variable representing $p(X,j)$.  Since you're going to minimize a sum of $p_j$'s, this suffices (the minimization objective will chose the smallest $p_j$ that satisfies both inequalities, which is the max).

Alternatively, if you're willing to remove the "squaring" in the definition of $p(X,j)$, this could be formulate as an instance of integer linear programming.


Does a Context-free language have a grammar that has either 3 or 0 nonterminals on the right hand side? Is the following true or false? Why?

Let L be a context-free language with $\epsilon\notin$ L. Then there is $\epsilon$-free grammar $G=(V,\Sigma, P,S )$ with $L (G) = L$, so all production rules are of form $A \to BCD$ or $A\to a$ with $A, B, C, D \in V$ and $a\in$ $\Sigma$.

I don't know normal forms for context-free languages. Just the CNF for regular ones. Trying a few small examples don't gives me a generally valid response, if there are really always production rules of this form.

Hint, can the production rules of that form generate a word  of length 2? Is there a context-free language that contains a word of length 2?


Name for the "starting vertex" and "ending vertex" of a directed edge Say a graph contains a directed edge e from vertex a to vertex b.  Is there a standard name for vertex a relative to edge e?  And similarly for vertex b?

Something akin to vectors in high school physics, where the initial point of the vector is called the "tail" and the terminal point of the vector is called the "tip"?  I'd like to say something like "a is the tail of edge e" or "b is the terminal vertex of edge e."

$a$ is the tail or initial vertex of the edge $(a,b)$
$b$ is its head or terminal vertex.


Confusing example of a language which may be Context-free or not context-free Hi so consider the language $L= \{(0^i)(1^j)\mid i=k*j \text{ for some positive }k\}$ Could I not rewrite this as $\{((0^k)^j)(b^j)\mid k>1\}$. Seeing it in this form makes me think of a form $a^n b^n$ which we know is context free so therefore it should be context free. Is my logic wrong and if not what would be the best way to show it's context free.

The best way to show that a language is context-free is to use one of the equivalent definitions of context-free languages. The two most popular ones are:

A language is context-free if it is generated by a context-free grammar.
A language is context-free if it is accepted by a (non-deterministic) push-down automaton.

The language $\{ a^n b^n : n \geq 0 \}$ is generated by the grammar $S \to aSb | \epsilon$. Let's try to use the same idea for your language: $S \to 0^k S 1 | \epsilon$ (we can implement $0^k$ using context-free rules). The problem is that we can't guarantee that the same $k$ is used in all productions. This leads me to conjecture that the language is not context-free.

How do we show that a language is not context-free? The most popular way is to use the pumping lemma or one of its variants, though this method doesn't always work. Perhaps you should give it a try.


Term for members of a class that are not inherited Is there an explicit term for a member of a class that is not inherited from any parent class?

class Vehicle {
    int weight;
}

class Car extends Vehicle {
    int numDoors;
}

Car car = new Car();
car.weight = 10000; // weight is an "inherited member"
car.numDoor = 4; // what's the term for numDoor?

Just a member variable. If you want to specify that it is not inherited, I suppose you could call it 'noninherited member variable'. Wiktionary lists this as a term in computing.


How to calculate IV, EV and optimal k for K-means? Could someone explain how to calculate the following 3 evaluative properties:

Intercluster Variability (IV) - How different are the data points within the same cluster
Extracluster Variability (EV) - How different are the data points that are in distinct clusters
Optimum value of k

The third one I believe is by min EV/IV

Anyway please advise.

$C$ is a cluster, $c$ is centroid, $d$ is provided distance function, $\delta$ is Dirac measure, $x$ is element.
$IV = \sum \limits_C \sum \limits_{x \in C} d(x, c)$ meaning for each cluster calculate the sum of distances from it's centroid, and sum the results.

$EV = \frac{1}{N} \sum \limits_i \sum \limits_j\delta(C(x_i) \ne C(x_j))d(x_i, x_j)$ meaning sum the distances between elements from different clusters and divide the result by number of elements.
One possibility for optimal $k$ is to minimize $\frac{IV}{EV}$. But there are some other techniques of determining optimal number of clusters or referenced from there eight methods of finding $k$. In fact I would not state that any given method is better, preferable or can be determined blindly in advance, this is the part where you should define your optimum that makes sense to you, your data and outcome of what you use clusters for.


Temporal compression protocol Recently it occurred to me that one could potentially design an interactive "compression" scheme which seems to allow for arbitrarily high compression ratios, at the sole expense of time. This already sounds pretty cranky, I realize that, but here is a formal description of the protocol which I hope makes sense:

Define a data store as a tuple $(\mathcal{O}, n, \delta)$ with $\mathcal{O} : \mathbb{N} \to \{ 0, 1\}^n$ a random oracle. We say that the data store "contains" the value $x$ at a (real) time $t \geq 0$ if $\mathcal{O}(\lfloor t \delta^{-1} \rfloor) = x$, such that the contents of the data store randomly change every $\delta$ units of time. A data store could be realized in software using the current time in some agreed-upon representation and any cryptographic hash function.
Alice wants to sends a message to Bob encoded as a bit string as part of an interactive protocol (Alice and Bob are both present and active during the transmission). First they both agree on a suitable $\delta$ such that they can both resolve the current time to within $\delta$ units of time. Then, Alice chooses an integer $n \geq 2$, instantiates a data store $(\mathcal{O}, n, \delta)$, and sends these parameters to Bob, and then breaks up the message into $n$-bit blocks. For each block, Alice then monitors the data store until its contents equal the block, at which point Alice sends a single bit "1" to Bob. When Bob receives this signal, he looks up the contents of the data store and retrieves the corresponding $n$-bit block (possibly rewinding as needed to account for any transmission delay, this is feasible as long as the transmission delay is fairly constant and known to within $\delta$ units of time). When the last block is sent, Alice sends the bit "0", Bob computes a checksum of the message and sends it to Alice for verification.
If the message contained $m$ $n$-bit blocks, the total amount of data actually sent (outside of protocol overhead) was $m$ bits, achieving a compression ratio of $1 - 1/n$, and it would take an expected $m \delta 2^{n}$ time to successfully send it (that is, $\delta 2^{n} / n$ time per bit). Also note that since this scheme doesn't actually use any structure in the message, it can be given already compressed data to compound any already attained compression ratios: the two are not mutually exclusive.
Clearly this doesn't allow for amazingly high transmission rates in general. A realistic usecase could be communication with a space probe, where the light-time transmission delay may be accurately computed allowing for a very low $\delta$, say, $\delta = 10 ~ \text{ns}$. Then we can achieve decent compression ratio/transmission rate tradeoffs, e.g. 94% at 3 KB/s ($n = 16$) or 90% at 122 KB/s ($n = 10$).
It gets exponentially more time-consuming to send data as $n$ increases, so  95% compression ratio is probably about the best one can practically achieve in reasonable time in the general case.

Obviously this only works as an interactive protocol, not as an offline protocol. Also, it doesn't really work "as-is" in real life because you can't just send 1 bit on most channels, as each communication entails a nontrivial amount of overhead (TCP/IP packet, etc..) but in principle I don't see why it couldn't work.
So, does anyone know if this kind of "temporal communication" has been studied before, and can point out any fundamental or practical problems or errors I overlooked that might explain why it isn't used?

There are two flaws in your idea.

First, compression ratio is not the right metric.  The right metric for evaluating your scheme is the transmission rate: how long does it take to send a $n$-bit message?  The answer is that your scheme fares very poorly under that metric: it takes $\Theta(2^n)$ units of time to send a $n$-bit message.  Therefore, your scheme has very poor performance, both theoretically and practically.

Transmission rate is the right metric for a scheme that sends data over a communication channel.  Compression ratio would be suitable for a compression scheme of the form $C:\{0,1\}^n \to \{0,1\}^*$, but crucially, this requires that the output of the compression scheme can be expressed in bits.  Your protocol doesn't have that property: the output is actually trits.

This leads me to the second flaw in your idea.  Your protocol requires a communication channel that has three states (i.e., can convey one of three symbols at any point in time): "1", "0", or "I have nothing to send right now".  In other words, you need a communication channel that can send trits (0, 1, or 2), not just bits (0 or 1).  But if we had a communication channel like that, we could already achieve higher transmission rate than your scheme.  So, you're not comparing to the right baseline.

For these reasons, your scheme does not beat any information-theoretic bound and does not contradict any theoretical barrier.  It also probably won't be effective or useful in practice.


What is a compact way to represent a partition of a set? There exist efficient data
structures for representing set
partitions. These data structures have good time complexities for operations
like Union and Find, but they are not particularly space-efficient.

What is a space-efficient way to represent a partition of a set?

Here is one possible starting point:

I know that the number of
partitions
of a set with $N$ elements is $B_N$, the $N$-th Bell
number. So the optimal space
complexity for representing a partition of a set with $N$ elements is
$\log_2(B_N)$ bits. To find such a representation, we could look for a
one-to-one mapping between (the set of partitions of a set of $N$ elements) and
(the set of integers from $1$ to $B_N$).

Is there such a mapping that is efficient to compute? What I mean by
"efficient" is that I want to convert this compact representation
to / from an easy-to-manipulate representation (such as a list of lists) in time
polynomial in $N$ or $\log_2(B_N)$.

You can use the way that the recurrence formula below is derived to find your encoding:
$$ B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k. $$
This is proved by considering how many other elements are in the part containing the element $n+1$. If there are $n-k$ of these, then we have $\binom{n}{n-k} = \binom{n}{k}$ choices for them, and $B_k$ choices for partitioning the rest.

Using this, we can give a recursive algorithm to convert any partition of $n+1$ to a number in the range $0,\ldots,B_{n+1}-1$. I assume you already have a way of converting a subset of size $k$ of $\{1,\ldots,n\}$ to a number in the range $0,\ldots,\binom{n}{k}-1$ (such an algorithm can be devised in the same way using Pascal's recurrence $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$).

Suppose that the part containing $n+1$ contains $k$ other elements. Find their code $C_1$. Compute a partition of $\{1,\ldots,n-k\}$ by "compressing" all the remaining elements to that range. Recursively compute its code $C_2$. The new code is $$C = \sum_{l=0}^{n-k-1} \binom{n}{l} B_l + C_1 B_{n-k} + C_2. $$

In the other direction, given a code $C$, find the unique $k$ such that
$$ \sum_{l=0}^{n-k-1} \binom{n}{l} B_l \leq C < \sum_{l=0}^{n-k} \binom{n}{l} B_l, $$
and define
$$ C' = C - \sum_{l=0}^{n-k-1} \binom{n}{l} B_l. $$
Since $0 \leq C' < \binom{n}{k} B_{n-k}$, it can be written as $C_1 B_{n-k} + C_2$, where $0 \leq C_2 < B_{n-k}$. Now $C_1$ codes the elements in the part containing $n+1$, and $C_2$ codes a partition of $\{1,\ldots,n-k\}$, which can be decoded recursively. To complete the decoding, you have to "uncompress" the latter partition so that it contains all the element not appearing in the part containing $n+1$.

Here is how to use the same technique to encode a subset $S$ of $\{1,\ldots,n\}$ of size $k$, recursively. If $k=0$ then the code is $0$, so suppose $k>0$. If $n \in S$ then let $C_1$ be a code of $S \setminus \{n\}$, as a subset of size $k-1$ of $\{1,\ldots,n-1\}$; the code of $S$ is $C_1$. If $n \notin S$ then let $C_1$ be a code of $S$, as a subset of size $k$ of $\{1,\ldots,n-1\}$; the code of $S$ is $C_1 + \binom{n-1}{k-1}$.

To decode a code $C$, there are two cases. If $C < \binom{n-1}{k-1}$ then decode a subset $S'$ of $\{1,\ldots,n-1\}$ of size $k-1$ whose code is $C$, and output $S' \cup \{n\}$. Otherwise, decode a subset $S'$ of $\{1,\ldots,n-1\}$ of size $k$ whose code is $C - \binom{n-1}{k-1}$, and output $S'$.


Is there a measure for connectedness? Is there a name for the "measure of connectedness", i.e. :
$$\text{MoC} = \frac{d(G)}{|G|-1}$$ with domain of function $D_\text{MoC} = [0,1]$, average degree of graph $d(G)$ and amount of nodes $|G|$? Meaning a quantitive measure for connectedness or meshedness of a graph? E.g. a complete graph would have a MoC of 1, while a graph without edges would have a MoC of 0.

Your measure is known as the density of the graph, and is given by the formula $$ \frac{|E|}{\binom{|V|}{2}}, $$
where the graph is $G = (V,E)$.


$FIRST_k$ set -- is algorithm given by Aho&Ullman correct? I am writing this, because no matter how I look at the algorithm I see an error :-)

Aho & Ullman in "Theory of Parsing, vol.1" (pp. 357-359) described the algorithm for building $FIRST_k(A)$ set for any $A$ non terminal by incrementally building helper set $F_i(A)$ which has such property that every $F_i(A)$ set is contained in $F_{i+1}(A)$ and it is finally equal to $FIRST_k(A)$.

However I found a counter example for this, for $k=2$.

A := a B
B := b

$FIRST_k(A) = \{ a b \}$, while $F_0(A) = \{ a \}$.

Any help is appreciated, here is shortened content of those pages -- FIRST(k) -- and if you don’t have a book, I asked the same question in longer form as blog-post -- LALR(k) FIRST sets.

In your example $F_0(A) = \varnothing$ (!) while $F_0(B) = \{b\}$. Then $F_1(A) = \{ab\}$. Voila.

By construction $F_0(A) = \{ x \in\Sigma^* \mid A\to x\alpha \text{ where } |x|=k \text{ or } \alpha = \varepsilon \}$. The only production $A\to aB$ has no terminal prefix with length two, so $F_0(A)$ must be empty.

On the other hand, also the production for $B$ is shorter than two. But here we include the string $b$ as in consists of terminals only (the $\alpha=\varepsilon$ case).

As you note, $F_{i+1}(A) = F_i(A) \cup \text{ something }$, so we have $F_0(A) \subseteq F_1(A) \subseteq F_2(A) \subseteq \dots$. The sets are increasing. The construction stops when two consecutive sets are equal (for all $A$), nothing will be added after that moment.


Big O complexity of algorithm with a nested for loop only running once I have been debating with someone about the big O complexity of the following algorithm. We have a different understanding of the theory. Basically one of us thinks that this algo is automatically O(N^2) since there is a loop over N elements and another potential other loop over N elements inside the loop. The other one thinks that since the second loop over N will only ever be executed once, the complexity is O(N). Help!

Here is the algorithm in Python:

def get_indexes(numbers, sum):
    s = set(numbers)
    for n in numbers:
        if n >= sum:
            continue
        if (sum - n) in s:
            return [numbers.find(n), numbers.find(sum - n)]
    return []

Both of you are correct. The algorithm runs in time $O(n^2)$ (where $n$ is the size of numbers), and it also runs in time $O(n)$.

Big O is only an upper bound on the running time. The algorithm also runs in $O(n^3)$, in $O(n\log n)$, in $O(2^n)$, and in $O(f(n))$ for many other (in fact, infinitely many) functions $f(n)$.


Shortest path tree from each vertex implies a unique MST? Given a connected, undirected graph G, edge-weighted (positive), prove that

If G has a spanning tree T which, for each vertex r in G, is a shortest path tree from r, then G has a unique MST.

I know how to show that given a T like that, it is also a MST, but how  can I show that it's unique? I tried to assume by contradiction that it isn't, but I can't see how to get a contradiction from that

Here is a hint:

   Pick any edge $e$ not in $T$. If you add $e$ to $T$, you will get a cycle. Can you show that $e$ is the unique heaviest edge in that cycle?

If you have seen the above hint, it is unlikely that you will not be able to complete what that hint ask you to do. In case you are still wondering what to do next, here is the hint for the next step.

   You are almost done! Can an MST contain the unique heaviest edge in any cycle?


Greedy Heuristics with an Altered Subset Sum/Partition Problem Say we have a constant-time function that accepts some integer set. The function outputs True if we can split the integers into two subsets of an equal sum. If we can't partition the integers given, the function outputs False.

Suppose we can use this function at any time, with any set of integers. Can we make a greedy algorithm using this function that will output one of the specific subsets that sum to half of a particular positive integer set?

The heart of the question:
If we know at any time the boolean result of canPartition() on any set of integers, can we greedily use that to output the specific values of a partition?

Suppose that a set $S$ of size more than 2 can be partitioned into two subsets of identical sum. One of these subsets contains at least two elements. If you merge these two elements (that is, replace them with a new element whose value is the sum of the values of the two elements), then the partition property still holds; and furthermore, given a partition of the new set, you can construct a partition of the original set.

You can find two elements in the same part by considering any three elements – two of them will be in the same part and so can be merged. This gives an algorithm for your problem with $O(n)$ oracle calls, where $n$ is the number of elements in the original set.


Weighted sum of last N numbers Suppose we're receiving numbers in a stream. After each number is received, a weighted sum of the last $N$ numbers needs to be calculated, where the weights are always the same, but arbitrary.

How efficiently can this done if we are allowed to keep a data structure to help with the computation? Can we do any better than $\Theta(N)$, i.e. recomputing the sum each time a number is received?

For example:
Suppose the weights are $W= \langle w_1, w_2, w_3, w_4\rangle$. At one point we have the list of last $N$ numbers $L_1= \langle a, b, c, d \rangle>$, and the weighted sum $S_1=w_1*a+w_2*b+w_3*c+w_4*d$.

When another number, $e$, is received, we update the list to get $L_2= \langle b,c,d,e\rangle$ and we need to compute $S_2=w_1*b+w_2*c+w_3*d+w_4*e$.

Consideration using FFT
A special case of this problem appears to be solvable efficiently by employing the Fast Fourier Transform. Here, we compute the weighed sums $S$ in multiples of $N$. In other words, we receive $N$ numbers and only then can we compute the corresponding $N$ weighed sums. To do this, we need $N-1$ past numbers (for which sums have already been computed), and $N$ new numbers, in total $2N-1$ numbers.

If this vector of input numbers and the weight vector $W$ define the coefficients of the polynomials $P(x)$ and $Q(x)$, with coefficients in $Q$ reversed, we see that the product $P(x)\times Q(x)$ is a polynomial whose coefficients in front of $x^{N-1}$ up to $x^{2N-2}$ are exactly the weighted sums we seek. These can be computed using FFT in $\Theta(N*\log (N))$ time, which gives us an average of $Θ(\log (N))$ time per input number.

This is however not a solution the the problem as stated, because it is required that the weighted sum is computed efficiently each time a new number is received - we cannot delay the computation.

Here is an elaboration of your approach. Every $m$ iterations, we use the FFT algorithm to compute $m$ values of the convolution in time $O(n\log n)$, assuming that the subsequent $m$ values are zero. In other words, we are computing
$$
\sum_{i=0}^{n-1} w_i a_{t-i+k}, \quad 0 \leq k \leq m-1,
$$
where $w_i$ are the $n$ weights (or the reverse weights), $a_i$ is the input sequence, $t$ is the current time, and $a_{t'} = 0$ for $t' > t$.

For each of the following $m$ iterations, we are able to calculate the required convolution in time $O(m)$ (the $i$th iteration needs time $O(i)$). So the amortized time is $O(m) + O(n\log n/m)$. This is minimized by choosing $m = \sqrt{n\log n}$, which gives an amortized running time of $O(\sqrt{n\log n})$.

We can improve this to worst-case running time of $O(\sqrt{n\log n})$ by breaking the computation into parts. Fix $m$, and define
$$ b_{T,p,o} = \sum_{i=0}^{m-1} w_{pm+i} a_{Tm-i+o}, \quad C_{T,p} = b_{T,p,0}, \ldots, b_{T,p,m-1}. $$
Each $C_{T,p}$ depends only on $2m$ inputs, so it can be computed in time $O(m\log m)$. Also, given $C_{\lfloor t/m \rfloor-p,p}$ for $0 \leq p \leq n/m-1$, we can compute the convolution in time $O(n/m + m)$. The plan therefore is to maintain the list
$$ C_{\lfloor t/m \rfloor-p,p}, \quad 0 \leq p \leq n/m-1. $$
For each period of $m$ inputs, we need to update $n/m$ of these. Each update takes time $O(m\log m)$, so if we spread these updates evenly, each input will take up work $O((n/m^2) m\log m) = O((n/m) \log m)$. Together with computing the convolution itself, the time complexity per input is $O((n/m)\log m + m)$. Choosing $m = \sqrt{n\log n}$ as before, this gives $O(\sqrt{n\log n})$.


Serving $k$ customers with bounded time window A person provides a service and he/she can serve $k$ clients each minute.
Now, client number $i$ comes at the beginning of minute $a_{i}$ and waits $w_{i}$ minutes to receive the service and if they don't receive the service in the interval $[a_{i}, a_{i} + w_{i}]$, they leave.
If we have $n$ clients, can the person serve all them or not?
My question: Does the above problem have a formal name? I want to write a python code for that but I don't know which keywords should I search?

The problem can be solved in $O(n \log n)$ time where $n$ is the number of clients  (Note that in the trivial case where $k > n$, you simply serve all clients as soon as they come.)
The algorithm is well-known: Sort the intervals by startpoint, endpoint.
Then you iterate over the intervals, for each minute.
If you are at a point where more than $k$ intervals end the next minute, you cannot solve it.
Otherwise you remove the $k$ first intervals in your list, and increase the minute counter.

Note that to be truly polynomial, you might need to skip further ahead than to the next minute, but that's an exercise.  (E.g. when the input is
$$\left[(2^0, 2^1), (2^2, 2^3), (2^4, 2^5), ..., (2^{100}, 2^{101})\right]$$
or other large numbers.)


Understanding the state vector in Quantum Computing I have just started to learn QC. It is said that

  The quantum state of $N$ qubits can be expressed as a vector in a space
  of dimension $2^N$

If there is $1$ qubit then we have two possible state vectors $|0\rangle$ and $|1\rangle$ or $(0,1)$ and $(1,0)$ respectively. Getting to $2$ qubits we have $4$ possible state vectors $(1,0,0,0), (0,1,0,0), (0,0,1,0), $ and $(0,0,0,1)$.
Note that in each case, all entries are zero except 1. The point I am trying to get to is that:

$2^N$ seems like a big space but given a vector in this space - all
    components will be zero except $1$. So there are only $2^N$ possible
    values the state vector can take.  Is this not correct? If not, why?
Why don't we say the space is $N$-dimensional. A $N$-bit string has $2^N$
possible values.

No, it's not correct.  It's not true in general that one entry will be 1 and all others 0; that is true for the basis vectors, but there are other states (other vectors) where that isn't true.  You can have linear combinations of the basis states, e.g., the following is a possible state:

$${1 \over \sqrt{2}} |0\rangle + {1 \over \sqrt{2}} |1\rangle.$$

It corresponds to the following vector in the vector space:

$${1 \over \sqrt{2}} (0,1) + {1 \over \sqrt{2}} (1,0) = (1/\sqrt{2},1/\sqrt{2}).$$

Because of this, you can have infinitely many possible states in this vector space.

The vector space is not $N$-dimensional.  The dimension of a vector space has a formal definition, and if you apply it, you will discover that the dimension of the vector space is $2^N$.


Fastest way to check if prefix of small string is substring of big string Let's say we have given 2 strings $A, B$, and let's suppose that the size of $A$ is pretty small (100 characters) and the size of $B$ is pretty big (1 million).

We define prefix of string $S$ as string $Y$ that contains the first $x$ letters (size of prefix always is less than or equal to size of whole string).

And the problem is to check for all prefixes of $A$, they are not too many if they are substrings of string $B$.

It is pretty slow if for each prefix we are traversing the whole string, is it possible to do something faster, maybe using string hasing?

Why would you need to traverse the big string for each prefix? Let's say A = "Some short string". So you traverse string B, looking for the letter "S". If not found, then no prefix of A is contained in B. If found, you found the prefix "S", and start at that point searching for "So". And so on.


How does Hoare's quicksort work, even if the final position of the pivot after partition() is not what its position is in the sorted array? All variable names are from Quicksort's wikipedia page's Lomuto's and Hoare's quick sorts pseudocode.

If p is what is returned by the partition function, Hoare divides his array from lo to p and from p+1 to hi, while Lomuto divides his array from lo to p-1 and from p+1 to hi.

I may be wrong about this, but Quicksort's philosophy is...

Take an element in the subarray (pivot).
Rearrange the subarray in such a way that all elements left of the pivot are smaller than the pivot, and all the elements right of the pivot are greater than the pivot.
Divide the array about the pivot. Repeat the process for the two smaller sub-subarrays. Keep doing this until you encounter an array with only one or less elements, because that is already sorted.

I find Hoare's partition to be more simpler to understand, than Lomuto's. Hoare's partition simply instructs us to start from the left end and the right end and to keep moving towards each other. If left marker encounters an element greater than the pivot, then the left marker pauses, and waits for the right marker to find an element smaller than the pivot. Then they exchange the elements, so that the left marker has the smaller element, and the right marker has the greater element. They keep doing this until they meet. Very straightforward.

Lomuto's partition, can be considered as a snake, of sorts, made of two parts, a head and a tail. The pivot is fixed (I usually take the last element as the pivot for Lomuto). The snake starts from the left-hand side, and stops just before the last element. When the snakes encounters an element smaller than the pivot, that element goes to the tail and the length of the tail increases. When an element greater than the pivot is discovered, that element goes to the head of the snake. Finally, the pivot is placed between the tail and the head. It's pretty clear but not as intuitive or efficient (in some cases) as Hoare's partition.

What confuses me is that Hoare's partition doesn't ensure that the position of the pivot after the partition has run its course, will be it's position in the final, sorted array. The only pattern that I could recognise in Hoare's partition was that i is at the final position of the pivot and that j is either i or i-1, j and i being the right and left markers.

Lomuto's partition, however, guarantees it. So, when I step back and look at the bigger picture, it makes sense for Lomuto to divide the array from lo to p-1 and from p+1 to hi. But, I can't understand how Hoare can divide his array from lo to p and from p+1 to hi, make up for his partition not putting its pivot in its rightful place.

I've been looking into examples and sorting arrays myself via Hoare's quicksort. I think I've found another interesting pattern in Hoare's partition algo. Which may explain why Hoare's method works. Lomuto divides the array into three parts; elements smaller than the pivot, the pivot, elements greater than the pivot. I think Hoare looks at things differently. He divides the array into two parts; elements smaller than the pivot, elements equal to or greater than the pivot. One of the traps that I fell into was that Lomuto's partition returns the final position of the pivot, whereas Hoare's partition returns the position just before the final position of the pivot. This is why Lomuto then quick sorts from lo to p-1, whereas Hoare quick sorts from lo to p. Another inference that can be drawn is that if Hoare's partition returned i instead of j, we'd then divide the array into two parts- from lo to i-1 and from i+1 to hi, just like Lomuto did. And it only took me 4 hours to understand that.


Merging Sorted lists using Heap Data Structure Suppose there are $\lceil\log n\rceil$ sorted lists of $\lceil\frac{n}{\log n}\rceil$ elements each. The time complexity of producing a sorted list of all these elements is:  (Hint: Use a heap data structure)

$O(n \log \log n)$
$θ(n \log n)$
$Ω(n \log n)$
$Ω(n^{\frac{3}{2}})$

My approach:

I know complexity of heap sort is $O(n \log n)$. But little bit confused form where to start.

Hint: Try to merge the lists in the correct way, using the fact that merging lists of size $m_1,m_2$ costs $O(m_1+m_2)$. If you do this correctly, you will obtain an $O(n\log\log n)$ algorithm.

We can also get a matching lower bound. The number of possible answers is
$$
\begin{align*}
\frac{n!}{(n/\log n)!^{\log n}} &\sim
\frac{\sqrt{2\pi n}(n/e)^n}{\sqrt{2\pi n/\log n}^{\log n}(n/e\log n)^n} \\ &\sim
\frac{(\log n)^{\log n}}{\sqrt{2\pi n}^{\log n-1}}(\log n)^n.
\end{align*}
$$
The dominant term here is $(\log n)^n = \exp(n\log\log n)$, and we get an $\Omega(n\log\log n)$ lower bound in the decision tree model.


What is the constant $C$ in the definition of asymptotic notations? For example in the definition of $\Theta$:

  $f(n) = \Theta(g(n)$ if there exist positive constants $c_1, c_2$ and $n_0$ such that
  $$ 0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \text{ for all } n \geq n_0. $$

I was scratching my head for two weeks since we took this definition in class. Why do we need this constant anyways? Shouldn't we get rid of all constants because they aren't significant?

Why can't we just say $g(n) \leq f(n) \leq g(n)$?

The basic idea of asymptotic notation is that "constant factors shouldn't matter". This has several different interpretations. Taking as our example big O, the simplest interpretation is:

  For all $C,D>0$ and functions $f,g$: $$ f = O(g) \Longleftrightarrow Cf = O(Dg). $$

This means that big O should be scale-invariant, that is, it should treat the functions $f$ and $Cf$ exactly the same. Stated differently, if $f_1,f_2$ differ by a constant factor, then $f_1,f_2$ should be treated the same.

In practice, the condition "$f_1/f_2=\text{const}$" is too restrictive. Instead, we would like to treat two functions $f_1,f_2$ in the same way as long as $f_1/f_2$ is bounded, that is, as long as $C_1 \leq f_1/f_2 \leq C_2$ for some constants $C_1,C_2>0$. That is, we would like that

  For all $C_1,C_2,D_1,D_2$ and functions $f_1,f_2,g_1,g_2$ satisfying
  $C_1 \leq f_1/f_2 \leq C_2$ and $D_1 \leq g_1/g_2 \leq D_2$:
  $$
f_1 = O(g_1) \Longleftrightarrow f_2 = O(g_2).
$$

You can check that the definition of big O satisfies this invariance property. The constant in the definition of big O ensures that. Indeed, while $2n \leq n$ doesn't hold, $2n = O(n)$ does hold.

The integer constant – $N_0$ – in the definition of big O isn't really necessary. It is there so we can accommodate functions which aren't positive or aren't even defined for small $n$. If your functions aren't pathological in that sense, then you can do away with $N_0$.

For these non-pathological functions (extended to non-integer points), the various asymptotic notations have equivalent definitions in terms of limits:

$f = O(g)$ if $\limsup_{n\to\infty} f(n)/g(n) < \infty$.
$f = \Omega(g)$ if $\liminf_{n\to\infty} f(n)/g(n) > 0$.
$f = \Theta(g)$ if both these conditions hold.
$f = o(g)$ if $\lim_{n\to\infty} f(n)/g(n) = 0$.
$f = \omega(g)$ if $\lim_{n\to\infty} f(n)/g(n) = \infty$.


Does any language need to have a bottom type? From wikipedia:

In type theory, a theory within mathematical logic, the bottom type is the type that has no values. It is also called the zero or empty type, and is sometimes denoted with the up tack (⊥) symbol.

The "bottomest" types I can think of in js are undefined and null, both unity types.
Notice how in TypeScript there is the explicit never bottom type for function that are not supposed to return anything, or to always throw an exception.
The question is/are:

does JavaScript have no bottom type?
if so, does that mean that languages do not need to have a bottom type?

Javascript has no bottom type. It does not even really have types in the sense of type theory. Instead, values are tagged with information that is called "dynamic type".
Programming languages typically do not have the bottom type (it is also called the empty type) because they allow defintion by general recursion, which implies that all types are non-empty. For example, to define a value v of any type T in Java, we can do this:
static T f() { return f(); }
static T v = f();


Finding corresponding node in a duplicate binary-tree Given two duplicate binary trees (see the embedded picture), you are given a node in Tree A, find the same corresponding node in Tree B.

I believe the optimal approach should be traversing both trees at the same time, and when you reached the node in Tree A, you would know you have also reached the same node in Tree B.

Code example to solve this issue would be appreciated.

I'm not going to provide a code example.
Your approach would work, and takes time proportional to the size of the tree (i.e., its number of vertices) in the worst-case. This can be improved to only take worst-case time proportional to the depth of the vertex of interest.
If the tree is balanced, there would be an exponential difference in the running times.

Keep track of the path from the node of interest to the root $r$ of Tree $A$. In particular, for each node  $x \neq r$ of the path, push into a stack $S$ either $L$ or $R$ depending whether $x$ it is the left or right child of its parent.

Then, start from the root of Tree $B$, iteratively pop from a value $y$ from $S$ and move to the left or right child depending on whether $y=L$ or $y=R$, respectively. The node you're at when the stack is empty is exactly the node you're looking for.


How does taking modulo 1 make sense? I need some help understanding the problem statement in CLRS 11.3-4 pg 269.  It says:

  Consider a hash table of size $m = 1000$ and a corresponding hash function
   $ h(k) =\left \lfloor m(kA \bmod 1) \right \rfloor $
  for $A = (\sqrt5 - 1)/2$. Compute the locations to which the keys
  61, 62, 63, 64, and 65 are mapped.

Is $\mod 1$ a misprint in my copy? Also $A$ is a real number.  Is modulus defined for non-integer numbers?

That's not a misprint.  $kA \bmod 1$ makes sense.  For instance, $37.239 \bmod 1 = 0.239$.


Gas Station problem : Fixed path variation Given a set of cities where you need a certain amount of fuel to travel from one city to another, each city has a different fuel price and you can only load K amount of fuel to the vehicle. The path is fixed (ie) you have to go from C1 to Cn through C2, C3,.. and so on. The objective is to fill fuel in these cities in such a way the spendings on fuel is minimized. I thought about storing the minimum prices within a window whose requirements add up to K and then find the minimum cost required to traverse. I'm not sure how it holds up or is it even right in the first place. What if being greedy and filling up fuel to reach the city empty till you reach the closest city with cheaper fuel, not the optimal solution? How do i prove that it is?

The greedy strategy works in this case (fill up as much as you need to reach the next cheaper city, or fill up to K if no cheaper city is reachable with a full tank).

The proof is pretty much the same as most standard proofs for greedy algorithms: Among all optimal solutions, take the one that "agrees with the greedy strategy the longest" and show that this solution is in fact identical to the greedy one (to understand why this almost always works, you can read up on matroids and see how the standard proof is done in this case).

Informally, in this case :

Call GS your greedy strategy and let OPTS be an optimal strategy which agrees with GS for the longest time, starting from the beginning. Suppose GS and OPTS differ in strategy for the first time in city C:

If OPTS fuels up more than GS at this point, then that means that GS fueled up just enough to reach the next cheapest city C'. It is clear that OPTS will arrive in C' with more fuel than GS (more than 0). But GS can then fill its tank up to as much as OPTS (for cheaper than OPTS could have at any point between C and C'). We can thus construct an optimal strategy OPTS' which does what GS does up to C' and then copies OPTS. But OPTS' is optimal and "agrees with GS" for longer than OPTS, which is impossible by definition of OPTS. So it is impossible that OPTS fuels up more than GS in C.
If OPTS fuels up less than GS in C, then let C' be the next city where OPTS is gonna fuel up. C' can not be cheaper than C, otherwise GS would have filled up just enough to get there and OPTS would have had to fuel up at some point between C and C'. So C' is as least as expensive as C, and filling up in C would not have been worse for OPTS. We can once again construct a new strategy OPTS' which contradicts the definition of OPTS. So it is impossible that OPTS fuels up less than GS in C.

Putting both together, we see that there can not be a "first disagreement point" between GS and OPTS. Thus, GS = OPTS, and GS is an optimal strategy.


Can a heap have no elements? Is it correct to call something with no elements a binary heap? I think it is correct, for one element too, but I'm not sure. It seems to satisfy the definition (from Wikipedia):

  Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.

  Heap property: the key stored in each node is either greater than or equal to or less than or equal to the keys in the node's children, according to some total order.

It's up to you to decide. It's a pathological case which is quite similar to the empty graph (on zero vertices) — sometimes it makes sense to admit it, and sometimes not. It depends on the circumstances. The definition in Wikipedia is irrelevant here — there are many other similar definitions in the literature, that might disagree on this point.

I recommend the classic article Is the null-graph a pointless concept by Harary and Read.


Does making the keys of a hashtable the same length make the hashtable any better? The question popped up in my head. The hash function used is Murmur3.

It makes the hash table unusable if I can’t have x and yz and abc as keys.


Efficient Algorithms for Complex Networks Most standard works on random graphs focus on $G_{n,p}$ and random regular graphs. However, such models are far from a good abstraction to describe the types of networks that one typically encounters in the real world.
There are several simple models that mimic the behavior of real-world graphs, sometimes called Complex Networks.
There are many graph problems that become easier in the setting of $G_{n,p}$, such as finding a Hamiltonian path, finding a perfect matching, etc. I am sure that similar work has been done for random complex networks, but I haven't been able to find a good book or survey paper on the subject. I must be using the wrong terminology.
I would be grateful if someone could point me towards something like that, or tell me what the subject of efficient algorithms for complex networks is called in the literature.

There are currently serious efforts devoted to algorithms taking into account usual properties of complex networks, either in their design (use these properties to be efficient) or in their analysis (show that, if the input graph has these properties, then the algorithm has low complexity).
Since most complex networks met in practice are sparse, let me first say that any complexity expressed in terms of the number of edges (instead of the squared number of vertices) is of interest in this context. But I do understand that you actually have more advanced complex network properties and complexity analysis in mind.
My 2006 paper about triangle counting and listing provides a good illustration, I think. There, I used the fact that most complex networks met in practice have very heterogeneous degrees. I proposed a very simple algorithm makes a distinction between low- and high-degree vertices, and proved its algorithmic complexity as a function of the graph degree distribution.
Many such examples exist in the literature. For instance, the arboricity and core value have been used to enumerate $k$-cliques. However I am not aware on any survey devoted to them.


Turing Recognisable => enumerable I get the proof of going from an enumerator to a Turing Machine (keep running enumerator and see if it matches input) but I don't see how the other way works.

According to my notes and the book (Intro to the Theory of Computation - Sipser), to get Turing enumerator from a Turing machine, we basically write all combinations of the alphabet. You then run the TM on this input, if it accepts print it out, replace with new string repeat ad infinitum.

The problem I am having is surely this requires the language to be decidable. Otherwise it might get stuck on the third word in some infinite loop doomed never to accept or reject and certainly never print out the whole language.

What am I missing?

What's missing is the way you run the Turing Machine $M$ on strings to get the Enumerator. Rather than generate each string, run $M$, and then output this string if the $M$ accepts – which as you identified will not work – you do something like the following, which
adopts the
 strategy of simulating many instances of the $M$ on different strings "in parallel".

Assume the tape has contents
$\langle w_1,  S_1\rangle \# \cdots \# \langle w_n, S_n\rangle$,
where $w_i$ is some word under consideration and $S_i$ is the current state of $M$
operating on $w_i$. This represents that $n$ copies of $M$ are being simulated. $w_i$ is stored so we know what the original input was.

Now run the following loop

At the end the tape write the next string from $w\in\Sigma^*$, along with the
initial configuration $S$ of $M$, that is, write $\# \langle w, S\rangle$.
Simulate each copy of the $M$ on the tape for one step. (Presumably use another tape.)
If any of the $M$s enters an accepting state, put the corresponding string onto the output tape. Remove this instance of $M$ from the tape.
If any of the $M$s enters a rejecting state, remove that instance of $M$ from the tape.
Goto step 1.

It is not hard to argue that all strings $w\in\Sigma^*$ accepted by $M$ will eventually be output on the tape.


Example of worst case input for Build-Max-Heap What would be an example of a worst-case input for Build-Max-Heap?  What would the "shape" of it "look like"?  I'm having trouble getting a feeling for it.

Think of a heap as a tree, not its array implementation.

Building a heap work bottom-up. Working from the lowest levels up to the root we add the keys one by one. Worst case is when each key moves as much as possible, so all the way to the level of leaves.

This should start getting the picture.


Dynamic programming for graph splitting I have a directed graph which has edges between every vertices $i$ and $j$ such
that $i < j$ and the edge is from i->j and every vertex needs to be visited.  I need to divide the graph into two parts such that the
travel distance on both the parts i.e. sum of edge weights while traveling from the lowest index to the highest index in each of the group is minimum.  For example there is a graph
of 4 vertices where each edge weight is the following

$w(1, 3) = 2$
$w(1, 4) = 1$
$w(3, 4) = 3$
$w(1, 2) = 100$
$w(2, 3) = 100$
$w(2, 4) = 100$

The solution would be $\{2\}, \{1, 3, 4\}$. In the first group {2} doesn't have any vertex so no edges between any of the vertices in that group. In the second group we travel from 1->3 and 3->4 so the edges we travelled would be 2 + 3. Hence the ans would be 0 (from the first group) + (2+3) (from the second group). We start from the lowest index vertex and move to the highest index vertex as the edges are from lower index to higher index vertex.
The algorithm I came up was a brute force i.e. considering each
combination and return the minimum of it i.e. to take one vertex in one
group or include in other which leads to complexity $O(2^n)$.
I want to get the above problem to run in $O(n^2)$ solution.  I did draw
a decision tree for the above problem and can see nodes being overlapped
i.e. $\{1,2\}, \{3,4\}$ and $\{3,4\}, \{1,2\}$ so I figured this is a
dynamic programming problem but I am not able to define the states.
Edit - It can be done using a 1d dp array

I don't have a dynamic programming solution but this problem can be efficiently reduced to a minimum weight max-flow problem.
Let $G$ denote your original graph. We will create an instance $(s,t,G')$ of the minimum weight max-flow problem as follows:

Let $W$ denote the sum of all weights in $G$ plus one.
For every vertex $u$ in $G$, we create two vertices $u_{in}$ and $u_{out}$ in $G'$ and add a directed edge from $u_{in}$ to $u_{out}$ with weight $-W$ and capacity $1$.
For every directed edge $e=(u,v)$ in $G$, we add a directed edge from $u_{out}$ to $v_{in}$ in $G'$ with weight $w(e)$ and capacity $1$.
We create a vertex $s'$ and we connect the source $s$ to $s'$ with a directed edge of weight $0$ and capacity $2$.
We connect $s'$ to every "in" vertex with a directed edge of weight $0$ and capacity $1$. We  connect every "out" vertex to the sink $t$ with a directed edge of weight $0$ and capacity $1$.

Let $n$ denote the number of vertices in $G$. Then the vertices in $G$ can be partitioned into two vertex-disjoint paths of total weight $k$ (which is what you want) if and only if there is a max-flow in $(s,t,G')$ with total weight $k-nW$. Moreover, this flow is the union of two paths in $G'$ (which are disjoint except at $s$, $s'$ and $t$) , from which you can easily retrieve the two vertex-disjoint paths in $G$.
Note that by changing the capacity of the $(s,s')$ edge from $2$ to whatever integer we like, we can generalize this approach to partitioning into arbitrary number of vertex disjoint paths with minimum total weight.


Approximation algorithms for NP-complete problems Given two NP NP-hard functional problems, A and B, one can find a reduction of A to B. Is it possible to find a reduction that would honour approximations? That is, if you have an approximation algorithm for B that yield approximate solutions within accuracy $\delta$, is it possible to reduce A to B in such a way that one would be able to derive an approximate solution of A within accuracy $\epsilon = \epsilon(\delta)$?

It depends on the problems. Some NP-complete problems are in APX (can be approximated to some constant amount) and some are not. This shows that you cannot in general assume the existence of a transformation such as the one you mention; this is spelled out here.

A concept somewhat similar to what you mention is APX-hardness. First, some definitions. APX, as mentioned, is the class of problems approximable to some constant in polytime. PTAS is the class of problems which can be approximated arbitrarily well in polytime. A problem is APX-hard if there is a "PTAS reduction" (approximation-preserving reduction) from every problem in APX to that problem. One problem which is APX-hard is MAX-SAT.

A related definition is MaxSNP. This is a class of graph problems with the following property: there is a PTAS reduction from every problem in APX to some problem in MaxSNP.


Data Structure - Array of Array Suppose that we have a family $F=\{a_1,\dots,a_s\}$ of sorted arrays
to merge. Our strategy is to choose two of them, say $a_i$ and $a_j$,
remove them from $F$, merge them and put the resulting array back into
$F$; we keep doing that until there is only one array in $F$. We will
use a greedy strategy: at each step, we choose $a_i$ of minimal length
in $F$, and $a_j$ of minimal length in $F-\{a_i\}$.

What data structure would you use to store $F$?

Obviously, I assumed F $F$ be an array of array as each element of F is an array of integers.

However, I think it is asking about Abstract Data Structures that were taught at a class. We are taught about Priority Queue ADT, Stack ADT, Queue ADT, and heap so far.

Can F be one of them? If so, please explain why F can be such structure.

Thank you,

You would like to have the ability to extract the minimal array (in terms of length), then extract the next minimal, merge them, and insert them back to the data structure.

Since you want the best performance possible, you now would like to ask yourself how much each operation would cost?

If you use a stack you would have the option to $pop$, which is good if you assume your stack is given you with the arrays already sorted by length (will be $O(1)$). So, you will be able to $pop$ the first two arrays and then merge them. But now, what will you do with the merged array? You have no guarantee that the new array is indeed the shortest one. A simple queue won't do as well.

So, a better option would be to use a priority queue, implemented as a heap. You will have a heap where the values are the length of the arrays. To get the two shortest array you will use $extract-min$. You can use Fibonacci heaps which will give you $O(\log n)$ amortized for extraction. Next, after merging the arrays you can insert it back with $O(1)$ amortized time complexity.

*Note that the complexity times I wrote here are disregarding the length of the arrays themselves. I treated them as simple elements for simplicity, since the question focuses on the use of the data structure.


is there a constructive proof of the existence of a language which isn't recursive (without invoking infinities)? My understanding is that a language cannot be decided if the language is actually infinite (not generated by any machine). However, actual infinites make me squirm. Is there any reason to believe in semi-decidable or undecidable languages other than a belief in actually infinite sets?
A positive answer to this question would confirm that there are, in fact, some Machines which present an insurmountable problem for decidability.
Edit: Still not resolved. Both answers use impredicative logic or prove something irrelevant.

We can write a computer program that will enumerate all halting computer programs. It seems that you are happy to accept accumulating the output of program into a (potentially infinite) set. Thus, you accept "all halting computer programs" as a valid set. It is, however, not a decidable set.
The standard proof of the undecidability of the Halting problem is constructive. Since we are proving a negative statement, a constructive proof is going to start with the assumption that it were decidable and going to derive a contradiction. Note that a decider by definition will answer either "yes" or "no" on any input, we can thus do the case-distinction in the usual proof of the undecidability of the Halting problem without having to involke the law of excluded middle.
Alright, so let us have a look at how exactly to prove that the Halting problem is undecidable. Bob claims the Halting problem is decidable, and we prove him wrong. Since Bob claims decidability, we can make him tell us what program he thinks does the job. Bob has to give us a program D, and the assurance that on any input w, the computation D(w) will halt and answer either "true" or "false".
Now, consider the following program:
E(input s)
   While {D([s]('s')} {do nothing}
   halt

Here, with $[s](`s')$ I mean "consider s as a program, and apply this program to the input given by s considered as a string". This may feel weird, but since we have received s, we can obviously copy it and so on.
Now, modulo knowing what D is (and that's Bob's responsibility, not mine), we have a concrete piece of code up there. Call that piece of code "e". We can again treat e both as a program (which takes an input) and as a string. In particular, it makes sense to consider $[e](`e')$ again, which is the program e run on the string e as input.
Bob has claimed that running $D([e](`e')$ will answer either true or false, and that this answer is about whether the computation $[e](`e')$ ever halts. Since Bob so kindly provided the case distinction for us, we can exploit it.
If $D([e](`e')$ answers "true", then in the computation that happens when we run E('e') we can never escape the while-loop, so it can't halt. Bob is wrong.
If $D([e](`e')$ answers "false", then E(`e') never enters the loop, but halts straight away. Bob is wrong, again. We won.


How to trigger a thread to start working using semaphore? How to trigger a thread to start working using semaphore?

I have find a lot of explanation about thread and semaphore but i still don't understand, any help please

When using semaphores or locks, you don't do anything else than acquiring the semaphore (resp. the lock), and then do what you want.  For example, if you want to use a lock, then you typically have two threads

# thread 1
lock.acquire()
# here is all the work for thread 1
lock.release()

and the other thread is completely identical:

# thread 2
lock.acquire()
# here is all the work for thread 2
lock.release()

Now, the first to obtain the lock gets to run the code first, and the other thread needs to wait until the lock is released.

Here's an example of a Python program that prints a series of 0s and 1s depending on the order of execution:

import time
import threading

lock = threading.Lock()
lst = []

def f1():
    for i in range(10):
        lock.acquire()
        lst.append("0")
        lock.release()
        time.sleep(0.1)

def f2():
    for i in range(10):
        lock.acquire()
        lst.append("1")
        lock.release()
        time.sleep(0.1)

t1 = threading.Thread(target=f1)
t2 = threading.Thread(target=f2)
t1.start()
t2.start()
t1.join()
t2.join()

print("".join(lst))

Feel free to run it in your own terminal.

(Note that I used lock.acquire() and lock.release(), but the "correct" way is to use a context manager and use with lock: ....)

See also:  Lock, mutex, semaphore… what's the difference?


Can we say DFA is more efficient than NFA? I just started reading about theory of computation. If we compare which is more powerful (in accepting strings), both are same. But what about efficiency ? DFA will be fast compared to NFA, since it has only one outgoing edge & there will be no ambiguity. But in case of NFA we have to check all possible cases & that surely takes time. So can we say DFA is more efficient than NFA ?

But, my other part of brain is also thinking that NFA exists only in theory, so we cannot compare it's efficiency with DFA.

There are two answers, depending on how you define efficient.

Compactness of representation

Telling more with less: NFAs are more efficient.

Converting a DFA to an NFA is straightforward and does not increase the size of the representation.

However, there are regular languages for which the smallest DFA is exponentially bigger than the smallest NFA. A typical example is $(a|b)^*b(a|b)^k$ for $k$ fixed.

Computation

Running it fast: DFAs are more efficient.

The computers we use today are deterministic in nature. That makes them bad at dealing with non-determinism. There are two common ways of dealing deterministically with NFAs: backtracking on one side, which is rather costly, or keeping track of the active states, which means each transition will take up to $N$ times longer (where $N$ is the size of the NFA).


Derive a while loop runs in $\Theta( \sqrt{n} )$ I know for a fact that algorithm A runs in $\Theta(\sqrt{n})$, but how does one derive that fact?

Algorithm A

i = 0
s = 0
while s <= n:
    s += i
    i += 1

Here is what I am thinking. We know that A is upper-bounded by O(n), as we increment $s$ by more than 1 in each iteration. We also know that it must be lower-bounded by $\log n$, as we increment $s$ with by something less than $2^i$ in each iteration. (Correct me if I am wrong, these are just my thoughts ...).

Now, what else can we say about A? How do we derive that its time complexity is $\Theta(\sqrt{n})$?

Each time add $i$ to $s$ and increase $i$ by one, up to reach to $n$. Hence, if you find the $k$ such that $s = 0 + 1 + 2 + ... + k$ be equal to $n$, you can find the number of running loop. As $1 + 2 + \ldots + k = \frac{k(k+1)}{2}$, you need to solve this equation $\frac{k(k+1)}{2} = n$.

$$k^2 + k -2n = 0 \Rightarrow k = \frac{-1 + \sqrt{1+8n}}{2} = \Theta(\sqrt{n})$$


Remove divisors from a set of integers I have a set $S$ of integers.  I want to remove all elements of $S$ that are divisors of another element of $S$.  In other words, I want to compute $T = \{y \in S : \forall d \in S . d \nmid y \}$.

How do I do this efficiently?

I can see how to do it in $\Theta(|S|^2)$ time, by examining all pairs of elements of $S$ and keeping only the ones that don't have any divisor in $S$.  Can it be done substantially faster?  (For simplicity, I'm willing to assume that all standard integer operations---addition, multiplication, division, etc.---can be done in $O(1)$ time.  Yes, I know this is an imperfect approximation, but if it makes your answer cleaner, I'm fine with it.)

Let me first repeat my remark: in the application you have in mind (finding the maximal LCM of a partition of $n$), you can assume that the elements of $S$ come factored, and so can represent them as vectors of non-zero integers corresponding to the powers of the various primes. The problem of computing all maxima in this setting has been considered by Kung, Luccio and Preparata, but they only give efficient algorithms in the case when the dimension (number of different primes) is constant, which is not your case. They also give a lower bound of $\Omega(n\log n)$. The problem has took up in the database literature under the name of Skyline - perhaps these people have practical algorithms which could be useful here.


Grammar that numbers of letters `c` is greater than number of letters `b` Exactly as stated in the subject. I look for grammar which use letters $a, b ,c$ that numbers of letters $c$ is greater than number of letters $b$.

Example: $acbccba$ is generated by the grammar.

I thought about:

$S \rightarrow aS \mid bS \mid SCS$

$ C \rightarrow cb \mid ca$

but not sure if it works. Could you help me, please.

Your grammar never accepts a word since you can't make the $S$ disappear.

If you want to create more $c$ than $b$ you just have to make sure that when you create a $b$ you create a $c$ with it (but be careful they don't need to be side to side). You can also generate as much $a$ or $c$ as you want.

If you need more indication please ask.


Is this language regular? Consider the following language:
$$ L_1=\{uu^rv \mid u,v\in\{0,1\}^+\}.$$
that means that neither $u$ nor $v$ can be $\varepsilon$. As usual $u^r$ refers to $u$ reflected.

I think that this language is not regular, but i am not sure. Any ideas?

Nice question. It is not regular.

Notice that this language consists of words where some nonempty prefix is an even palindrome.

Intersect $L$ with $(01)^{+} (10)^{+}$. If a word of this form has a palindromic prefix: $(01)^n (10)^m = u u^R v$ and $u \neq \varepsilon$, then the center of palindrome must be between the group of $01$ and the group of $10$. For example, take the word $0101011010101010$. The only possibility of breaking a prefix into a palindrome is $(010101\cdot 101010)\cdot1010$. (I leave the proof of this statement to you.)

Therefore, $L \cap (01)^{+} (10)^{+}=\{(01)^n (10)^m : m > n \geq 1\}$. However, this language is not regular - for example, each prefix $(01)^n$ is in a different Myhill-Nerode class.


NFA - string acceptance (decision problem) test I am interested in testing for a given string (w) whether it is in the language (L) defined by a nondeterministic finite automaton (A). I have some blurry point in my mind.

What is the complexity of this test by using the NFA and backtracking? Assume my NFA has m states and string (w) has length n (|w| = n). For regular expressions, by using Thompson's algorithm, the resultant NFA has the same complexity (worst case) if I use backtracking?

What are the methods/algorithms other than backtracking and converting to DFA?

A naïve backtracking algorithm will still result in exponential behaviour ($O(2^{n})$ where $n$ is the length of the input string). This behaviour can occur even with very small automata (i.e. where the number of states $m$ is a fixed constant).

Consider for example the NFA $M$ below:

The alphabet is simply $\Sigma =\{0\}$, and the language is $L(M) = \{0^{k}\mid k \in \mathbb{N}\} = \Sigma^{\ast}$. If our algorithm chooses poorly for even the first step (for example if we use the obvious choice and go by state ID), then we're stuck between $q_{0}$ and $q_{1}$, where at each point in the input, we have the choice of moving to the opposite state, or staying where we are - i.e. a binary choice for each character, for the entire length of the string, giving $2^{n}$ steps before we manage to backtrack to $q_{2}$ and then move along the correct path to $q_{4}$.

So even with only 4 states and where every string is valid, we can still get terrible performance from a backtracking approach.

There is a much better approach however. Even without converting the NFA to a DFA we can decide acceptance in polynomial time. As we are dealing with a regular language, we don't need to remember the entire computation history up to this point (which is what backtracking does), we only need to know what state we are up to at the current point. In a DFA this is very easy, as we can only be in one state at any point, but an NFA (without knowing the final computation path) allows more possibilities. However we can simply keep track of these possibilities. The algorithm is as follows:

Initialise $S_{0}$ to $\{s_{0}\}$ where $s_{0}$ is the start state.
For each symbol of the input $c_{i}$ with $1 \leq i \leq n$, for each state $s \in S_{i-1}$, let $E(s,c_{i})$ be the set of states reachable from $s$ using $c_{i}$ and any number of $\varepsilon$-moves1. Set $C_{i} = C_{i} \cup E(s,c_{i})$.
If there is an accepting state in the set $C_{n}$, return $\mathrm{YES}$, otherwise return $\mathrm{NO}$.

So all the algorithm is really doing is keeping track of all the states we could be up to after having read $k$ symbols from the input.

Assuming that the NFA is fixed, this algorithm is $O(n)$-time in the length of the input string. If the NFA is part of the input, it's a little more complicated, but still polynomial time - $O(m^{2}n)$ where $m$ is the number of states (if I haven't missed an implicit loop in there).

Footnotes.

That is, we take the $\varepsilon$-closure of the state $s$, then from each of these states see if we can move using symbol $c_{i}$, then for those where we can, we take the $\varepsilon$-closure again, and this gives us $E(s,c_{i})$.


Restricted traversal on an undirected graph Given a undirected graph $G=(V,E)$.

Imagine traversing the Graph was restricted; following an edge $a$ over a node $v$ to an edge $b$ is allowed if and only if a function $w: ( a, v, b ) \rightarrow \{0,1\}$ returns $1$.

Is there a effective solution to find the shortest path between two nodes without trying every possible path on the graph? (Since without visiting every node from every possible direction it is not guaranteed to follow every edge that might exist. Also, just remembering if a node has been already visited nor not does not fit anymore since there might be other leaving edges allowed to take - depending on the incoming edge that had been taken. )

Also, is there a more common formulation of this problem (e.g. “restricted traversal”) ?

Yes, here's an algorithm for that.  Construct a new graph $G' = (V\times V, E')$ where you have an edge $(u,v) \to (v,w)$ for each triple of vertices $u,v,w \in V$ such that $(u,v) \in E$, $(v,w) \in E$, and $w((u,v),v,(v,w))=1$.  Now look for the shortest path in $G'$.  This graph basically keeps track of the current node and the previous node; the node $(u,v)$ in $G'$ corresponds to a traversal in $G$ where the current node is $v$ and the previous node was $u$.

If you know finite automata, this is basically a product construction (parallel composition).


Relative primality is primitive recursive How do I prove that the predicate $P(x , y)$ is primitive recursive, where $P(x,y)$ holds if $x,y$ are relatively prime?

Two numbers $x,y$ are not relatively prime iff there exists some common factor $a > 1$, which divides both $x$ and $y$. This common factor can be bounded by $a$. Therefore $x,y$ are not relatively prime iff there exist $a,b \leq x$ and $c \leq y$ such that (i) $a \geq 2$, (ii) $x = ab$, and (iii) $y = ac$.


Solving a two-variable recurrence I've written a function. I believe the function runs in complexity:

$$  T(m, n) = \begin{cases}
              T(m-1, n) + T(m, n-1) + T(m-1, n-1) + 1 &\text{if $m,n>0$}\\
              0 &\text{otherwise}
              \end{cases}
$$

I have no idea how to simplify this. Can anyone help?

(No, this is not a homework assignment. Well, writing the function was, but after writing it I'm certain that I wrote a very inefficient implementation and am trying to figure out just how bad my version really is.)

Let $P = \sum_{n,m \geq 0} T(n,m) x^n y^m$. We have
$$
\begin{align*}
P &= \sum_{n,m \geq 1} T(n,m) x^n y^m \\ &=
\sum_{n,m \geq 1} [T(n-1,m) + T(n,m-1) + T(n-1,m-1)+1] x^n y^m \\ &=
\sum_{n \geq 0, m \geq 1} T(n,m) x^{n+1} y^m + \sum_{n \geq 1, m \geq 0} T(n,m) x^n y^{m+1} + \sum_{n,m \geq 0} T(n,m) x^{n+1} y^{m+1} + \sum_{n,m \geq 1} x^n y^m \\ &= (x+y+xy)P + \frac{xy}{(1-x)(1-y)}.
\end{align*}
$$
We deduce that $(1-x-y-xy)P = xy/(1-x)(1-y)$, and so
$$
P = \frac{xy}{(1-x)(1-y)(1-x-y-xy)}.
$$

At this point we could invoke multivariate asymptotic analysis, but instead we'll connect $P$ to the Delannoy numbers $D(n,m)$, which follow a similar recurrence $D(n,m) = D(n-1,m) + D(n,m-1) + D(n-1,m-1)$, with base case $D(0,0) = 1$. These numbers have generating series $Q = 1/(1-x-y-xy)$. Our formula above shows that
$$
P = \frac{x}{1-x} \frac{y}{1-y} Q = \sum_{n,m \geq 1} x^n y^m Q,
$$
and so we obtain the formula
$$
T(n,m) = \sum_{n'<n,m'<m} D(n',m').
$$
This formula can also be derived directly in various ways.

Pemantle and Wilson shows that when $n,m \to \infty$ and $n/m,m/n$ are bounded,
$$
D(n,m) \sim \frac{nm}{\sqrt{2\pi}(n+m-\sqrt{n^2+m^2})^2\sqrt{n^2+m^2}} \left(\frac{m}{\sqrt{n^2+m^2}-n}\right)^m \left(\frac{n}{\sqrt{n^2+m^2}-m}\right)^n
$$
This should be compared to the similar frightening formula for the binomial coefficients,
$$
\binom{n+m}{m} \sim \sqrt{\frac{n+m}{2\pi nm}} \left(\frac{n+m}{n}\right)^n \left(\frac{n+m}{m}\right)^m.
$$
The asymptotic formula for $D(n,m)$ can probably be used to come up with an asymptotic formula for $T(n,m)$, or one can do the asymptotic analysis directly using the same methods, but I doubt that it would be very useful.


Searching a value in a "piecewise" ordered array If we have an array $A$ of length $N$, which is partitioned into $\sqrt{N}$ adjacent subarrays $A(i)$, each of which is monotonically ordered from $\min(i)$ to $\max(i)$ (it is known what places have those bounds in A for each subarray), with the following conditions:

min(i) < min(i+1),
max(i) < max(i+1),
min(i+1) < max(i),
If subarrays A(i) and A(i+1) both have the j-th element, then A(i,j) < A(i+1,j),
The number of elements in subarray A(i) is strictly increasing with i

Would it be possible to search an element in the array $A$, in time $O((\log N)^k)$, for a positive $k$?  If yes how?

If not, what kind of minimal additional conditions would allow that?

Edit. The subarrays are not necessarily of equal length.
They are strictly increasing. The above stated conditions are always guaranteed.

What I have tried so far is to binary search them separately, but that is obviously going to be very inefficient.

[Note that this question has obviously nothing to do with the search of the min of max value in the array. And I am not interested in sorting the array. Just the mere search.]

It should be possible to do this with $O(\sqrt{N})$ comparisons, saving an $O(\log N)$ factor over the straightforward "binary search each subarray".

The last condition, that the lengths of the subarrays strictly increases, makes things messy.  The analysis of $M$ subarrays, each of length $M$, is easier and it should be straightforward to extend the method to increasing-length subarrays.
Note that $\log M = O(\log N)$.

Also complicating things are the strict inequalities; it is easier to work with non-strict inequalities (which are also more general).

Finally, the conditions ensure that in subarray $A(i)$, the first element $A(i,1)$ is the minimum value and the last element $A(i,M)$ is the maximum value, so there is no need to deal with these elements explicitly.  This yields the simplified problem

there are $M$ subarrays of equal length $M$, and
for all $i,j$

[monotonicity across subarrays] $A(i,j) \le A(i+1,j)$,
[adjacent subarrays overlap] $A(i+1,1) \le A(i,M)$, and
[monotonicity within subarrays] $A(i,j) \le A(i,j+1)$.

If there is $u$ such that $A(u,1) \le n < A(u+1,1)$,
then only the first $u$ subarrays need to be considered,
and similarly for $v$ such that $A(v-1,M) < n \le A(v,M)$ focuses attention on the last $v$ subarrays; together their intersection defines a set of subarrays that must contain $n$.  The rest of the subarrays can be ignored.
This preprocessing can be done in $O(\log N)$ steps.

Then $A(i,1) \le n \le A(i,M)$ is guaranteed for each remaining $i$ in the range $M-v+1$ to $u$, otherwise $n$ is not in the array.  For the remainder, suppose that the preprocessing did nothing, so $u=v=M$ (this is the worst case). Run binary search on the middle subarray $w=\lfloor M/2\rfloor$; this determines that $A(w,j) < n < A(w,j+1)$; (if equality holds then $n$ has been found).

By monotonicity across subarrays, $A(i,j) \le A(w,j) < n$ for all $i \le w$ and similarly $n < A(w,j+1) \le A(i,j+1)$ for all $i \ge w$.

Now we need to recursively search about half of the remaining elements, considering the two rectangular blocks $A(1,j+1)..A(w-1,M)$ and $A(w+1,1)..A(M,j)$ in turn.  There are $M$ calls to check a block, but successive calls receive exponentially smaller blocks to work with.  Amortising the work across calls, the total work is $O(\sqrt{N})$ steps as each leaf of the search tree only does a constant amount of work.  More precisely this relates to solving the recurrence $f(n) = 2f(n/4) + \log n$ for which $f(n) \in O(\sqrt{n})$.

So overall, $O(\sqrt{N})$ steps suffice.

Note that the overlap of adjacent subarrays may be of use when extending to increasing-length subarrays, or in improving the algorithm, but isn't used here.

As far as I can tell, $\Omega(\sqrt{N})$ is also a lower bound.  A handwaving argument is that in the worst case, when all the values are close except for a single missing value, that value could be hidden in any of the rows and each row must be examined at least once.


Which attributes to consider for credit card fraud detection on an ATM? I am working on a project in which I am supposed to come up with a system that detects fraud from a credit card transaction. I read about techniques that others have used and decided to use Artificial Neural Networks for their adaptability.

WHAT THE SYSTEM MUST DO

My system is supposed to detect fraud on a credit card used on an ATM, that is, I am assuming that the user has already been granted access to the account by entering their PIN on an ATM. In other words, I am saying before the transaction is authorized, pass it through the fraud detection system so  we can check if it is fraudulent or not.

ATTRIBUTES THAT I AM THINKING TO CONSIDER

The amount of money to be withdrawn  - here I am assuming that each
user has a certain range of money that they usually withdraws; any
deviations are treated a suspicious.
Time taken to input PIN - here I am thinking that each user has a range of time that they usually take to input PIN; any deviation is treated as suspicious.

Questions

Which attributes can I take into consideration that enables me tell whether a  transaction is fraudulent or not?
What others have considered to solve this problem?
What do you recommend me?
What can be inputs to my Neural network?

Thanks for your ideas.

Location based trends
Number of transactions from a particular ATM in a particular location, compared to the home area. So if the user usually uses a small set of ATMs near to their address, and then suddenly there are 5 large transactions from an ATM on the other side of the country.
Another little suggestion
If it was up to me, I would use a system where the attempted transaction is given a suspiciousness rating, where each factor is given a score and then the overall decision whether or not to authorize the transaction is based on the average score. This would also allow you to prioritize different factors.
Does that make sense? (Sorry, it's my first post, I'm still getting used to the etiquette)