Minimum number of letters I have an assignment that I have to do and the question is

  Draw a DPDA that accepts the language L = {ba(bb)^(n+1)a^(n – 1) |n > 1}.

Im not looking for the answer but rather some direction. I would like to understand the 'n' powers.

Currently my understanding of the above language is that it will start with ba (obviously) Then it will have (bb) however this is where I am confused....

The last part says n > 1 does that mean that n+1 will have a min value of 3 meaning the language will always start with abbbbbbb(bb)* or does n > 1 mean at least 1 i.e. n+1 min value is 2?

Again please dont give me the solution to the DPDA as I would like to figure that out on my own.

Thanks
Jacques.

n>1 means that minimum n value is 2.

(bb)^n means bb repeated n times, i.e. if n=2, then it's bbbb.

With n=2, it's "ba bbbbbb a" (I added spaces only for clarity).

With n=3, it's "ba bbbbbbbb aa" - as you see, teacher used n to regulate size of the first and the second repetition in sync.


Randomized quicksort expected running time analysis I am following the quicksort analysis in CLRS (pp. 181-184, 3rd edition). Let me summarize the setting of the analysis.

Setting in CLRS

First let $Z = \{z_1, ..., z_n\}$ be the set of elements of the input array $A$ in sorted order. $X$ is defined as the number of comparison we make (i.e., between pivot and an element). Because any two elements of the array $A$ is compared at most once, we have $X = \sum_{i=1}^{n-1} \sum_{j = i+1}^{n} X_{ij}$ where $X_{ij} = 1$ if $z_i$ and $z_j$ are compared. So we just need to calculate the expectation, $\mathbb{E} \left[ X \right] = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \mathbb{P} \left(X_{ij} = 1\right)$.

So we just need to calculate $\mathbb{P} \left(X_{ij} = 1\right)$. According to the book, $\mathbb{P} \left(X_{ij} = 2\right) = \frac{1}{j - i + 1}$ and I don't follow this result.

My analysis

Let $k$ be the index of the randomly selected pivot. Conditioning on the event that $k \in Z_{ij}$ where $Z_{ij} = \{z_i, z_{i+1}, ..., z_j\}$,

\begin{equation}
  \begin{aligned}
    \mathbb{P} \left(X_{ij} = 1\right) &= \mathbb{P} \left( \left.X_{ij} = 1 \right| k \in Z_{ij}\right) \mathbb{P} \left(k \in Z_{ij} \right) + \mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) \mathbb{P} \left(k \not\in Z_{ij} \right) \\
    &= \frac{2}{j - i + n} \frac{j - i + 1}{n} + \mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) \left(1 - \frac{j - i + 1}{n} \right).
  \end{aligned}
\end{equation}

From this, we can see that if $\mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) = \mathbb{P} \left(X_{ij} = 1 \right)$, then indeed $\mathbb{P} \left(X_{ij} = 1 \right) = \frac{2}{j-i+n}$ agreeing the book's result. But I don't think that equality holds.

Suppose we choose pivot $k > j$ which is not in $Z_{ij}$. Then, we reduce the problem size to $\{1, ..., k-1\}$. Because $z_i$ and $z_j$ still belong to the same partition, we are given another chance to pick another pivot such that it is either $i$ or $j$. So I would expect that  $\mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) = \mathbb{P} \left(X_{ij} = 1 \right)$ does not hold.

Question

Is my analysis correct, i.e., $\mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) \not= \mathbb{P} \left(X_{ij} = 1 \right)$? If not, how to derive $\mathbb{P} \left(X_{ij} = 1 \right)$ considering the fact that if the chose pivot is not in $Z_{ij}$ we are given another chance?

Update

Yuval Filmus' answer is very good and complete in itself. But let me just add a little more step just for completeness. In particular steps leading to $\frac{2}{n} + \frac{2}{n} \cdot \frac{i-1}{j-i+1} + \frac{2}{n} \cdot \frac{n-j}{j-i+1}$ were not trivial to me. So hopefully this may help others.

As Yuval Filmus said we can prove that $p(n,i,j) = 2/(j-i+1)$ using (strong) induction (over $n$). First check the base case which is $n = 2$ because we need at least two elements in order to even think about comparing $z_i$ and $z_j$. With $n = 2$, $j = 2$, $i = 1$ and $p(2,1,2) = \frac{2}{2 - 1 + 1} = 1$. If we have 2 elements, then pivot has to be one of them, and $\mathbb{P} \left(X_{ij} =1; 2\right) = 1$. This proves the base case.

Now consider the inductive step. Assume that $p(m,i,j) = \frac{2}{j-i+1}$ for all $m < n$. In particular, note that all the values of the first argument of $p(\cdot, \cdot, \cdot)$ inside both summations are less than $n$. Hence, we can plug in $p(m,i,j) = \frac{2}{j-i+1}$.

\begin{equation}
  \begin{aligned}
    p(n,i,j)
  &= \frac{2}{j - i + 1} \frac{j - i + 1}{n} + \frac{1}{n} \sum_{k=1}^{i-1} \frac{2}{(j-k)-(i-k)+1} + \frac{1}{n} \sum_{k=j+1}^{n} \frac{2}{j-i+1} \\
  &= \frac{2}{j - i + 1} \frac{j - i + 1}{n} + \frac{2}{n} \frac{i-1}{j-i+1} + \frac{2}{n} \frac{n-j}{j-i+1},
  \end{aligned}
\end{equation}

which is the expression given by Yuval Filmus. The rest of the step is in his answer.

Let us denote by $p(n,i,j)$ the probability that $X_{ij} = 1$ given that there are $n$ elements.

Let $k$ be the first chosen pivot. If $k \in \{i,j\}$ then $X_{ij} = 1$. If $i < k < j$, then $X_{ij} = 0$. Otherwise, if $k < i$ then $X_{ij} = 1$ with probability $p(n-k, i-k, j-k)$, and if $k > j$ then $X_{ij} = 1$ with probability $p(k-1, i, j)$. Altogether, we get
$$
p(n,i,j) = \frac{2}{n} + \frac{1}{n} \sum_{k=1}^{i-1} p(n-k, i-k, j-k) + \frac{1}{n} \sum_{k=j+1}^n p(k-1,i,j).
$$
We can now prove that $p(n,i,j) = 2/(j-i+1)$ by induction, by noticing that
$$
\frac{2}{n} + \frac{2}{n} \cdot \frac{i-1}{j-i+1} + \frac{2}{n} \cdot \frac{n-j}{j-i+1} = \\
\frac{2}{n} + \frac{2}{n} \cdot \frac{n-(j-i+1)}{j-i+1} = \\
\frac{2}{n} + \frac{2}{j-i+1} - \frac{2}{n} = \\
\frac{2}{j-i+1}.
$$
Another way to get this result is to follow the algorithm until the first time when a pivot (at any level of recursion) in $\{i,\ldots,j\}$ gets selected. Elements $i$ and $j$ are compared if and only if this pivot happens to be $i$ or $j$, which happens with probability $2/(j-i+1)$.


how do I simplify this particular boolean expression? so I have spent nearly 5 hours trying to simplify this particular expression but I keep going round and round in circles. I have my hard copy notes to show you where I scribbled for hours and hours to no end. so please can someone please show me how can this be done?

$$(\overline{A}+\overline{B}+E)(\overline{A}+\overline{C}+D)(C+D+\overline{E})(\overline{B}+D)(A+E)\,.$$

I tried expansion, common, DeMorgan but I can't find my way out.

We can do it by brute force, expanding all 108 product terms and combining like terms carefully. Many of the terms can be eliminated immediately.

In hindsight or by luck or by sharp observation that D and E appear most frequently, we can proceed as follows.

  $(\overline{A}+\overline{B}+E)(\overline{A}+\overline{C}+D)(C+D+\overline{E})(\overline{B}+D)(A+E)$

Let $D=1$ and $E = 1$. The formula becomes 11111 = 1
Let $D=1$ and $E = 0$. The formula becomes $(\overline{A}+\overline{B})1 1 1 A = \overline{B}A$
Let $D=0$ and $E =1$. The formula becomes $1(\overline{A}+\overline{C}) C \overline{B} 1 = \overline{A}C\overline{B}$
Let $D=0$ and $E = 0$. The formula becomes $(\overline{A}+\overline{B})(\overline{A}+\overline{C})1 \overline{B} A = \overline{C}\overline{B}A$

So the original formula is
$$DE + (D\overline{E}A + \overline{D}(E\overline{A}C + \overline{E}\overline{C}A))\overline{B}$$

(Computationally, it is debatable which formula is simpler.)


Consistent theory based on L and not(A->A) is a theorem I am working on this problem in which I have a theory $T$ based on language $\mathcal{L}$ and the only information we have is that T is consistent and $\vdash \lnot(A \rightarrow A)$. Given this information, how can I know if this theory is sound, complete and/or decidable?
My only guess is that I can say that $T$ is sound because since $T$ is consistent and we can derive $\lnot(A \rightarrow A)$ from axioms and inference rules, $\lnot(A \rightarrow A)$ is a theorem and because of that we can assume that $T$ is sound (because the premises and conclusions are true).
Am I correct? What else can I say about this theory?
Thank you!

I'll assume that we're working in the context of classical propositional logic.
The first thing to point out is that $\lnot(A \rightarrow A)$ leads to a contradiction: ($A \land \lnot A$). Since propositional logic itself is consistent, it is impossible to derive a contradiction, so $\vdash \lnot(A \rightarrow A)$ is impossible.
So perhaps your intention was $T \vdash \lnot(A \rightarrow A)$. This can only happen if $T$ is itself inconsistent.
Given that $T$ is inconsistent, $T$ is vacuously complete (since an inconsistent theory can prove any formula) and decidable (for the same reason). As for soundness, it's a property of the logical system, not any particular theory like $T$. Propositional logic is sound.


Definitions of Computer Architecture and Computer Organization seems confusing So there was this question in one of my class tests. It may seem very simple and straight-forward, but I am unable to catch up with its meaning or explanation. I have referred my textbook of COMPUTER ORGANIZATION AND ARCHITECTURE by William Stallings. But that has just got me more confusing.
The definitions according to my textbook are:

Computer architecture refers to those attributes of a system visible to a programmer or, put another way, those attributes that have a direct impact on the logical execution of a program. Computer organization refers to the operational units and their interconnections that realize the architectural specifications.

I even referred to some websites which students at our university, if not the whole country, mainly depend on, but that didn't me help either.
The question is to mark which of the following is/are true:

Computer Organization refers to the design of functional blocks in a computer system.
Computer Organization is responsible to integrate functional blocks in a computer system.
Computer Architecture refers to the design of components and functional blocks in a computer system.
Computer Architecture concerns with the integration of functional blocks to build a computer system.

My marking was 2nd and 3rd option. My explanation about the same was: architecture would include designing of a structure while organization would be, well, the very English definition of how things are organized in a particular manner. I know this may be wrong, hence I am asking you for an explanation regarding which options are correct. Any help will be appreciated. Thank you.

It seems that the important difference between the terms as used here is that computer architecture is about useful things the system can do for its user (the programmer), and that computer organization is about how to build and connect "units" in order to create such a system.
I will first note that your argument here is not correct: while I agree architecture is about organizing and building things, computer architecture is, according to your book, not about building things. Note that "computer architecture" and "architecture" are not the same. A technical term with a definition is what the definition says it is, no more, no less.1 Any relation the name may have with the English language is irrelevant.2
For example, if I define a particular combination of points and lines to be a caterpillar, then a caterpillar is exactly that and any complaint that a combination of points and lines cannot turn into a butterfly is irrelevant.3
According to what the definitions computer architecture and computer organization say, it seems to me that (assuming "integrating functional blocks" and "interconnecting operational units" are interchangeable) Statements 1 and 2 are true, while 3 and 4 are false. I encourage you to work out the details on your own, using the definitions of the terms involved.

1: Or, as Lewis Carroll wrote:

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

 2: That said, it certainly is annoying when the name of a term seems to outright contradict its definition (cf. the lines in the poem preceding the quoted line of Mr. Dumpty), and I think the particular names chosen for the definitions in your book are not that good, to be honest. Naming concepts is an art in itself and not many good scientists are also good artists, or even want to be. So many concepts have unfortunate names, but if you read a book that uses those names, you will have to live with it.
3: No, I did not make this up. Someone else beat me to it.


Informed search with a lower-bound heuristic? I am well aware of informed graph / tree search strategies for optimal solutions when one has an admissible heuristic - i.e. one that never overestimates the minimum cost from a node to any goal state.

However, what about when one only has a heuristic that never underestimates the minimum cost from a node to any goal state? (Also: is there a name for such a heuristic?)

What I am currently doing is as follows. I first find some path to a goal state (luckily in my case this is relatively trivial) and record its cost and path as the best cost and path. Then I do a depth-first search, with two modifications. One, I do not stop when I reach a goal state, instead updating the best cost found so far and record the path to get here. Two, anytime I find myself at a node where the sum of the cost to get here and the heuristic is greater than or equal to the best cost found so far, I backtrack. Then at the end I output the best path found.

(Two nice things about this: 1) it's guaranteed to return an optimal solution, 2) if interrupted it has a solution, albeit a suboptimal one)

I've been calling this "iterative shallowing" (as opposed to iterative deepening), but I have no clue as to the actual name.

So: is there a name for this? If so, what is it? Is there a name for a lower-bound heuristic? Is there a name for informed search algorithms using only a lower-bound heuristic?

After some consideration, this appears to be an alternative formulation of the depth-first variant of the Branch-and-Bound algorithm.


Distributed predicate computation on event stream My question is actually a request for papers, articles, texts or books on the problem that I'm trying to solve on my work.
I'm working on a program that computes a predicate value (true or false) for a given object in a distributed system in which there is a stream of events that can change the object's attributes and, consequentially, the predicate value. Whenever the predicate value changes, the program must send a notification about this change.
For example, consider that there is an object A which has an attribute called name and consider that there is a predicate P which is true when the object's name is equal to Jhon.
Each event in the stream has a timestamp and a value for the attribute name. So consider the following sequence of events:
e1 = { name: Jhon, timestamp: 1 }
e2 = { name: Jhon, timestamp: 2 }
e3 = { name: Peter, timestamp: 3 }
e4 = { name: Doug, timestamp: 4 }
e5 = { name: Jhon, timestamp: 5 }

In this problem the events have a total order relation: If you have two events you always can say which one is the oldest of them.
Now, the events don't necessarily show up in the stream in the correct order according to its timestamp. Each event is unique to its timestamp, so there are no two or more events with the same timestamp for the same object. Also, the timestamps don't necessarily form a sequence that always increase by one: if we see e1 with timestamp 1 and e3 with timestamp 3, it doesn't imply the existence of e2 with timestamp 2.
There is no guarantee that all events will be received or when they will be received. It's part of the problem that we only know about the existence of the events that we see in the stream.
The real scenario is even worse: there are multiple computers parallelly processing this stream of events. However, for simplicity, I'll go further in this example considering only one computer.
If the events arrive and are processed in the order described above, then the notifications sent should be:
P(A) = true when e1 arrives
P(A) = false when e3 arrives
P(A) = true when e5 arrives.

That is the correct sequence of notifications because it respects the timestamp order.
Now, imagine that the computer receives the events in the following order:
e1, e5, e2, e4, e3

A naive algorithm which doesn't consider the event's timestamp would send an incorrect sequence of notifications:
P(A) = true when e1 arrives
P(A) = false when e4 arrives

The algorithm that I'm working on considers the timestamps and infers when a notification should have been sent but was not. So when e3 arrives it will notice that the notification P(A) = true for e5 was not sent.
This feels a bit like reinventing the wheel, though I'm not aware of any reading about this problem.
I would like some references to this problem or to something similar, like some papers dealing with this kind of problem.
The real problem is quite more complex since it involves storing the predicate $\times$ object state in a database that works as a shared state between the computers processing the stream and I'm talking about thousands of events arriving per second so it's not possible to keep all events stored in some database.
Is there any literature about the problem that I have described? if so, could you give me links to it?
I would like to see a paper or a text that explains an algorithm that solves this problem and it would be even better if such paper provides proofs about the algorithm (e.g. correctness).
If such paper doesn't exist (I actually think that is the case), I would accept an answer that describes an algorithm and provides an argument or a proof about its correctness.
For this algorithm to be correct, it should always send the correct sequence of notifications no matter what order that events arrives.
And the algorithm shouldn't keep all the received events in memory, because the real problem deals with too many events to save in memory or to store in a DB.
It would be reasonable to keep some events in memory, preferably a fixed amount.

Impossibility result #1: dropped events
The problem cannot be solved in general; there is no way to guarantee that your requirements will be met if some events are dropped (i.e., not received).  Consider first this stream:
e1 = { name: Jhon, timestamp: 1 }
e2 = { name: Jhon, timestamp: 4 }

where the algorithm sees both events.  Next, consider this stream:
e1' = { name: Jhon, timestamp: 1 }
e2' = { name: Pete, timestamp: 2 }
e3' = { name: Jhon, timestamp: 3 }
e4' = { name: Jhon, timestamp: 4 }

where the algorithm sees only the events e1',e4' (the other events are lost and never received).  You might notice that what the algorithm sees in both cases is identical, so its outputs will be identical in both cases.  However, the correct answer differs in these two cases, so there is no hope for an algorithm that always produces a correct output.  (The correct response in the first case is to produce no notifications; the correct response in the second case is to produce two notifications, one to indicate that the predicate is false after receiving e2', and one to indicate that the predicate is true after receiving e3'.)
It is not clear how to adapt the requirements to deal with this situation.  The only plausible solution I can see is to say that the notifications that are produced should depend only on the received events, not on the events that are sent.  This is equivalent to specifying that events cannot be dropped.
Impossibility result #2: re-ordered events
You state that you must be able to handle re-ordered events, without storing all events in memory, and with arbitrary re-ordering. However, these requirements are incompatible: that is impossible to achieve.  Consider a long sequence of events with timestamps 2,4,6,8,10,12,...  At the end of the long sequence of events, if an event with an odd timestamp arrives, the only way to be sure you can handle it correctly is to store the entire history of past events (or past states of the object).
So, you're going to have to relax the requirement about re-ordering as well.  Perhaps you're willing to store all events in memory forevermore.  (If so, you have a solution.)  Perhaps you are willing to impose a bound on re-ordering, e.g., no event will be delayed by more than 10 minutes.  (If so, you only have to store history for the past 10 minutes, and everything older can be deleted.)  Perhaps something else makes more sense in your particular situation.
But the one thing that is not an option is to impose all of the strong requirements stated in your question, and require an algorithm that is always correct.

I'm not aware of any literature on this and I don't particularly see any reason to expect there to be any.  It's a very specific set of requirements, and it looks to me like the resulting task is either trivial or impossible to solve.  Those usually aren't the kind of problems that tend to be studied in the literature.  Perhaps you might be interested in persistent data structures, but that's just a fancy way of storing the entire history of events, which you said you want to do; and you don't need a fancy data structure to do that in your particular situation.


Expected number of nodes in the independent set produced by a coloring algorithm on a graph with maximal degree $k$ We have a graph with $n$ nodes and maximal degree $k$. On this graph we run a coloring algorithm that finds a maximum independent set. The algorithm colors every node green with probability $\frac{1}{k}$ and colors the node red otherwise. This is done independently for every node. Return the independent set of nodes $x$ where $x$ is green and all neighbors of $x$ are red.

Show that the expected number of nodes in the independent set is at
least $\frac{cn}{k}$ where $c$ is some constant. (That is, $c$ does not depend on $k$).

Prove that the expected approximation ratio of the algorithm is at least $\frac{c}{k}$

I have no idea where to start on showing this.
I think I have figured out that the algorithm fails with probability $1-(1-\frac{1}{k})^k$ and that for any fixed node the probability for that node being put in the independent set is $\frac{1}{k}(1-\frac{1}{k})^k$. I am not sure, however, that these results are completely correct. That might be the reason I can't find a way of showing this or I could be missing something obvious. Help would be appreciated.
For anyone wondering, this is a practice problem for an upcoming exam.

As you've computed the probability of a node be in the dependent set is $\frac{1}{k}(1-\frac{1}{k})^k$. Hence, the expected number of these nodes is $n\frac{1}{k}(1-\frac{1}{k})^k$. As $\frac{1}{e} \leq \frac{1}{k}(1-\frac{1}{k})^k$, so the expected would be at least $\frac{cn}{k}$ (for $\frac{1}{e} \geq c$).

Hence, the expected approximation ratio is $\frac{cn}{k}$ over $n$.


Is emulation and/or virtualization faster when the host and guest systems are more similar? Is emulation and/ or virtualization performance faster when the guest and host OS are similar? If yes, how big, relatively speaking, is the difference? And whether the answer is yes or no, why is it so?

For example:

Same architecture

Will a x86 Windows host emulate and/or virtualize an x86 Android guest faster than it will an ARM Android guest?

Similar OS

In the following two examples, please ignore the fact that Debian is arguably more resource efficient than Windows, and simply focus on relative emulation/virtualization performance.

Will a Windows 10 host emulate/virtualize a Windows 7 guest faster than it will a Debian guest? (All are x86.)

Remotely similar OS

Will an OS X host emulate/virtualize a Debian guest faster than it will a Windows guest? (All are x86.) (Since OS X and Debian are both UNIX or UNIX-like.)

I would appreciate if any answers used many layman terms and analogies to explain in a way that people who are not computer scientists could understand it.

Yes, virtualization on the same architecture will be a lot faster, if the architecture has built-in support for virtualization (as modern x86 processors do).  With hardware support for virtualization, most code will run at full speed.

If you want to "virtualize" onto a different architecture, then under the hood the VM will probably end up doing emulation.  Emulation is much slower.

To understand why, I suggest you do some more background reading about how virtualization and emulation work.  You could start with Wikipedia: https://en.wikipedia.org/wiki/Virtual_machine and https://en.wikipedia.org/wiki/Hardware-assisted_virtualization and https://en.wikipedia.org/wiki/Hardware_virtualization and https://en.wikipedia.org/wiki/Emulator.  If you'd like more details, you could check out an appropriate textbook (e.g., a good operating systems textbook).

The operating system most likely won't matter -- at least, there's no fundamental reason why it needs to make a difference.  (It might make a difference for engineering reasons rather than scientific reasons, e.g., due to a 32-bit vs 64-bit OS, or due to lack of support for features used by the VM software.)  The only way to know for sure is to do some experiments: measure performance on workloads you care about.


Why is this language over {a,b,c} regular? The language of all words over the alphabet {a,b,c} such that

the number of as in the word
minus the number of cs in the word

is divisible by three.

How is this language regular? Lecturer notes says that it is, and then provides no explanation at all.
I tried drawing a DFA for it, but it just seems that the longer the word, the more states there will be and there could be an infinite amount, which is not allowed?
Please help, thanks.

All you need to keep track of is the value "number of $a$s seen minus number of $c$s seen", modulo 3 – call that $X$. There are only three different values that $X$ can take. When you see the next character of the input, it's either $a$, $b$ or $c$. Think about how each one affects $X$ and you should be very close to a 3-state automaton that accepts the language you're interested in.


Brute force method to solve the 0-1 knapsack problem I know that the brute force method is not the best way to solve the 0-1 knapsack problem. I'm not quite getting the dynamic programming idea, but would like to know the following:

If the brute force method can solve the problem with 20 items in 1 second - how many items can it solve in one day (2^16 s)?

I know that the time complexity of brute force is big O(2^n). But still I don't see how I can solve this.

You can't. Landau notation does not hold enough information.

You don't know the constant factor(s).
With only $O$, you don't have a lower bound.
It's only a worst-case bound; different runs with the number of items can have wildly different runtimes.
Such bounds only hold in the limit, that is even $\leq c \cdot 2^n$ may not hold for those $n$ you can realistically run the algorithm for.
The quantity bounded is not runtime but some abstract measure.

In particular, effects like operation reordering, memory hierarchy and branch mispredictions routinely skrew with runtimes.

The best you can do is assume that the runtime behaves like $\approx c \cdot 2^n$, run experiments with $n_1$ and $n_2$ items and estimate the constant factor -- then it's simple rule of three. But given all the caveats listed above, the prediction is unlikely to be worth much.


Does a never-halting machine always loop? A Turing machine that returns to a previously encountered state with its read/write head on the same cell of the exact same tape will be caught in a loop. Such a machine doesn't halt.

Can someone give an example of a never-halting machine that doesn't loop?

Consider the TM that always moves the tape head to the right and prints a special non-blank tape symbol at each step.  This means that the TM never halts, since it always moves to the right, and never repeats a state, since after k steps the tape head is over the kth cell of the machine.  Consequently, each configuration of the machine is different from all others, and the machine always loops.

We could also nonconstructively show the existence of such machines.  Assume for contradiction that every TM that never halts eventually loops.  This means that if you start a TM $M$ on a string $w$, one of the following will eventually happen:

$M$ halts, or
$M$ repeats a configuration.

In this case, the halting problem would be decidable as follows.  Given a TM $M$ and string $w$, simulate $M$ on $w$, at each point writing out the contents of the tape, current state, and current tape position.  If this configuration is a duplicate, output "does not halt."  Otherwise, if $M$ halts on $w$, output "halts."  Since one of these is guaranteed to happen eventually, this process always terminates, so we would have an algorithm for the halting problem, which we know does not exist.

Hope this helps!


How to speed up finding a subset of a given set? Is there a data indexing technique that speeds up finding subsets of a given set in a collection, or do I always have to scan all of the data?

For example, let's say that I have a collection of sets:
(a, b)
(b, c)
(a, b, c, d)
(a, b, c)
(b, c, d)
(b, e)
(d, e, f)
(d, f, g)
(d, e, f, g)

I want to find subsets of (a, b, c, d), so the output should be:
(a, b)
(b, c)
(a, b, c, d)
(a, b, c)
(b, c, d)

Is there a method to index/hash data in a way that will limit the number of collection elements that I have to scan in order to find all matches?

if you map every element in set in S into a bit in a binary number. For set with n elements, we have n bit binary number. the $i$-th number takes 1 if the subset has that element. Then we can use a binary number from $00,...,00$ to $11,...,11$  to represent all the subset.

If you map all your subset into binary numbers, then you are searching in the number space.


What are GPUs bad at? I understand that GPUs are generally used to do LOTS of calculations in parallel. I understand why we would want to parallelize processes in order to speed things up. However, GPUs aren't always better than CPUs, as far as  I know.

What kinds of tasks are GPUs bad at? When would we prefer CPU over GPU for processing?

GPUs are bad at doing one thing at a time.  A modern high-end GPU may have several thousand cores, but these are organized into SIMD blocks of 16 or 32.  If you want to compute 2+2, you might have 32 cores each compute an addition operation, and then discard 31 of the results.

GPUs are bad at doing individual things fast.  GPUs only recently topped the one-gigahertz mark, something that CPUs did more than twenty years ago.  If your task involves doing many things to one piece of data, rather than one thing to many pieces of data, a CPU is far better.

GPUs are bad at dealing with data non-locality.  The hardware is optimized for working on contiguous blocks of data.  If your task involves picking up individual pieces of data scattered around your data set, the GPU's incredible memory bandwidth is mostly wasted.


Who coined the term "artificial intelligence"? The most obvious (and commonly given) answer to this question is John McCarthy, but I have traced the first usage of this term to a 1955 paper, which McCarthy co-authored with Marvin Minsky, Nathaniel Rochester, and Claude Shannon. Although McCarthy was the lead author and probably the main organizer of the 1956 Dartmouth Summer Research Project on Artificial Intelligence, it could just as easily have been that one of these co-authors actually proposed the term "artificial intelligence". Does anyone know of any other evidence to suggest whose idea the actual term was? All of these individuals are now dead, but maybe some of their close associates or former students might be able to also shed light on the question.

Based on my research, there is no conclusive answer as to who coined the term, although McCarthy can be credited with helping the term to find widespread acceptance within the computer science community. See "AI: The Tumultuous History of the Search for Artificial Intelligence" by Daniel Crevier (Published in 1993 by BasicBooks):

"Overcoming the resistance of some participants (Samuel felt that "artificial" sounded phony, and Newell and Simon persisted in calling their work "complex information processing" for years afterward), McCarthy persuaded the majority to go for "artificial intelligence." He lays no claim to having coined the phrase, and admits it may have been used casually beforehand. Yet nobody denies him the achievement of getting it widely accepted."

-- Daniel Crevier, p.50


Do the following two CFGs describe the same language Do the following two CFGs describe the same language

S → aS | bS | ε
S → aS | Sb | ε

Would the answer to this be no, because the order can't be switched? bS and Sb are different. I'm a bit confused about how I would find out if they described the same language.

No. The word "abab" is described by (1) but not (2). You can test and visualize this here.
Trying to think about it inductively: (1) can only prepend "a" or "b" to a string while (2) can only prepend "a" and only append "b".
Switching the order of a production does not necessarily change the language the grammar represents, but it is in this case. As to the second part of your question, there is no generalizable or efficient way to determine whether two CFGs describe the same language.


Minimize sum of squares of rows in matrix when sum of columns have some constraint I'm looking for an algorithm that can find any matrix $a_{j,i}$ such that
$$
  \sum_{i \in I} \left(\sum_{j\in J} a_{j,i}\right)^2
$$
is minimal, while also for each $j\in J$ satisfying the constraint
$$
  k_j = \sum_{i \in I} a_{j,i}
$$
where $k_j$ is some non-negative constant. Furthermore every $a_{j,i}$ must be non-negative, and some arbitrary selection of $a_{j,i}$s in the matrix are fixed to be zero.

This problem models a situation where each $j$ has some fixed amount of resources that need to be divided in some way between a row of buckets. The constraint saying that some values are fixed to zero means that some buckets are missing on some rows.

We then want to find the way to divide the resources between buckets such that the columns of buckets have their contents divided as equally as possible between them.

Notice that if no values are fixed to zero, the solution is easy, since we can simply assign the values
$$
  a_{j,i} = \frac{k_j}{\#I},
$$
where $\#I$ is the number of columns. This way every line of buckets has an equal amount of resources assigned, and since decreasing the contents in one line would increase the contents of another, this is optimal.

The only solution I've currently been able to find is using some sort of linear programming solver that supports quadratic objectives, but I hope that this problem could be solved more efficiently than that.

Nontrivial example Suppose we are looking for a 3x3 matrix where
\begin{align}
  1 &= a_{1,1} + a_{1,2} \\
  2 &= a_{2,1} + a_{2,2} + a_{2,3} \\
  1 &= \phantom{a_{3,1} +\,} a_{3,2} + a_{3,3}
\end{align}
Notice that some terms are missing in these sums. This is equivalent of fixing those terms to zero.

We then want to minimize
$$
  (a_{1,1}+a_{2,1})^2 + (a_{1,2}+a_{2,2}+a_{3,2})^2 + (a_{2,3}+a_{3,3})^2.
$$
Notice that a lower bound on the minimum is $3\cdot\left(\frac{4}{3}\right)^2=\frac{16}4$, since in this case the $4$ total resources are equally divided.

In this case we can achieve that lower bound with the solution
\begin{bmatrix}
1/3 & 2/3 & 0 \\
1   & 0   & 1 \\
0   & 2/3 & 1/3
\end{bmatrix}
which indeed has the minimum $\frac{16}3$.

A different solution is
\begin{bmatrix}
2/3 & 1/3 & 0 \\
2/3 & 2/3 & 2/3 \\
0   & 1/3 & 2/3
\end{bmatrix}

Example that doesn't hit lower bound of minimum. Suppose we have the constraints
\begin{align}
  1 &= a_{1,1} + a_{1,2} \\
  4 &= \phantom{a_{2,1} +}\,\, a_{2,2} \\
  1 &= \phantom{a_{3,1} +}\,\, a_{3,2} + a_{3,3}
\end{align}
In this case we have $a_{1,1} \leq 1$, but in order to reach the lower bound where every line is equal to $2$, we must have $a_{1,1} = 2$, which is not possible.

In this case there is only one optimal solution, which is:
\begin{bmatrix}
1 & 0 & 0 \\
0 & 4 & 0 \\
0 & 0 & 1
\end{bmatrix}

Summary

Solve iteratively by pseudo-inverse, set negative $x_{ij}$ to 0, and remove negative $x_{ij}$ from equations.

Warning: seems to always work only if number of rows equal to the number of columns. Don't know if it is because of ill-conditioning of matrix or the initial guess is too far off or bug.

Lagrange Multipliers

I will write in math's ordering of index.

$x_{ij}$ is the element of matrix $X$ at row $i$ and column $j$.

The square of column sum of the $j^{th}$ column is:

$$\left(\sum_{i} x_{ij} \right)^{2}$$

The row sum constraint for the $i^{th}$ row is:

$$0 = s_i - \sum_{j} x_{ij} $$

Optimize sum of square of column sums by Lagrange multipliers:

$$
  L = \left [ \sum_{j} \left(\sum_{i} x_{ij}\right)^2 \right ] - \sum_{i} \lambda_i\left(s_i - \sum_{j} x_{ij}\right)
$$

Set derivatives to zero:

$$\forall i, j: 0 = \frac{\partial L}{\partial x_{ij}} = 2\left (\sum_{k} x_{kj}\right) + \lambda_{i}$$

$$\forall i: 0 = \frac{\partial L}{\partial \lambda_{i}} = s_i - \sum_{j}x_{ij} $$

Pseudo-inverse

Matrix equation:

$$A\vec{y} = \vec{b}$$

"Solve" by Moore-Penrose inverse (pseudo-inverse)

$$\vec{y} = A^{+}\vec{b}$$

This gives a solution that is as good as possible, even when some of the equations conflicts with each other.

Karush–Kuhn–Tucker conditions

What if the solution says some of the $x_{ij}$ is negative?

We set all negative $x_{ij}$ to zero, remove these variables from the matrix equation, and solve by Moore-Penrose inverse again. Repeat until no more negative $x_{ij}$.

(This is a simplified version of KKT because I don't understand everything in KKT yet.)

See: https://math.stackexchange.com/questions/1747435/correct-formulation-of-equality-and-non-negativity-constrained-non-linear-minimi

https://optimization.mccormick.northwestern.edu/index.php/Quadratic_programming

Example

I will explain with the 1-4-1 problem as an example.

Let $\vec{y}$ be the coefficients in row-major ordering and the $\lambda_i$

$$\vec{b} = \begin{bmatrix}
x_{1,1}&x_{1,2}&x_{1,3}&x_{2,1}&x_{2,2}&x_{2,3}&x_{3,1}&x_{3,2}&x_{3,3}&\lambda_{1}/2&\lambda_{2}/2&\lambda_{3}/2\\
\end{bmatrix}^{T}$$

where $[\cdot]^{T}$ denotes transpose of a matrix/vector.

I define a geometry matrix $G$. If $g_{ij} = 0$, $x_{ij}$ should be zero.
$$G = \begin{bmatrix}
{\color{red}1}&{\color{red}1}&{\color{red}0}\\
{\color{green}0}&{\color{green}1}&{\color{green}0}\\
{\color{blue}0}&{\color{blue}1}&{\color{blue}1}\\
\end{bmatrix}$$

Matrix $A$ is:

$$A = \begin{bmatrix}
{\color{red}1}&{\color{red}1}&{\color{red}0}&0&0&0&0&0&0&0&0&0\\
0&0&0&{\color{green}0}&{\color{green}1}&{\color{green}0}&0&0&0&0&0&0\\
0&0&0&0&0&0&{\color{blue}0}&{\color{blue}1}&{\color{blue}1}&0&0&0\\ \hdashline
{\color{red}1}&0&0&{\color{green}0}&0&0&{\color{blue}0}&0&0&{\color{magenta}1}&0&0\\
0&{\color{red}1}&0&0&{\color{green}1}&0&0&{\color{blue}1}&0&0&{\color{magenta}1}&0\\
0&0&{\color{red}0}&0&0&{\color{green}0}&0&0&{\color{blue}1}&0&0&{\color{magenta}1}\\
\end{bmatrix}$$

Upper half is for constraints.
Bottom half is for $0 = {\partial L}/{\partial x_{ij}}$.
The magenta numbers are for $\lambda_1$, $\lambda_2$, and $\lambda_3$.

The $\vec{b}$ is just the row sum padded by zeros:

$$\vec{b} = \begin{bmatrix}1&4&1&0&0&0\\\end{bmatrix}^{T}$$

Result

--- cycle 0 ---
    Matrix A:
        [[1. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
         [0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0.]
         [0. 0. 0. 0. 0. 0. 0. 1. 1. 0. 0. 0.]
         [1. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0.]
         [0. 1. 0. 0. 1. 0. 0. 1. 0. 0. 1. 0.]
         [0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 1.]]
    Vector b^{T}:
        [[1. 4. 1. 0. 0. 0.]]
    Vector y^{T}:
        [[ 1.4 -0.4  0.   0.   4.   0.   0.  -0.4  1.4 -1.4 -3.2 -1.4]]
    X:
        [[ 1.4 -0.4  0. ]
         [ 0.   4.   0. ]
         [ 0.  -0.4  1.4]]
    lambda^{T} / 2:
        [[-1.4 -3.2 -1.4]]
    row sum of X:
        [1. 4. 1.]
    column sum of X:
        [1.4 3.2 1.4]
--- cycle 1 ---
    Matrix A:
        [[1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
         [0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0.]
         [0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0.]
         [1. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0.]
         [0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 1. 0.]
         [0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 1.]]
    Vector b^{T}:
        [[1. 4. 1. 0. 0. 0.]]
    Vector y^{T}:
        [[ 1.  0.  0.  0.  4.  0.  0.  0.  1. -1. -4. -1.]]
    X:
        [[1. 0. 0.]
         [0. 4. 0.]
         [0. 0. 1.]]
    lambda^{T} / 2:
        [[-1. -4. -1.]]
    row sum of X:
        [1. 4. 1.]
    column sum of X:
        [1. 4. 1.]

Program

import numpy as np
from numpy.linalg import pinv, lstsq

def vec_y_split(vec_y, geometry):
    """Reshape vec_y into reshaped vec_y matrix and lambda
    """
    n_rows, n_cols = geometry.shape
    return vec_y[:-n_cols].reshape(geometry.shape), vec_y[-n_cols:]

def array_to_indent_str(x, indent=1):
    s = " " * indent * 4
    return s + str(x).replace("\n", "\n" + s)

def print_vec_y(vec_y, geometry, row_sum, indent=0):
    c, lam = vec_y_split(vec_y, geometry)
    s = " " * indent * 4
    print(s + "X:")
    print(array_to_indent_str(np.around(c, 3), indent + 1))
    print(s + "lambda^{T} / 2:")
    print(array_to_indent_str(np.around(lam.T, 3), indent + 1))
    print(s + "row sum of X:")
    print(array_to_indent_str(np.around(c.sum(axis=1), 3), indent + 1))
    print(s + "column sum of X:")
    print(array_to_indent_str(np.around(c.sum(axis=0), 3), indent + 1))
    print(s + "Error (Not considering zero requirement):")
    err = np.sum((c.sum(axis=1) - row_sum) ** 2) ** 0.5
    print(s + str(err))

def make_mat_A(geometry):
    n_rows, n_cols = geometry.shape
    mat_A = np.zeros((n_cols + n_rows, geometry.size + n_cols))
    # row equations
    for i in range(n_rows):
        for j in range(n_cols):
            mat_A[i, i * n_cols + j] = geometry[i, j]
    # col equations
    for j in range(n_cols):
        mat_A[n_rows + j, geometry.size + j] = 1
        for i in range(n_rows):
            mat_A[n_rows + j, i * n_cols + j] = geometry[i, j]
    return mat_A

def make_vec_b(geometry, row_sum):
    n_rows, n_cols = geometry.shape
    vec_b = np.empty((n_cols + n_rows, 1))
    vec_b[:n_rows, 0] = row_sum
    return vec_b

def remove_var(geometry, mat_A, coeff, epsilon):
    n_rows, n_cols = geometry.shape
    for i in range(n_rows):
        for j in range(n_cols):
            ix = i * n_cols + j
            if coeff[ix] < -epsilon:
                mat_A[:, ix] = 0

def iterate(geometry, mat_A, vec_b, vec_y, row_sum):
    i = 0
    epsilon = 1e-7
    n_rows, n_cols = geometry.shape

    while i == 0 or np.any(vec_y[:-n_cols] < -epsilon):
        print("--- cycle %d ---" % i)
        print("    Matrix A:")
        print(array_to_indent_str(np.around(mat_A, 3), 2))
        print("    Vector b^{T}:")
        print(array_to_indent_str(np.around(vec_b.T, 3), 2))

        vec_y = lstsq(mat_A, vec_b, rcond="warn")[0]

        if i > 0:
            remove_var(geometry, mat_A, vec_y, epsilon)

        print("    Vector y^{T}:")
        print(array_to_indent_str(np.around(vec_y.T, 3), 2))
        print_vec_y(vec_y, geometry, row_sum, indent=1)

        i += 1

def search(geometry, row_sum):
    print("=== Start ===")
    print("row_sum^{T}:")
    print(row_sum.T)
    print("geometry:")
    print(geometry)
    n_rows, n_cols = geometry.shape
    vec_y = np.empty(geometry.size + n_cols)
    # Set initial guess to solution with no zero
    vec_y[:-n_cols].reshape(n_rows, n_cols)[:] = \
        row_sum[:, np.newaxis] / n_cols
    vec_y[-n_cols:] = 0
    print("Intial Guess:")
    print_vec_y(vec_y, geometry, row_sum, indent=1)

    mat_A = make_mat_A(geometry)
    vec_b = make_vec_b(geometry, row_sum)
    iterate(geometry, mat_A, vec_b, vec_y, row_sum)

def problem_1_4_1():
    # For the 1-4-1 problem, use
    row_sum = np.array([1, 4, 1])
    geometry = np.array(
        [[1, 1, 0],
         [0, 1, 0],
         [0, 1, 1], ]
    )
    search(geometry, row_sum)

def problem_random():
    np.set_printoptions(precision=3)
    N = 100 * 2
    n_rows = N
    n_cols = N
    # row_sum is integers between 1 and 100 inclusive.
    row_sum = np.random.randint(1, 1000, size=n_rows)
    # geometry is a random array of zeros and ones.
    geometry = np.random.choice(2, size=(n_rows, n_cols))

    search(geometry, row_sum)

problem_1_4_1()
problem_random()

Random Implementation Ideas

No need to calculate pseudo inverse. Some solvers solves for a linear least square system. That is equivalent to solve by Moore-Penrose inverse, but possibly faster. https://eigen.tuxfamily.org/dox/group__LeastSquares.html
Use sparse solvers if there are many zeros.
Maybe rewrite the equations in block triangular form. For each overall iteration, perform one newton iteration on each block. That means no need for sparse matrix and two much smaller dense matrices. Don't know if that is possible though.
Use old solution as initial value for finding new solution.

Alternative and Questions

Use/Derive Simplex/criss-cross algorithm for the derivative of the lagrange multiplier equations. Don't know speed.

Or Use/Derive Simplex algorithm for quadratic programming.

https://www.me.utexas.edu/~jensen/ORMM/supplements/methods/nlpmethod/S2_quadratic.pdf

https://math.stackexchange.com/questions/246808/analog-of-simplex-method-for-quadratic-programming

What algorithm does the solver use?

How big is the matrix $X$?

How many zeros in matrix $X$?


Training a neural net without labels in Reinforcement Learning I am trying to dig further into machine learning and I am making a program to play a game as a start. I have created a game that is based on the mobile game Flappy Bird and can be generalized to the following:

Actions $A = \{\text{no action}, \text{tap}\}$
States $S \subset \mathbb{R}^3$ such that $s \in S$,

$s_1$ is the horizontal distance to the center of the nearest forward gap
$s_2$ is the vertical distance to the center of the nearest forward gap
$s_3$ is the vertical velocity ($\text{unit}/\text{sec}$)

As a starting point, I have implemented a naive Q-Learning algorithm with positive rewards whenever it passes through a gap successfully. Everything went well and the q-table ($f(s): S \to A$) was adjusted accordingly to the rewards.

Now I would like to train a neural net to do the same. One problem that existed with the Q-Learning approach is that the algorithm does not take locality into account. I had to also discretize the feature space into very huge chunks which is not optimal. I am hoping that a neural net can solve these issues.

I am familiar with performing basic classifications with neural nets, and so I am trying to approach this problem similarly. I would just take a state (a vector of three real numbers) as input and an action as output (one neuron per action and take the one with the highest probability). The problem is, I do not have labels for training! The only thing that I get from the game is reward.

Is a neural net a good choice for this type of problem? How should I train or design such network?

What you are looking for is DQN: Deep Q-Network.

You want to have a look at the example code, but the idea is as follows:

Input: The observation
Output: Reward - the action can either be in the input or better one reward-prediction per possible action, if the action is discrete.

For final states, you know the true reward. Hence your target is clear (see line 112). But if this is not the case, you need to adjust the target to the observed reward and the discounted expected reward (line 113ff).

Extremely important: The output layers activation function. Don't use softmax, as it is unlikely that your rewards sum up to 1. Don't use ReLU if the reward can be negtive. Simply using a linear output makes most sense in most cases.


Query all bounding boxes which contain a point I'm looking for the most efficient spatial-indexing data-structure for storing and querying bounding boxes which contain individual points. The points represent 2D coordinates on a grid, while the bounding boxes represent regions of the grid. The bounding boxes may vary greatly in size, and multiple bounding boxes may overlap a single point. Both points and bounding boxes are stored as signed integers.

For example, in the diagram below, if I were to query points $B$ and $C$, I'd expect a single bounding box in return. However, if I query point $A$, I'd expect an array containing both bounding boxes in return.

--------
| B  ============
|    |A|        |
-----|--     C  |
     ============

I'm not concerned with insert/remove efficient for adding bounding-boxes to the structure as all bounding-boxes are added to the structure during a one-time initialization. My main concern is efficient look-ups for finding which bounding boxes contain a point, as such queries will be made frequently.

My initial thought is to use a quadtree, and to test all objects contained in a particular node to see if they contain the point being queried. However, I'm wondering: is there a better data-structure I could use to implement this behavior with?

Use a 2-d segment tree. Assuming we have $n$ items, construction takes time $O(n \cdot \log^2(n))$ and each query takes $O(\log^2(n))$ time. These times become $O(n \cdot \log(n))$ and $O(\log(n))$ time, respectively, if we use fractional cascading and lowest-level interval tree. These are good times unless there is more problem structure.

The query is called "multi-dimensional stabbing query" or "point enclosure query".

Range tree involves finding points in a query range. Segment tree involves finding rectangles that contain a query point.

On an unrelated note, one might wish to use an R-tree with sort-tile-recursive (STR) bulk-loading. This leads to almost no overlap between bounding boxes for a node's children and the structure is balanced. If we are lucky (i.e. R-tree involves heuristics and we wish to avoid ties for each component), the structure is good for moderate number of dimensions because factor of $d \cdot \log(n)$ for time is lower than $\log^{\textrm{max}(d - 1, 1)}(n)$ (noting that $d \geq 1$). We take advantage of fact that use of R-tree does not involve cloning primitives. Also, nearest neighbor via heuristic can perform quite well with R-tree, which seems to be something that that excels at w.r.t. segment tree and range tree. Additionally, one might wish to for dynamic structure use an R*-tree or one might wish to for slightly more dimensions use an X-tree. The more dimensions one has, the more likely linear scan is more affordable via a kind of "curse of dimensionality".

Further, if one has only distances and no absolute locations, a metric tree will prove useful. Structures that assume rectangle primitives will be aided by fact that a point is a degenerate rectangle. A pair of points that act as opposite corners of a rectangle can be turned into one point via a "corner transformation" from Pagel 1993.

One strategy that may be used with R-tree is augmenting it with "look-ahead" and edge checks to get guaranteed theoretically acceptable time for a query such as point enclosure query. This is even when it seems an R-tree is designed specifically for this kind of query.

References

Pagel et al. - The transformation technique for spatial objects revisited (1993)


How does this recurrence relation fit the algorithm? I have the following pseudo code:

Multiply(y,z)
1. if (z==0) return 0
2. else if (z is odd)
3.    then return (Multiply(2y, floor(z/2)) + y )
4. else return (Multiply(2y, floor(z/2)))

Towards analysing this procedure's runtime, this recurrence relation is given as answer:

$\qquad \displaystyle T(z) = \begin{cases} 0 & z=0 \\ T(z/2)+1 & z>0\end{cases}$

Why is $T(z)=0$ when $z=0$? Shouldn't it be $1$ for this case?

And, the $+1$ in $T(z/2)\mathbf{+1}$ is because the worst case is
(multiply(2y, floor(z/2)) + y (note the + y). Am I correct?

You should be careful about what is being counted. If you want to count "runtime" (as in, number of statements) the given recurrence is clearly wrong.

Reverse-engineering from the recurrence, it is probably supposed to count additions. In particular, note how the computation the parameters for recursive calls is ignored. I hope it is clear that the recurrence is correct for the worst-case then; your reasoning for $+1$ is spot-on.

Why does restricting your self to additions make sense here? Additions are one of the statements that are executed most often (in the worst case, that is ignoring line 4.). That means that the true runtime (in a theoretic model) is proportional to the number of additions. Since you are (most likely) after asymptotics in terms of $O$, counting additions is sufficient: the proportion-constant is lost in $O$, anyway.

You can, for the fun of it, set up a recurrence counting all statements. You'll see that the result has the same asymptotic growth as the one you were given.


How to prove for that a given non-regular language its given super-set is also non-regular? Consider the non-regular language $L_1$ = {$a^n$b$a^n$:  $n \geq 0$} and its super-set language

L = Language of strings with equal number of trailing and leading a's,

or in other words,

$$L = \{a^n b w b a^n : n \ge 0, w \in \{a,b\}^*\} \cup \{a^n b a^n : n \ge 0\}.$$

How would we prove that L is also non-regular?

I have the idea that I should use the help of $L_2 = L - L_1$, but I'm stuck at the following step:

$L_1 \cap L_2 = \phi $ , thus $L_1 \cap L_2$ is a regular language.

I was trying to prove it using contradiction.

Let, L to be regular which is $L_1 \cup L_2 $ is regular.

And tried to prove, $L_1$ or $L_2$ is equal to a set union or intersection or complement operation over the regular sets $L_1 \cap L_2 $ and $L_1 \cup L_2$

But stuck at

$L_1 = [(L_1 \cup L_2) \cap (L_2)^c] \cup (L_1 \cap L_2)$

With Myhill-Nerode theorem: I might be incorrect please fix me if I am wrong.

Take S  =$a^*(b+b.(a+b)^*.b)$
Pick x and y from S such that $x \neq y$.

x = $a^n b$
y = $a^m b$
Take, z = $a^n$

$x.z \in L$ but $y.z \notin L$. Thus, by Myhill_Nerode one can conclude it to be non-regular.

Since you already know that $L_1$ is nonregular, here is a simple proof.
Suppose that $L$ is regular. Then since $a^*ba^*$ is regular, the language $L \cap a^*ba^*$ should be regular. But $L \cap a^*ba^* = L_1$, which is not regular. Hence $L$ is nonregular.


algorithm to find shortest path connecting EVERY node I have received a problem to solve and I am not sure what algorithm to use.
TLDR; Find the shortest path to get to every node in a undirected graph

The problem states that one must visit every station in the shanghai metro in the shortest path possible. Interchange Stations ('edges') can be reused and you can start / stop anywhere.
I have created a lookup table that shows connected stations as well as the distance to travel (not shown)
"Xinzhuang": [
  "Waihuan Rd." : 1
],
"Waihuan Rd.": [
  "Xinzhuang": 2.2,
  "Lianhua Rd.": 3
],
"Lianhua Rd.": [
  "Waihuan Rd.": 4,
  "Jinjiang Park": 5,
],
"Jinjiang Park": [
  "Lianhua Rd.": 9.1,
  "South Railway Station": 10.3
],
"South Railway Station": [
  "Jinjiang Park": 4.1,
  "Caobao Rd.": 1.1,
  "Shilong Rd.": 2.5
],
...

I found this leetcode problem but it did not mention any specific algorithm and since it was O(2^N * N) I wondered if there was a faster method than BFS.
https://leetcode.com/problems/shortest-path-visiting-all-nodes/solution/
Since my graph is so big, I was going to reduce the lines with a single path to a single node.
What algorithm can I use that will work in Polynomial time, OR has the least time complexity?

There is no polynomial-time algorithm for your problem unless $P=NP$, since it captures the Hamiltonian path problem as a special case.
Moreover, unless the exponential time hypothesis fails, there is no $2^{o(n)}$-time algorithm for your problem, where $n$ is the number of vertices.


Question on the properties of red black trees Problem statement

Let $T$ be a red black tree and $u$ some internal node of $T$. Suppose that in the left subtree of $u$ we have $n$ nodes. What is the maximum number of nodes that we can have in the right subtree of $u$, before the properties of the red black tree are broken?

Attempt at a solution

I was given the answer $O(n^2)$ (past exam sheet question with the answer marked). However, I don't think it's correct, unless I have misunderstood the problem.

According to  CLRS the properties of a red black tree are the following:

Every node is either red or black
The root is black
Every leaf (NIL) is black.
If a node is red, then both its children are black.
For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Since we are in some internal node $u$, from the properties we infer that all simple paths starting from $u$ and ending in some leaf, should contain the same number of black nodes.

We are given that in the left subtree of $u$ we have $n$ nodes, and our goal is to maximize the number of nodes that we have in the right subtree. It seems natural to assume that the left subtree is a chain containing $n$ black nodes, because in this way, we can make the right subtree of $u$ be a complete binary tree, where every simple path starting from the root of the subtree and ending in some leaf contains exactly $n$ black nodes. And not only that, we can also in the end add red levels of nodes in between black levels, thus increasing the size of the right subtree by 2.

Reducing the black height of the left subtree, will only imply fewer nodes in the right subtree.

So lets find the number of nodes in the right subtree. Essentially we have a complete binary tree of height $n$, so the number of nodes will be:

$S = \sum_{i=0}^{n-1}2^n$

$-2S = \sum_{i=1}^{n}2^n$

$S(1-2) = 1 - 2^n$

$S = 2^n - 1$

so the answer is $O(2^n)$. Am I wrong or was there a typo in the exam sheet?

The left subtree cannot be a chain of $n$ black nodes, since it breaks the red-black tree properties.

In the worst case scenario, the left subtree is a minimal black binary tree of  height $\log n$, while the right subtree is a full maximal binary tree of height $2\log n$.

The black height of the right subtree must be $\log n$ as well, therefore its maximal total height (including red nodes) is $2\log n$. Since it is a maximal binary tree, it has
$ 2^{2\log n}  = 2^{\log n^2} = n^2 $ nodes.


Is every edge of a graph included in some spanning tree? Let's say we have a graph $G$. We pick one edge from it (any edge). Will there always be such a spanning tree that contains that very edge?

I think the answer is yes, because no matter what we do we can always create such a spanning tree so that the very edge we picked is included. Of course, a more formal proof would be needed?

Note that the initial graph $G$ needs to be connected or it has no spanning trees at all.  (Though the same argument applied to each component would show that any graph has a spanning forest containing any chosen edge.)

Let $G=(V,E)$ be a connected graph, let $T$ be any spanning subtree and let $e$ be any edgein $E$. We claim that there is a spanning tree that includes $e$. If $e\in T$, we are done. Otherwise, $T+e$ contains a cycle. That cycle necessarily contains at least one edge $e'\neq e$ (actually, it contains at least two). $T+e-e'$ is a spanning tree that contains $e$.

You should prove to yourself that $T+e-e'$ really is a spanning tree.


Why is the subset of palindromes of a regular language context-free? Why is $A(L) = \{x \in L \mid x = x^R \}$ context-free if $L$ is a regular language?

Trying to understand the approach to determining whether a regular language is context-free.

Hint: The intersection of a context-free language with a regular language is still context-free.


Terms for different models of sum types There seem to be at least a couple different possible ways of modeling sum types in a type system, but I haven't been able to find consistent terms for referring to them:

A sum type is formed from a set of "data constructors", which are function-like entities that notionally map values of a summand type to values of the sum type. This is the model adopted by e.g. Haskell and the various flavors of ML.

A sum type is formed directly from the underlying summand types, with no data constructors, and as a consequence the sum type is a supertype of the summands (or at least behaves very much like one). This model seems to be much less common, but it's the model adopted by Ceylon, and by C++'s std::variant.

Note that this is separate from the distinction between discriminated and non-discriminated unions: both models permit the sum type to be discriminated (although only if the summands are disjoint, in the case of #2).
Are there settled terms for distinguishing these two models?

The first concept you mention is that of an algebraic data type (or ADT). These are (recursive) sum-of-product types, though in many languages the product types are not first-class in that you may not refer to them directly, but only as part of the sum.
The second concept is a true sum type. However, in both the examples mentioned, the sum type has a restriction that the summands must be unique, e.g. you cannot describe the type $A + A$, because summands are referenced nominally, rather than by their index.

Note that ADTs suffice to describe sum types (even with non-unique summands), by wrapping their summands in new constructors. However, they are more general, as they can describe fixed point types, like binary trees.


Why is the undecidability of the Halting Problem useful? My understanding:

The Halting Problem is undecidable for a Turing Machine, and yet it is decidable for a linear bounded automaton (a Turing Machine with finite tape). The reason is that the only way an LBA can loop is by entering a configuration it's already been in, which is easy to check. However, unlike an LBA, a Turing Machine can also loop by entering infinitely many new configurations, none of which accept. So it seems that what the Halting Problem's undecidability really means is that the problem of checking whether a Turing Machine will enter infinitely many new configurations without accepting is undecidable.

My question:

But real computers are LBAs, not TMs. They can't enter infinitely many new configurations. So why is the undecidability of the Halting Problem a useful result?

I've looked at the answers to this and similar questions, and invariably they go something like, "a real computer has a bazillion configurations, and so waiting until you hit a repeat one would take a bazillion years." But as I detailed above, Halting undecidability doesn't seem to tell us anything about that kind of looping; it only tells us about the infinitely-many-new-configurations kind that real computers can never engage in.

Detecting whether a Turing machine loops can be arbitrarily difficult.
For example, pick any problem P and consider the program:

k = 0
done = False
while not done:
  if <k encodes a solution to P>:
    k = 0
  elif <k encodes a solution to ¬P>:
    break
  else:
    k += 1

This program either terminates or runs forever with repeating configurations, but in order to tell whether configurations repeat, we need to know whether P has a solution. Now just insert a very difficult (undecidable) P.

A real computer has a bazillion configurations. That number is closer to infinity than to any number we can actually comprehend. Turing machines are a better mathematical model of real computers than finite state automata. Something similar happens in physics: the Earth is made from finitely many molecules, but physicists use differential equations that assume matter to be continuous and smooth. That is because the extremely large finite number of molecules is better approximated with the continuum than a discrete system with bazillion states.


Expressive power of formal systems How do we classify formal systems' (propositional logic, first-order logic, second-order logic,  higher-order logic, Hoare logic and type theory) expressivity?

In the same way that grammars (CSG, CFG, ...), languages (CSL, tree-adjoining language, ...) and abstract machines (Turing machine, ...) 'fit' into the Type 0-3 range of the Chomsky hierarchy, can we also classify the formal systems into it?

Or, is there another yardstick for describing the relative expressive power of formal systems?

Comparison of logics is  a complicated subject.

Expressive power of logics can be 'measured' in various ways. The most well-known approach is that of conservative extensions. If $L$ is a logic with signature $\Sigma$, then a logic $L'$ over signature $\Sigma' \supseteq \Sigma$ is a conservative extension of $L$ provided every $\Sigma$-formula $\phi$ that is provable in $L'$ is already provable in $L$. In other words, conservativity means that by moving from $L$  to $L'$  we are not adding expressive power to the discourse about things that can be expressed in $\Sigma$.

Things become more complicated when you are looking at logics with signatures that are not comparable by $\subseteq$. When you want to compare e.g. set theories with type theories, then you won't get a nice match of signatures. In this case you need to look at encodings. This can be done in various ways. For example you can encode formulae, or formulae an proofs. You can study properties of those encodings (e.g. do they preserve formula/proof structure) etc?

An old example of encoding is Gödel's and Gentzen's double-negation translation that embeds classical logic into intuitionistic logic, and reduces the consistency of the former to that of the latter.

Comparison of programming languages is  even more complicated
 and -- kind of, sort of -- contains the comparison of logics as a special case by the Curry–Howard correspondence.


Solving recurrences (tree method) with square roots I am trying to find the upper and lower bounds for this recurrence, but I am not sure how to handle to square root:
$$
T(n) = 4T(n/2) + n^2\sqrt{n}
$$

$n^2 \cdot \sqrt{n} = n^{5/2}$, then you can proceed with the Master Theorem as normal.

If you specifically need to use the Recursion Tree Method for solving recurrences, then you can still proceed normally.

Root Level : $n^{5/2}$
Next Level : $4 \cdot (n\ /\ 2)^{5/2} = 2^{4/2} \cdot n^{5/2}\ /\  2^{5/2} = n^{5/2}\ /\ 2^{1/2}$
Next Level : $16 \cdot (n\ /\ 4)^{5/2} = 4^{4/2} \cdot n^{5/2}\ /\ 4^{5/2} = n^{5/2}\ /\ 4^{1/2}$
etc.


How do Computer Algebra Systems work? In Computer Architecture course, I have learnt how computer performs numerical computations.
While using MATLAB, I was introduced to symbolic mathematics toolbox.
I was amazed to see it manipulating trigonometric expressions, indefinite integration etc.
What sorts type of algorithms are used for doing symbolic mathematics.
Is there any text or article available of how symbolic mathematics is performed in computer algebra systems.

Note: For this answer I chose to assume that the question was somewhat
naive, since, as remarked by @D.W. in his comment, the OP should
otherwise search for himself in wikipedia and other places on the web,
and the spectrum of problems and techniques is far too wide for an
answer here. So I am focussing on the fundamental aspects, obvious to
a seasoned computer scientist, but somewhat magical for someone with
less technical experience, and seeming to border artificial
intelligence, when it is often just the application of appropriate
recipes (well, often complex ones). One meta-remark: users who ask
questions should give some information regarding their experience (or
their age, as a weak indicator). It is often difficult to assess the
level appropriate for an answer.

A fundamental question is whether there is any difference between
numerical computation and algebraic manipulation.

As a computer scientist (to be ?) you shold more than anyone else be
aware that all that is done by the computer, or by the mathematician,
is to manipulate representations of abstract entities.

You learn in "algorithmics and data structures" that to deal
efficiently with a problem, you have to find a proper representation
for the data (e.g. a graph, an array, a string, a hash-table, a binary-tree, etc.) and to
manipulate this representation appropriately (which impacts the choice of the proper representation) to get a representation
of the result.

Numerical calculation is no different. You represent numbers by
sequences of symbols (though some systems use two dimensional
representations). Then you define various manipulation schemes of
these sequences that corresponds to numerical operations you are
interested in.

The invention of the representation 0 for a number measuring the absence of any content, and of positional
numeration system (i.e. representation of numbers) was a major step in
mathematics, and allowed for more effective encoding techniques for
numerical data, and of simpler manipulation techniques for doing the
operations.

This oganization is universal: we always work on representations. The
computer does nothing else, even when doing simple arithmetics.

So the answer to your question is simply, as always: choose a
representation for whatever concepts you want to manipulate an design
the algorithms that manipulate these representations in a way that
corresponds to the abstract manipulations you are interested in.

Typically, if you want to manipulate algebraic expressions containing
constants, variables (identifiers) and operators, you can just
represent them as a rooted tree structures with constants and
variables on the leaves, and the operators on the nodes. That is easy, though more complex representations may sometimes be useful.

Now you may consider your expression as representing a function of a
variable x, that appears among the variables, and you want to
compute the derivative of that expression for x. You can probably imagine
the algorithm yourself, if you know the rules for computing a
derivative, when you do it by hand.  This is a fairly simple recursive
procedure, since the derivative of an expresson can be defined from
the subexpressions and their derivatives, in a way that depends on the
top operator.

You can do things similarly for some trigonometric computations, applying various rules and strategies for transforming trigonometric expressions (such as: $\cos(a+b)=\cos a\cos b-\sin a\sin b$ ), that were used by hand by people (including myself) before computers were available to do it.

Now, many of these manipulation problems are actually hard to
solve. But that comes from the diffculty of mathematics, not from the
fact that it is mechanized in a formal calculation system. There involve a wide variety of techniques and mathematical theories, that have to be adressed individually, and certainly not together in a single question.

As a final remark, we should remember that much of the theory of
computation originates with the search for answers to the
Entscheidungsproblem, a challenge posed by David Hilbert in 1928
about mechanisation of mathematics, and addressed by such people as
Gödel, Church, Turing, and several other pioneers of the field. The
fact that computing devices are now used to do just that, mechanize
mathematics, was only to be expected. It is always pleasing to see
some consistency between the various branches of computer science.


How hard is finding restricted assignment of 3-SAT satisfying $7/8$ of the clauses? The PCP theorem implies (with other results) that there is no polynomial time algorithm for MAX 3SAT to find an assignment satisfying $7/8+ \epsilon$ clauses of a satisfiable 3SAT formula unless $P = NP$.

There is a trivial polynomial time algorithm that satisfies $7/8$ of the clauses. How hard is it to find an assignment that satsfies at least $7/8$ of the clauses but no more than $7/8 +\epsilon $ for some $\epsilon \gt 0$? Is this task still $NP$-hard?

The PCP theorem states that for every $\delta > 0$, it is NP-hard to decide whether a 3CNF is satisfiable or at most $(7/8+\delta)$-satisfiable. Take such a formula $\varphi$ and add to it lots of copies of $(a \lor b \lor c) \land \cdots \land (\lnot a \lor \lnot b \lor \lnot c)$, where $a,b,c$ are new variables (by $\cdots$ I mean eight clauses, exactly seven of which are always satisfied). Suppose these clauses take up $(1-\epsilon)$ of the new 3CNF. This replaces the original $1$ vs. $7/8 + \delta$ to $\epsilon + (1-\epsilon)7/8$ vs. $(7/8+\delta)\epsilon + (1-\epsilon)7/8$, that is $7/8 + \epsilon/8$ vs. $7/8 + \delta\epsilon$. That's not exactly what you wanted since $\delta \neq 0$, but it's pretty close.


Finding negative cycle using Bellman Ford Given a graph with |V| vertexes and |E| edges, I have to find a negative cycle, if there is one, in a graph.
The wanted complexity is O(|V|*|E|).

I was thinking about using Bellman-Ford to solve the question doing this:
Do |V| iterations of Bellman-Ford, If there were no changes on the last iteration, there is no cycle of negative weight in the graph.
Otherwise take a vertex the distance to which has changed, and go from it via its ancestors until a cycle is found.
This cycle will be the desired cycle of negative weight.

The problem is, that no start vertex is given, and Bellman-Ford notes wether there is reachable negative cycle via the start vertex or not.
Assume that if we start from vertex a there won't be negative cycle and if the start vertex was b there will be one.
So if I choose a as a start vertex I'll miss the negative graph.

How can I solve that?
I thought about trying all the vertexes as start vertex but it won't be O(|E|*|V|).

Choosing a arbitrary vertex as source may not reach the negative cycle in the graph.

Assuming the graph is directed. The cycle may not be visited if there are vertices that the source node cannot reach, such as: (assuming $V_0$ is the source)

Graph containing different components or

There are vertices behind the source vertex.

So, the solution is to:

Set Dist[v]=0 for all v that has 0 in-degree (or alternatively, add an additional vertex as source, which connects to all other vertices with 0-weighted edges. (similar to Johnson's algorithm))
Run Bellman-Ford for V-1 iterations
Perform an additional iteration for marking negative paths (by ancestor backtracking)
Maintaining the minimum cycle while perform a BFS starting from the 0-in-degree vertices.


What is combinational circuit? I'm reading the Digital Design and Computer Architecture by David Harris, Sarah Harris. The authors give the following definition of combinational logic:

A combinational circuit’s outputs depend only on the current values of
the inputs; in other words, it combines the current input values to
compute the output... A combinational circuit is memoryless, but a
sequential circuit has memory. The functional specification of a
combinational circuit expresses the output values in terms of the
current input values.

However, they claim this circuit is not combinational:

because "node n6 connects to the output terminals of both I3 and I4". Indeed, it's one of the designated signs when a scheme can not be combinational but, according to the authors:

Certain circuits that disobey these rules are still combinational, so
long as the outputs depend only on the current values of the inputs.

As I'm able to catch on, the aforementioned circuit is the case: its output is 1 if and only if its inputs are both 1, otherwise the output is 0. So the output is defined as a function of the inputs (the AND function).
In fact, there was already a question about this circuit and it has an accepted answer. Here's an excerpt from it:

Circuit (d) cannot be written in this form [of formula], since the
outputs of I3 and I4 are wired together. What is the relation between
the input to the rightmost gate and the outputs of I3 and I4? Not
something that can be described combinatorially.

Unfortunately, I'm still confused due to

The circuit, regarded as a black box, is still in scope of the combinational logic definition: its output values depend only on the current values of the inputs;
The relation between the input to the rightmost gate and the outputs of I3 and I4 can be described through the function NAND of the circuit inputs and this function is quite "memoryless". It's not obvious  for me why we can't afford to depict a gate input using multiple outputs of other gates.

I need some elaboration. Maybe things would fall into place if someone provide a circuit example when two gates outputs is connected to one input and it actually causes "memory" (in contrast to the considered sample).

For me a short-circuit isn't combinatorial nor sequential. It's an error, it may fry the circuits.

The circuit, regarded as a black box, is still in scope of the combinational logic definition: its output values depend only on the current values of the inputs;

You can make a logic inverter with high power relays. You set opposite tensions, the relays or the wires connecting them turn into melted metal. You have a memorised effect (blown circuit) : It is sequential!


Impact on the order of elements on the cost of searching in a linked list I have the following homework question that I am struggling with. I have read the corresponding chapter from the book, but no guidance there.

Consider a linked list $X: X_1 \to X_2 \to X_3 \ldots$.
Assume that the cost of examining a particular element $X_i$ is $C_i$. Note that to examine $X_i$,
one needs to scan through all elements in front of $X_i$. Let $P_i$ be the probability of
searching for element $X_i$, so the total cost for all searches is
$$
\sum_{j=1}^{n} \left( P_j \cdot \sum_{i=1}^{j} C_i \right)
$$

Show that storing elements in non-increasing order of $P_i/C_i$ does not necessarily minimize the total cost.
Show that storing elements in non-decreasing order of $P_i$ does not necessarily minimize the total cost.

Any help and direction how to approach the problem will be highly appreciated.

I'm assuming costs are strictly positive. Otherwise it doesn't make much sense to consider the quantity $P_i/C_i$.

Regarding 1: Consider any order, and suppose that for some $i$, $P_i/C_i < P_{i+1}/C_{i+1}$. Suppose that we switch the elements $i$ and $i+1$. Say that we switched between $\ldots,A,B,\ldots$ and $\ldots,B,A\ldots$. Let $\Delta$ be the difference in average search cost (new cost minus old cost). When looking for $A$, which happens with probability $P_i$, we have to pay $C_{i+1}$ more. When looking for $B$, which happens with probability $P_{i+1}$, we have to pay $C_i$ less. So
$$ \Delta = P_i C_{i+1} - P_{i+1} C_i = (P_i/C_i - P_{i+1}/C_{i+1}) C_i C_{i+1} < 0. $$
In other words, the switch was beneficial. We conclude that the optimal arrangement is to store the elements in non-increasing order.

How I found this proof: I tried to construct a counterexample by trying a few examples on two elements, but I didn't work. So I decided to write the inequalities enjoyed by such a counterexample, and solve them in order to find one. The solution showed that in fact no counterexample is possible.

Regarding 2: This is quite easy to construct, especially in view of part 1, which gives a condition for optimality in case there are only two elements. I'm sure you can handle this part yourself.


$\epsilon$-approximation Sub-linear time monotonicity testing I have the following exercise I have been staring at for several hours to no avail.
Question:
Testing the monotonicity of a function - the case of bits: Given a function $f: [n] \rightarrow \{0,1\}$ and a parameter $0 < \epsilon < 1$, show an algorithm that runs in $O(\frac{1}{poly(\epsilon)})$ queries to $f$, with the following behavior:

if $f$ is monotone (i.e $\forall x, y \in [n]$ if $x \le y$ then $f(x) \le f(y)$, then the algorithm always outputs "yes"
if $f$ is $\epsilon$ far from monotone, then the algorithm outputs "No" with probability at least $\frac {3}{4}$.

Definition of $\epsilon$-far:
A list $a$ is $\epsilon$-far from a list $b$, both of length $n$ iff they differ in more than $\epsilon n$ indices.
I will greatly appreciate help, and show my (stale) thought process.

My thoughts:
Consider the following algorithms
Alg1

Pick a uniformly random position $i$ between $1$ and $n$.
let $v_i$ be the value at position $i$ in the list.
Use binary search to look for the value $v_i$ in the list.
If the binary search reported $i$ as the position of $v_i$ then
return Yes
else
return No

which is proven to always return "Yes" for sorted lists, and
given a list which is $\epsilon$-far from being sorted, it returns "No" with probability at least $\epsilon$.

Alg 2

Let $ h \leftarrow \lceil \frac{2}{\epsilon} \rceil $
Execute $h$ independent copies of Alg1 on the input list.
If all the copies answer "Yes"
Return Yes
Else
Return No

which is proven to always return "Yes" for sorted lists, and
given a list which is $\epsilon$-far from being sorted, Algorithm 3 detects it is not sorted, with probability at least $\frac{2}{3}$
It is also proven to be of (query) complexity
$h lon(n) =  \lceil \frac{2}{\epsilon} \rceil O(log(n)) = O(\epsilon ^{-1} log(n))$

What to do with all that?
I thought I could use Alg 2 for the case of the binary function $f$, and to find out if it is non-decreasing.
The problem is, binary search has too many queries.
So I have to skip the search, and probably use some kind of sampling.

Let's say I uniformly sample $k$ indices of the list, and later force $k=o(\frac{1}{\epsilon})$.
I will then test monotonicity on the sample, and return an answer accordingly.
I haven't the slightest idea if this holds the required probability constraint, or how to augment so it does.
I thought maybe it would make prooving easier if I were to use the number of indices in the sample, between the leftmost "1" to the rightmost "0" as a proxy for the probability bound, but this is as far as I went.

I will appreciate direction to this, or even a solution at this point.

Let $P$ denote the number of pairs of indices $i<j$ such that $f(i)=1$ and $f(j)=0$, and let $C$ be the minimal number of flips required to make $f$ monotone. First, we show by induction on $n$ that for every function $f$ defined on $[n]$ it holds that $C^2\le 3P$.
Suppose that the claim holds for $n$ and let $f$ be a function defined on $[n+1]$. We denote by $C(n),P(n)$ the number of corrections and monotonicity violating pairs for $f|_{[n]}$ correspondingly. Finally, let $w(n)$ denote the weight of $f$, i.e. $w(n)=\big|f^{-1}(\{1\})\cap[n]\big|$. Observe that if $f(n+1)=1$ then $C(n)=C(n+1)$ and the claim clearly holds, it thus suffices to focus on the $f(n+1)=0$ case. If $f(n+1)=0$ then $P(n+1)=P(n)+w(n)$ and $C(n+1)\le C(n)+1$. Applying the inductive hypothesis $C^2(n)\le 3P(n)$ we have:
$$C^2(n+1)\le C^2(n)+2C(n)+1\le 3P(n)+2C(n)+1=\\3P(n+1)+2(C(n)-w(n))- w(n)+1$$
Since $C(n)\le w(n)$ and $w(n)\ge 1$ (the claim is trivial for the constant zero function), this concludes the proof.
The above inequality yields a simple algorithm for testing monotonicity. Sample a pair $i<j$ uniformly at random and answer "no" if $f(i)>f(j)$. Let $q$ denote the probability that $i,j$ is such a pair, then $q\ge \frac{P}{n^2}\ge \frac{C^2}{3n^2}\ge \frac{\epsilon^2}{3}$. By repeating this procedure $\approx q^{-1}$ times, you obtain an $O\left(\frac{1}{\epsilon^2}\right)$ algorithm for separating the monotone from the $\epsilon$-far from monotone case.


Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems I was doing a few dynamic programming problems and I am struggling to understand the thought process required to come up with recurrences.

The first problem I solved was longest palindromic substring and I managed to solve it successfully using the following logic: I have a function f(i,j) which returns the longest palindromic substring between characters at positions i,j in the string. I came up with the following recurrence:

f(i,j) = true // if(s[i] = s[j])
f(i,j) = true // if(i>j)
f(i,j) = true // if(s[i] = s[j] and f(i+1, j-1) == true)
f(i,j) = false // otherwise

Using this recurrence I managed to solve the problem successfully.

The second problem I wanted to solve was Longest valid parentheses (which I want to do using DP not stacks). The question is: Given a string containing just the characters '(' and ')', find the length of the longest valid parentheses substring.

My initial thought process was that this was similar to the longest palindromic substring problem that I already solved. So I defined f(i,j) as a function that returns longest valid parenthesis between elements i,j. The recurrence I came up with is as follows - here I use -1 to indicate that f(i,j) does not form a valid parenthesis:

f(i,j) = -1 // if i == j
f(i,j) = -1 // if j=i+1 and ! (s[i] = '(' and s[j] = ')')
f(i,j) = 2 // if j = i+1 and s[i] = '(' and s[j] = ')'
f(i,j) = 2 + f(i+1, j-1) if s[i] = '(' and s[j] = ')' and f(i+1, j-1) > 0;
f(i,j) = -1 // otherwise

My code (written in java) for the top-down version of the above is (note: dp[][] was initialized to -2 indicating state i,j is not processed yet):

private int topDown(String s, int i, int j, int[][] dp) {
    if(dp[i][j] != -2)
        return dp[i][j];

    if(i == j)
        dp[i][j] = -1;
    else if(j == i+1 && (s.charAt(i) != '(' || s.charAt(j) != ')' ) )
        dp[i][j] = -1;
    else if(j == i+1 && (s.charAt(i) == '(' && s.charAt(j) == ')' ) )
        dp[i][j] = 2;
    else if(s.charAt(i) == '(' && s.charAt(j) == ')' && topDown(s, i+1, j-1, dp) > -1)
        dp[i][j] = 2 + topDown(s, i+1, j-1, dp);
    else
        dp[i][j] = -1;

    return dp[i][j];
}

This does not work for inputs like ()() as it will return 2 instead of 4.

I was unable to come up with a solution of my own so I looked it up online. I found a solution here.

In this case the author defines f(i) as the length of the longest longest valid, balanced parentheses substring which begins at index i. He then describes the recurrence as follows:

f(i) = 2 + f(i+2)   // if s[i] = "(" and s[i+1] = ")"
f(i) = f(i+1) + f(i + f(i+1) + 2)   // s[i]="(" AND s[i+1]="(" AND s[i+f(i+1)+1]=")"
f(i) = 0    // otherwise

I have not written/tested the code for the recurrence but I assume it is correct.

My questions are as follows:

When I was solving the problem initially I had not thought of writing it as a function of f(i). I only thought of it as a function of f(i,j) and that turned out to be wrong. So is there an easy way to tell just by looking at a problem what states should be computed? For example why can't I solve the longest palindromic substring problem as a function of f(i)? similarly why can't I solve the longest parenthesis problem as a function of f(i,j)?
Is there a way to solve the longest valid parenthesis problem as a function of f(i,j) where f(i,j) represents the length of longest valid parenthesis between i and j? It is ok if the runtime complexity is higher I am just curious about this.

Thanks.

Here is a way to solve the problem of longest valid parentheses by dynamic programming as you had hoped. Or almost.
For simplicity, a string is called valid if it consists of well-formed opening and closing parentheses.
The critical observation is that a string is valid if  it is the empty string, a concatenation of two valid strings or "(" followed by a valid string followed by ")". In fact, that observation is the usual recursive definition of well-formed opening and closing parentheses! That observation indicates that a suitable set of subproblems are s[i...j].

Let s be the given string of length L.

Let dp be an L by L+1 array of booleans.
dp[i][j] will become true iff the substring s[i,j] is valid. Here s[i,j] means the substring with indices from i inclusive to j exclusive, 0 <=i <= j < L. In particular, s[i,i] means the empty string.

Initially, all dp[i][j] are false.

The base case is the empty string, dp[i][i] = true for all i.

The recurrence relation is, according to the observation above, dp[i][j] = true for i < j if s[i] == '(' and dp[i+1][j-1] == true and s[j-1] == ')' or there is an index k, such that both dp[i][k] == true and dp[k][j] == true.  We can stipulate that i < k < j.

Here is the top-down version of the above approach, following the style in the question.
private static boolean topDown(String s, int i, int j, Boolean[][] dp) {
    if (i > j) return false;
    if (dp[i][j] != null) return dp[i][j];

    if (i == j) {
        dp[i][i] = true;
    } else {
        if (s.charAt(i) == '(' && s.charAt(j - 1) == ')' && topDown(s, i + 1, j - 1, dp)) {
            dp[i][j] = true;
        } else {
            for (int k = i + 1; k < j; k++) {
                if (topDown(s, i, k, dp) && topDown(s, k, j, dp)) {
                    dp[i][j] = true;
                }
            }
        }

    }

    if (dp[i][j] != null) {
        return true;
    } else {
        dp[i][j] = false;
        return false;
    }
}

Here is the bottom-up version. The code is sped-up a bit by the observation that a string can be valid only when its length is even.
private static int longestValidSubstring(String s) {
    final int L = s.length();

    // isValid[i][j] is true iff s.substring(i,j) is valid.
    boolean[][] isValid = new boolean[L][L + 1];

    // empty string is valid.
    for (int i = 0; i < L; i++) {
        isValid[i][i] = true;
    }
    for (int l = 2; l <= L; l += 2) {  // l is the length
        for (int i = 0; i <= L - l; i++) {
            // determine isValid[i][i+l]
            if (s.charAt(i) == '(' && s.charAt(i + l - 1) == ')' && isValid[i + 1][i + l - 1]) {
                isValid[i][i + l] = true;
            } else {
                for (int j = 2; j < l; j += 2) {
                    if (isValid[i][i + j] && isValid[i + j][i + l]) {
                        isValid[i][i + l] = true;
                        break;
                    }
                }
            }
        }
    }

    for (int l = L & 0xfffffffe; l >= 2; l -= 2) {
        for (int i = 0; i <= L - l; i++) {
            if (isValid[i][i + l]) {
                return l;
            }
        }
    }
    return 0;
}

The iterative version should be faster than the top-down version. However, even the iterative version is not fast enough when L is large since it computes L * L entries, which is pretty large once L is greater than 10000. Moreover, the two dimensional array isValid uses lot of memory as well.
Here is an improved solution of $O(n)$-time and $O(n)$-space. Here is the most brilliant solution, also of $O(n)$-time and $O(n)$-space. I will not discussion them, since they are out of the scope of this answer.

Is there a way to solve the longest valid parentheses problem as a function of f(i,j) where f(i,j) represents the length of longest valid parentheses between i and j? It is ok if the runtime complexity is higher I am just curious about this.

The fundamental quality of the subproblems in dynamic programming is that you can solve a larger subproblem more easily once you have the solution to the smaller subproblem. Or, you can extend or combine the solutions to the smaller subproblems to build a solution to the larger problem.
In this particular problem, if we know whether all shorter substrings are valid or not, then it is easy to know a longer substring that is slightly longer is valid or not. On the other hand, if we know all f(i,j), which represent the length of longest valid substring between i and j, the lack of specific location of those longest valid substrings does not help us determine whether a substring of a longer substring is valid or not. The difference is critical, although might be subtle to untrained eyes. You will learn to appreciate the difference.

When I was solving the problem initially I had not thought of writing it as a function of f(i). I only thought of it as a function of f(i,j) and that turned out to be wrong. So is there an easy way to tell just by looking at a problem what states should be computed? For example why can't I solve the longest palindromic substring problem as a function of f(i)? similarly why can't I solve the longest parenthesis problem as a function of f(i,j)?

As I have shown above, it is not necessarily wrong to use f(i,j) although we should give f(i,j) a slightly different meaning.  Solving a problem efficiently might not be easy, even if it is known to be solvable by dynamic programming. Quite a few problems puzzle me for a long time even if I consider myself experienced. It requires some intelligence and experience to identify or formulate the proper set of subproblems (which are not necessarily in the exact form of the original problem).
To extend a palindromic substring to a longer palindromic substring, you need to extend it from both sides. That indicates it may not easy to solve the longest palindromic substring problem as a function of a single variable that stands for the one end of the palindromic string in a simple and efficient way. However, if we analyze the fine structure of palindromes, we could arrive at the Manacher's algorithm
, which basically use a map from a single variable that stands for the center point of palindromic substrings.


Path of maximum value with bounded cost in DAG Consider a Directed Acyclic Graph in which every node has a value and a cost and edges do not have any weight. I need to find a path containing nodes such that sum of values of these nodes is maximized, but sum of cost over all these nodes must be at most C.

I am thinking of some modification of Dijkstra's algorithm. Any ideas? Is there any standard algorithm for this?

Consider a SUBSET SUM instance with weights $w_1,\ldots,w_n$ and target $C$. We create an instance of your problem, with the same value of $C$. There are $n+1$ nodes $v_1,\ldots,v_n$, where node $v_i$ has cost and weight $w_i$. There is an edge from $v_i$ to $v_j$ iff $i < j$.

Any directed path in this DAG corresponds to a subset of the weights $w_1,\ldots,w_n$. You are thus looking for a subset of the weights with maximal sum under the constraint that the sum is at most $C$. Thus the solution to your problem is $C$ iff the SUBSET SUM instance is a Yes instance.


Adding a character in the middle (rolling hash) Is there a way to support adding characters in the middle and update the hash in O(1) ?
All I have is the hash of ABBDE and I want to get the hash of ABBCDE.

With just the Rolling HASH for the whole ABBDE, you can not insert into the middle of it.

But...
   as I understand rolling Hash...

If you are building the hashes up as you go (adding into the middle, adding other entries), you would need a little extra information to be able to insert into the middle at a latter access.

As I see it , You need  need to know:

A) The whole hash (I assume you got by finding the entry there)
B) The hash for one of the halves (Left or Right)
C) A length of the HALF to know the offset that needs to be adjusted by.
D) An indicator to know which half is being adjusted to keep the halves balanced.`

Then all the parts can be used to recalculate, updated, replaced, and inserted to make new entries.

This would then give an O(1) time

BTW,  what is this for?

The answer to another question with a related general solution:
Finding Hash of Substring [i, j] in O(1) using O(|S|) pre computation


How does one efficiently produce all binary sequences with an equal number of 0's and 1's? A binary sequence of length $n$ is just an ordered sequence $x_1,\ldots,x_n$ so that each $x_j$ is either $0$ or $1$. In order to generate all such binary sequences, one can use the obvious binary tree structure in the following way: the root is "empty", but each left child corresponds to the addition of $0$ to the existing string and each right child to a $1$. Now, each binary sequence is simply a path of length $n+1$ starting at the root and terminating at a leaf.

Here's my question:

  Can we do better if we only want to generate all binary strings of length $2n$ which have precisely $n$ zeros and $n$ ones?

By "can we do better", I mean we should have lower complexity than the silly algorithm which first builds the entire tree above and then tries to find those paths with an equal number of "left" and "right" edges.

Obviously there are $4^{n}$ binary strings of length $2n$. To traverse the binary an algorithm has to visit each node once, i. e. it has to do
$$ \sum_{i=0}^{2n} 2^i = 2^{2n+1} - 1 = \mathcal{O}(4^n)$$
steps.

Let's consider a recursive algorithm which traverses the tree you described, but counts the number of ones and zeros on its way, i. e. it will only traverse the good part of the tree.
But how many such binary strings with $n$ 0's and $n$ 1's are there? We choose $n$ 1's for our strings of length $2n$ and use Stirling's formula in step 2:
$$ {2n \choose n} = \frac{(2n)!}{(n!)^2} = \frac{4^n}{\sqrt{\pi n}} (1 + \mathcal{O}(1/n))$$

EDIT
Thanks to Peter Shor's comments we can also analyse the number of steps needed by the second algorithm, which counts the 1's and 0's. I'm citing his comment from below:

  We want to find all binary sequences with exactly $n$ 0's and $n$ 1's. We traverse the binary tree where each node is a sequence of at most $2n$ 0's and 1's. We don't need to visit any node with more than $n$ 0's or more than $n$ 1's. how many nodes do we need to visit? There are ${i+j \choose i}$ strings with $i$ 0's and $j$ 1's. Summing this over all $i,j \leq n$ gives $\sum_{i=0}^n \sum_{j=0}^n {i+j \choose i} = {2n+2 \choose n+1} − 1$. Now, we need to visit each of these nodes at a constant average cost per node. We can do this by visiting each left child first, and each right child second.

Using Stirling's formula again we obtain
$$ {2n + 2 \choose n + 1} - 1 = 4^{n+1} \frac{1}{\sqrt{n+1}} (1 + \mathcal{O}(1/n)) - 1 = \mathcal{O}(\frac{4^n}{\sqrt{n}}) $$
as the running time of the new algorithm.


Complexity of recursive Fibonacci algorithm Using the following recursive Fibonacci algorithm:

def fib(n):
   if n==0:
      return 0
   elif n==1
      return 1
   return (fib(n-1)+fib(n-2))

If I input the number 5 to find fib(5), I know this will output 5 but how do I examine the complexity of this algorithm? How do I calculate the steps involved?

Most of the times, you can represent the recursive algorithms using recursive equations. In this case the recursive equation for this algorithm is $T(n) = T(n-1) + T(n-2) + \Theta(1)$. Then you can find the closed form of the equation using the substitution method or the expansion method (or any other method used to solve recurrences). In this case you get $T(n) = \Theta(\phi^n)$, where $\phi$ is the golden ratio ($\phi = \frac{(1 + \sqrt{5})}{2}$).

If you want to find out more about how to solve recurrences I strongly recommend you to read chapter 4 of Introduction to Algorithms.