There is a simple reduction from Hamiltonian path. Suppose we are given a graph $G$ on $n$ vertices, and want to know whether it contains a Hamiltonian path. Adjoin a new vertex $s$ and connect it to all other vertices. The new graph $G'$ contains a walk of length (at most) $n$ starting at $s$ and covering all vertices if and only if the original graph $G$ contains a Hamiltonian path.


Logic formula for exactly n unique objects (no more, no less)

You need to say that (a) there are at least $n$ elements, and (b) there are at most $n$ elements.
To express (a),
$$
L_n := \exists x_1\dotsc \exists x_n\, \left( \bigwedge_{1\le i < j \le n} x_i\ne x_j \right).
$$
To express (b),
$$
M_n := \forall x_1\dotsc \forall x_{n+1}\, \left( \bigvee_{1\le i < j \le n+1}x_i = x_j\right).
$$
So the sentence $L_n \land M_n$ holds iff there are exactly $n$ elements.


How does Knuth measure the running time of this program?

Knuth's $a$ is not standard notation. Here it's just a flag which is $0$ if the element was found and $1$ if it wasn't found. When I sum the elements in his table I get $6n + 10 + 3a$, so it's $6n + 10$ if the element is found and $6n + 13$ if it's not found (which is $3$ more).


explain ackerman's recursion. how long it takes to execute the following code for an average PC

The Ackermann–Péter function works as advertised, while not being primitive recursive. There is an abundance of literature on this function and its execution time. Growth in the second parameter depends on the first, it is a bit like going from counting to addition to multiplication to exponentiation ...
The execution time of the code shown is entirely irrelevant, as the values will almost immediately overflow anyways - googol is small compared to ack(4,2), googolplex dwarfed by ack(5, 1).


Union and intersection of a regular and a non-regular language

Note that the languages $\emptyset$, $\{\epsilon\}$ and $\Sigma^*$ are regular. Let $L_2$ be any non-regular language over $\Sigma$.

Union. $\emptyset \cup L_2 = L_2$, which is non-regular; $\Sigma^*\cup L_2 = \Sigma^*$, which is regular.

Intersection. $\Sigma^*\cap L_2 = L_2$; $\emptyset\cap L_2 = \emptyset$.

Subtraction. $\Sigma^*\setminus L_2 = \overline{L_2}$, which is non-regular, since regular languages are closed under complementation.  That is, if $\overline{L_2}$ were regular, then $\overline{\overline{L_2}}=L_2$ would also have to be regular.  $\emptyset\setminus L_2 = \emptyset$, which is regular.

Concatenation. $\{\epsilon\}\cdot L_2 = L_2$; $\emptyset\cdot L_2 = \emptyset$.


How can we design an efficient warehouse management program?

It looks like what you have is a variant of the knapsack problem.  However, you have an advantage that, rather than trying to optimize one "sack", you're simply trying to minimize the number of sacks (or in this case, pallets.)

I would have my program start by adding up the total height of the boxes I have to stack, and dividing it by the total height I could get out of each pallet if I could pack it perfectly (in this case, 7000mm).  If there's no possible way I could fit the boxes I'm given on less than three pallets, for example, I'm better off knowing that to begin with.

So once I've calculated my P, the number of pallets I may be able to fit my boxes on (if I'm lucky and calculate well) I'm going to start distributing my biggest boxes first.  I've got 5*P stacks to fill; I'm just going to go around them, always choosing the stack that's currently the lowest height to put the next box on.  I'll continue that as I run out of the biggest boxes and move on to the next biggest.

If I'm fortunate, this is all I'll need to solve the problem.  If I'm less fortunate, I'll have to have code that explores to see if swapping boxes around creates the room I need.  This is where the problem gets hairy; there's only so much you can do other than just plain trial and error.

In planning for that contingency, I might be well-advised to do some searching to see if there are any "perfect" stacks that can be made with the box sizes I'll have to work with (for instance, 7 of the 200 mm boxes make a perfect stack).  Any "perfect" stacks that I can make simplify the task of figuring out how to swap boxes between the remaining stacks ... or, regrettably, accepting that there's no way to swap boxes around so that they fit on our hoped-for number of pallets.


Is it possible to derive a deterministic CSPRNG given two functions, at least one of which is a CSPRNG?

No.  There's no way to create such an $h$.

Here's an informal sketch of the proof.  Suppose $f$ is a CSPRNG.  Then for all $h$, there exists a $g$ such that $h(f,g)$ outputs only even numbers.  In particular, $g$ reads the state of $f$, deduces what $f$'s next output will be, and outputs something that will cause $h$ to output an even number (if necessary, by generating multiple candidate outputs and testing each one to see which will provoke $h$ to output an even number).

[This is the main idea of a proof.  To get a full formal proof, you'd also have to consider the case where $h$ ignores its second input or mostly ignores its second input.  However, it's pretty easy to see that such a $h$ can't possibly be any good, either.]

That's the theory.  What about practice?  In the real world, if you're not sure whether $f$ or $g$ are any good, don't let them read the internal state of anything else.  Don't ever let something that might be malicious read the internal state of security-critical parts of your system.

If you know that $f$ and $g$ are independent (as random variables), and you know that at least one of $f,g$ is a secure CSPRNG, then $f+g \bmod m$ is indeed good (it's a secure CSPRNG).  However, the critical requirement here is that they be independent.  If one can read the internal state of the other, then they're not independent.


$\lambda$ (lambda) is sometimes used to denote the empty string.  Thus, a "lambda production" is a production like $A \to \lambda$, i.e., a production that allows a non-terminal to generate the empty string.

Other sources will use $\epsilon$ (epsilon) to denote the empty string.  They might refer to them as epsilon productions.  They're the same thing.  It's just a difference in notation.


Turing recognizable & decidable: binary strings with even length. Let A = {(M) | M is a DFA such that L(M) is not the same as EVEN}

The language is clearly recognizable: given a DFA $M$, simulate it, in minlex order, on every word, and see if there is a word $w$ such that $|w|$ is odd, and $w$ is accepted by $M$, or if there exists a word $w$ such that $|w|$ is even, and $w$ is not accepted by $M$. In both cases - accept.

However, this machine doesn't show the decidability of the language.

In order to decide the language, it is easier to proceed as follows: Let $A$ be a DFA that accepts the language EVEN. Fix such a DFA.

Now, given $M$, we need to decide whether $L(M)=L(A)$. If you feel comfortable with automata, you can just say that this is decidable, and that's it.

If you're not that comfortable yet, consider the following:
Given two DFAs $B,C$, it is easy to construct a DFA $D$ such that $L(D)=L(B)\cap \overline{L(C)}$, and it is also easy (well, decidable in NLOGSPACE) whether $L(D)=\emptyset$. The latter test is equivalent to deciding whether $L(B)\subseteq L(C)$. Thus, you can decide whether $L(M)\subseteq L(A)$ and $L(A)\subseteq L(M)$, which amounts to deciding whether $L(A)=L(M)$, and you are done.


Do we have knowledge bases only because the logics are not automated enough?

Most logical systems in use are automated enough in principle. That is, there are algorithms which find the proof of a statement, if such a proof exists. The problem is computational complexity. Such algorithms are very, very, very, very, very slow. We only know efficient algorithms for special, easy cases.

More generally, knowledge representation is not just about logical deduction. You cannot logically deduce the fact that after Monday comes Tuesday and that tigers have legs, that is something that the machine has to be told, and it has to then store such knowledge. How do we store knowledge? That is a question of expressivity of the symbolic representation (the thing you call "logic"), and it is an issue that is largely separate logical deduction.


calculate the effective (average) access time (E AT) of this system

I would approach it this way : Consider 1000 requests made by the processor - the number arrived at by ensuring whole number of requests to each storage. 90 % or 900 of those are served by the cache. Of the 10 % or 100 which are not, only 1 % or a single request faces a page fault and 99 are served by main memory.

The Expected time per request = ( 900 * 40 + 99 * 200 + 20000 ) / 1000 = 75.8 ns.

The speedup due to the cache is based on the ratio of number of cycles spent on a set of operations without the cache to the same set with a cache.


I'm not well aware of study pattern in your region, but I can advise you according to my own experience of 6 years in this field. I am in post graduation course.
One of the many things you need to know is CS is not all about programming, although most of the concepts you can relate to it and easily understand. Most importantly, its useless to learn every language, but mastery in any one language would be very helpful. Slowly you'll start understanding that all you need to understand is declaring variables, loops, functions and some built-in or library functions for a language, and it'll do most of your basic work.

Secondly, theory alone is of little use, except in the field of algorithms. From programming to digital and networking, you need to understand the practical examples. You need to start from "How will I do this?" then go for "what are the problems in my ways?" and then you'll almost always end up with adopting standard ways of doing things, this methodology will give you a lot of help.

Nothing is too difficult if you work hard and follow right approach. Computer science is a field where either you'll understand things or you won't. There is little to no use of understanding half things. You can't know half algo. You can't know OSI architecture upto 3 layers. You'll forget things if you do them that way. But once you have struggled enough, things would start relating so nicely that you'll easily be able to forecast solutions to a problem in one subject due to your experiences from other subjects.

My advice would be to go for the course if there is some curiosity in you when you think how facebook works? How Windows work? How am I connected? Why is everything 0 or 1? WHAT is 0 and 1?
All the best.


Find equivalence classes of language $L = \{0^n1^n, n \in \mathrm{N}_0 \}$

Let $\Sigma=\{0,1\}$. Here are all (Myhill–Nerode) equivalence classes, $O_0,O_1, O_2,\cdots, L_0, L_1, L_2, \cdots$ as well as $R$.

$$ \begin{aligned}
O_{k} &= \{0^k\},  \ \text{ where } k \in \mathrm{N_0}. \\
L_{k} &= \{0^{m+k}1^m: m \in \mathrm{N} \},  \ \text{ where } k \in \mathrm{N_0}. \\
R &=\{x10^n1^m: x\in\Sigma^*,\, n,m \in \mathrm{N_0},\, n\ge m\}\cup\{x0^n1^m: x\in\Sigma^*,\, n,m \in \mathrm{N_0},\, n<m\}
\end{aligned} $$

If $a\in O_{k}$ and $b\in O_{t}$, $k\neq t$, $a1^{k}\in L$ while $b1^{k}\not\in L$. So $a$ and $b$ are in different classes.
If $a\in O_{k}$ and $b\in L_{t}$, $a01^{k+1}\in L$ while $b01^{k+1}\not\in L$. So $a$ and $b$ are in different classes.
If $a\in O_{k}$ and $b\in R$, $a1^{k}\in L$ while $b1^{k}\not\in L$. So $a$ and $b$ are in different classes.

If $a\in L_{k}$ and $b\in L_{t}$, $k\neq t$, $a1^{k}\in L$ while $b1^{k}\not\in L$. So $a$ and $b$ are in different classes.
If $a\in L_k$ and $b\in R$, $a1^k\in L$ while $b1^k\not\in L$. So $a$ and $b$ are in different classes.

What remain to be proved are the following.

For any $k\ge0$, all elements in $O_k$ belong to the same class, which is true trivially since there is only one element.
For any $k\ge0$, all elements in $L_k$ belong to the same class.
all elements in $R$ belong to the same class.
$\cup_{k=0}^\infty L_k\cup R =\Sigma^*.$

I will let interested readers to fill in the details.

Now that the correct equivalence classes are shown, let me get to your questions.

  In the definition, nothing is said about $x$ and $y$ in $(xR_Ly)$. Do I have to assume that those are two arbitrary words that are already in $L$? (If not, then my approach doesn't work)

No, $x$ and $y$ may or may not be in $L$. Your approach doesn't work.

  For a fixed $n \in \mathrm{N}_0$ I think $\exists$ just one word in the class $C_n$. Then does it mean that the unique word in $C_n$ is only equivalent to itself?

I cannot find where $C_n$ is defined. If it is what I guess it is, there are more than one word in $C_n$. If it means $O_n$ I defined above, then it does have only one word, $0^n$.


Multi-dimensional knapsack seem appropriate. The additional dimensions are 1 if item is in group A, else 0, 1 if item is in group B, else 0, 1 if item is green, else 0, ... The maximum weights of additional dimensions are 6, 2 and then 2 for each color.

The condition that there must be exactly 6 items from group A could be forced by an additional dimension -1 if item is in group A, else 0 and maximum weight of -6. However, this is awkward.


Reason behind declaring iteration variables on a method level

No, this is not conventional if writing C++. People who do this might have a C background. Indeed, in old C89, you had to declare all variables at the beginning of your scope. Of course, even if you didn't start programming with C89, you might have been exposed to out-dated guides or material and you might have picked up the habit. As we know, it is sometimes difficult to unlearn something.
In general, variables should be declared as close as possible to their actual site of usage and thus we don't unnecessarily pollute the scope, exactly as you point out. This is also defensive programming, it helps readability and protects from mistakes.


How do I efficiently checking if a string matches any substring in a collection

I think the Aho-Corasick algorithm is your best bet here. The algorithm is designed to solve the set matching problem (essentially the one you've defined), in which you want to determine which elements of a set of substrings, L, can be found in a longer string, S.

It runs in time $O(n + m + z)$, where $n = \sum \limits_{l \in L} |l|$ (the total combined length of the substrings in $L$), $m$ is the length of S, and $z$ is the number of matches of $L$ in $S$.


You are absolutely correct.  Wikipedia has an error -- or perhaps, if we are feeling more charitable, we could call it an oversimplification.

It is not true that the running time is at most $O(|R|+|S|)$.  For instance, if we consider the case where the value of attribute $a$ is 42 for all elements of $R$ and $S$, we output $|R| \times |S|$ tuples.  It is also easy to see that the pseudocode does $|R| \times |S|$ iterations of the nested inner loop (i.e., that many iterations of the statement "Write output:"), so the running time is also $O(|R| \times |S|)$.

Here are some statements that are true:

If there are no repeated values of $a$ (i.e., each value for $a$ appears at most once in $R$ and at most once in $S$), then the running time for the merge is $O(|R|+|S|)$, and the size of the output is also $O(|R|+|S|)$.
If any value appears at most $c$ times in attribute $a$, where $c$ is a constant, then the running time for the merge is $O(|R|+|S|)$, and the size of the output is also $O(|R|+|S|)$.
If we count only the I/O complexity (the number of disk/cache transfer operations), and if memory is large enough to hold $|S|$ items, then the I/O complexity is $O(|R|+|S|)$... though the running time and the size of the output might be as large as $O(|R| \times |S|)$.  More generally, the same statement is true if any value for attribute $a$ appears at most $k$ times in $S$, and main memory is large enough to hold at least $k$ items (here $k$ does not need to be a constant).

So Wikipedia's statement is misleading or wrong or (at best) over-simplified.  Perhaps what they really meant was one of the bullet items above.  Your understanding is absolutely correct.


Math term for Associative arrays/Maps/Dictionaries

Function ($A \to B$). If that doesn't work for you, try a set of pairs (subset of $A \times B$).

Note that something like mutable state is not common in maths, outside of computer science.


Use of Big-O Notation: Size of Input vs Input

You have it backwards, but you are on to an important distinction.

$O(N)$ if $N$ is a number in the input is perfectly well-defined and can appear in, say, the $\Theta$-asymptotic of a runtime function.

In your example, note that $\sqrt{N} = 2^{w/2}$ and thus $O(\sqrt{N}) = O(2^{w/2})$ -- it's just another way of expressing the same function class, given the identity $w = \lg N$.

The distinction between $f(N)$ and $f(\langle N \rangle)$ is only important in the context of complexity classes. Many of those are defined along the lines of

  Class $X$ contains all problems for which there is an algorithm with runtime in $O(f(|x|))$ where $x$ is an input string.

For examples, see pseudo-polynomial problems/algorithms.


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

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

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

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

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


Computational complexity of the clique problem

Wikipedia is usually a good starting reference to well-known problems as the clique. There is a list of the fastest known algorithms for CLIQUE including references.

Apparently, the fastest algorithm we know runs in time $O(1.1888^n)$, so that's the best upper bound on the complexity of CLIQUE we have. As for lower bounds, we don't have a super-polynomial one, or otherwise P=NP? would have been solved.


k-center problem: proof for Gon algorithm gives a 2-approximation

If $k+1$ vertices are at least $h$ units apart, then no ball of diameter $< h$ can cover two of these vertices, hence you would need at least $k+1$ balls.
Since you want to have at most $k$ balls, $h$ must be at least the minimum distance of the $k+1$ vertices (pairwise).
Another way of phrasing it would be:

If you have a set $T$ of $k+1$ points, and at most $k$ balls of diameter $h$, then at least one ball must contain two points.  Let $d$ be the shortest distance between two vertices in $T$ (the two closest vertices).  Then $h \geq d$.

Taking the contra-positive of the lemma:  If $\text{OPT} < h$, then you cannot have $k+1$ points that have pairwise distance $\geq h$, or in other words, if  $\text{OPT} < h$ then

Any set with pairwise distance at least $h$ has at most $k$ vertices
Any set with at least $k+1$ vertices has a pair with distance less than $h$.


Proof that if a function is computable with standard programs it is computable with Turing Machines

To write a proof, you need to define your claim precisely. "Standard programs" is not a precise term.

However, if we define "standard program" to be, for example, any valid program in the C programming language, then you can write a proof. To prove this, you describe how to simulate any valid C-program with a Turing machine, or describe a "compiler" that takes a C-program and outputs an equivalent Turing machine. Since the C-language has many features, the proof will be long and tedious, but it is doable. I don't know if anybody has gone through the trouble to write a full formal proof.


Can Circuit Value Problem or HORN-SAT be reduced to PATH problem?

Hint: Reduce from the monotone circuit value problem. Let $X$ be the set of all inputs and internal gates in the circuit. Choose $T$ and $R$ so that an element is admissible if the corresponding input or gate is true (each AND gate will require one triple in $R$, each OR gate will require two). Choose $S$ to be the indicator of the output gate to complete the proof.


Minimum number of comparisons in comparison-based sorting algorithms

Suppose the input array has $n$ elements. The goal of the sorting algorithm is to compute a permutation of $\{1,2,\ldots,n\}$ - the permutation needed to sort the input.  Let $A$ be the set of these $n!$ permutations.

Similar to the "guess my number" game (or the game of 20 questions), each comparison can reduce the search space by a factor of at most $2$.  For example, after the first comparison is made, one obtains a partition $A= A_1 \cup A_2$, where $A_1$ is the set of permutations in $A$ that are consistent with the comparison and $A_2$ are the remaining permutations.  The search space for the output is now restricted to $A_1$.  In the worst case, the size of $A_1$ would be larger than that of $A_2$, and so each comparison reduces the size of the search space by a factor of at most $2$. After each comparison is made, the search space is restricted further to those permutations which are consistent with all the comparisons made so far.

Hence, the number of comparisons required to reduce the size of the search space from $n!$ to $1$ is at least $\log_2(n!)$.  The product $1 \times 2 \times \cdots n$ is at least the product of the last $(n/2)$ numbers, which is $(n/2)^{n/2}$, and is at most $n^n$.  Thus, $\log(n!)$ is sandwiched between $(n/2) \log (n/2)$ and $n \log n$, both of which have the same asymptotic growth rate $\Theta(n \log n)$.


Finding solutions to $n m\equiv x \mod n$

Let's solve the problem for a specific $a$. Observe that
$ab \equiv x \pmod{n}$ if and only if there exists a $m \in \mathbb{Z}$ such that

$\qquad ab + mn = x$

By the Bezout theorem, the above has solutions if and only if $x \mid (a, n)$ (the "if" arrow is the theorem, the "only if" arrow is trivial). One of those solutions can be found by the Extended Euclid algorithm, and all the others can be obtained observing that if $(b, m)$ is a solution, then

$\qquad \left( b + \frac{n}{(a, n)}, m + \frac{a}{(a, n)} \right) $

is also a solution. Repeating the above process for all $a \in \mathbb{Z}/n\mathbb{Z}$ yields all the pairs you are looking for. While it's rather naive, I don't think you can get much better than that if you're looking for all solutions.


The short answer is that no one knows what real randomness is, or if such a thing exists. If you want to quantify or measure the randomness of a discrete object, you would typically turn to Kolmogorov complexity. Before Kolmogorov complexity, we had no way of quantifying randomness of say a sequence of numbers without considering the process that spawned it.

Here's an intuitive example that was really bugging people back in the day. Consider a sequence of coin tosses. The outcome of one toss is either heads ($H$) or tails ($T$). Say we do two experiments, where we toss a coin 10 times. The first experiment $E_1$ gives us $H,H,H,H,H,H,H,H,H,H$. The second experiment $E_2$ gives us $T,T,H,T,H,T,T,H,T,H$. After seeing the outcome, you might be tempted to claim there was something wrong with the coin in $E_1$, or at least for some weird reason what you got is not random. But if you assume both $H$ and $T$ are as probable (the coin is fair), the probability of obtaining either $E_1$ or $E_2$ is equal to $(1/2)^{10}$. In fact, obtaining any specific sequence is as probable as any! Still, $E_2$ feels random, and $E_1$ does not.

In general, since Kolmogorov complexity is not computable, one can't compute how random say a sequence of numbers is, no matter what kind of claimed "totally random" process spawned it.


Real time application with DFA or NFA application

DFA/NFA in a real time application ? consider designing a parser for user inputs where each input is a word w="http://some-address.com?key[1]=value1&key[2]=value2..."

consider having each key[i] as the string ##i now you can easily build a regex /##./ to accept all input-strings having key values contained in w.

Since we have a regular expression that recognize this pattern there exists an equivalent NFA that recognizes such words, now your parser server can recognize http requests that holds information valuable to your application
and distinguish them from normal static requests for pages/images.

There is a big difference from Complexity to Decidability problems,
Decidability problems is a question whether for all inputs w the algorithm A will halt and yield a result, Not every problem is Decidable (i.e loop to infinity doesn't halts), moreover not every problem that is decidable has the same complexity.

problems can be solved by different algorithms Complexity analysis is about trying to understand the time/space complexity of a problem and its boundaries.

Moreover by Complexity analysis we can try and break up different problems into different classes, for example class A could be "All problems that have an algorithm solving them in (some_constant)(nlog(n) time" could be an hypothetical class of problems.

Here is some nice short video trying to summarize some of the ideas of Complexity.
https://www.youtube.com/watch?v=YX40hbAHx3s


Divide an array into two sub arrays such that their sums are equal and possibly maximum

The problem is NP-hard, by a straightforward reduction from the partition problem.  Therefore, you should not expect any efficient algorithm.  However, there is a pseudo-polynomial-time algorithm using dynamic programming (see pseudo-polynomial-time algorithm for the partition problem for inspiration).


Formal model of execution for Java (or general imperative language)

There is an (operational) semantics for Java 1.4 formulated in the $\mathbb{K}$ framework. Associated to this framework is a proof system called Matching Logic. While that page describes a prototype implementation, it seems that the functionality is being incorporated into the $\mathbb{K}$ framework tools themselves as kprover. Unfortunately, it seems the framework is in the middle of being updated, and getting the framework to build and work appropriately is a bit of a chore, and I'm not really sure how practical and/or functional kprover currently is. You could, however, manually prove things referencing the operational semantics (and also using the Matching Logic proof system if you like). The paper describing the Java semantics, K-Java: A Complete Semantics of Java, references some other systems that are less complete, but may be complete enough for your purposes. That said, they may well not be geared toward proving properties about Java programs. Indeed, in the paper, the semantics is being used for model checking rather than correctness proofs.

This is an answer if you want a high degree of confidence that the actual Java code behaves as you intend. If the goal is more verifying the algorithm than the specific realization into Java, then this is likely overkill. That said, you could easily formalize a simple imperative language in $\mathbb{K}$ if you only need basic imperative/OO features. Indeed, this is done as an exercise in the $\mathbb{K}$ framework tutorial. In fact, if you can reformulate your problem into the fragment of C the Matching Logic prototype supports, you could possibly use that as-is.


Known lower bounds on halting for finite machines?

It seems that your machine runs without any further input once it is
started. Whatever input it has is encoded in its starting state. Since
your machine is deterministic, there is at most a single transition
from each state. So the state-transition graph of your automaton is a
directed graph composed of paths that either are isolated cycles or
are simply open linear path from an initial node/state to a final node
(corresponding to a halting state without transition). There may be
any (positive) number of such paths, possibly only one. Actually, only one of these paths is relevant, the one containing the initial state.

Depending on whether the initial state of your automaton is on a
cyclic path or on an open path, the automaton will run for ever or
halt at the end of the open path. The former is identified by checking
whether a state is visited twice. The latter is identified by the fact
that a halting state (without transition) is encountered.

In the question, you do not give any constraint or information on the way states and
transitions are defined, other than the following:

from a given state, there is a transition function that gives you
the next state;
you can know whether two states are the same or not.

So the only way you can map the graph structure to reason about it is
to follow the transition function from state to state, even when
knowing the total number of states $n$.

With $n$ states, you can have a graph $C_n$ composed of one cycle of
$n$ states. You can also have a graph $L_n$ composed of one open
linear path of $n$ states starting with the initial state and ending
with a halting state. The former is non-halting, while the latter is
halting.

Still assuming you know the number of states, and using only the gven
primitives, the only way to find a difference is to follow $n-1$
transition. Then you are either in a halting or a non-halting state.
The former tells you that computation halts, while the latter tells
you it does not halt.

You clearly will not do better when you do not know $n$ in
advance. Actually, you then need only one more transition to detect that
the computation is not halting.

So there is no way to decide whether your automaton halts in fewer
steps, unless you have other means for analyzing the state-transition
graph.

In other words, the only way you can have a faster algorithm is to
have some formalism that structures the state-transition graph with
properties that can be used to analyze it without having to follow the
transitions.


Sampling from a Acyclic Deterministic Finite Automaton

Some rough thoughts:

As $M$ is acyclic and deterministic, each word $w$ in $L$ determines a unique path through $M$. Therefore, at each state $q \in Q$, we weight each transition based upon the number of valid subsequent paths (this is the size of the subset of $L$ with a particular prefix). This can be done recursively, and should be linear in the number of transitions.

Then, in order to sample, we can define a function $p: Q\times\Sigma \to R$ that gets us this 'weight' of a particular transition, and use this to define the probability of moving through that transition. At the end of this, rolling a die at each transition should get a normal sample.

I've probably missed something, but it seems like a decent approach.


While proving optimality of the A* algorithm, why can we change graphs?

No, it isn't a problem.

The whole idea is that the algorithm doesn't operate on a single graph, but rather on a family of graphs (with costs), determined by what the algorithm knows from the heuristic and the explored nodes. That family is denoted by $G_{n,\theta}$ in the paper.

The admissibility of the heuristic basically means that the actual graph is amongst the family $\{G_{n,\theta}\}_\theta$ for some $\theta$.

The proof of Theorem 2 says, that if the other algorithm established that the shortest path form $s$ to $t$ has cost $f(t)$ and $A^*$ expanded the node $n$ which the other hasn't, it means that the estimate of cost of $s \rightarrow t$ path via $n$ was lower than the actual $f(t)$, which means there is some graph in the $\{G_{n,\theta}\}_\theta$ family where the shortest path from $s$ to $t$ passes through $n$. Because the other algorithm didn't expand $n$, it is not admissible for the assumed graph family (because that particular graph would break it).

In other words, if the problem was eg. going from Madrid to Paris, the algorithm might have discovered that (for simplicity) you can get to Barcelona and Valencia in 300 km. Then you know the distance to Paris is $>$1000 km from Valencia, and $>$800 km from Barcelona. If the other algorithm hasn't expanded Valencia and tells you that the shortest path goes through Barcelona with distance 300 km$+$1100 km (for the stretch Madrid-Barca and Barca-Paris), it hasn't ruled out an (alternative universe) situation where the distance between Valencia and Paris was only 1050 km (and would be therefore shorter).

Apologies for distorting Europe a bit


Generating a random minimum spanning tree

Since there are just about 10 random points, the following simplest algorithm is should be fast and easy enough for your need.

Generate random points $p_i$, $0\le i\le9 $ in the grid, in whichever way you prefer.
Compute all Euclidean distances between each pair of points. (In fact, I believe for your purpose, the Manhattan distance should be fine as well. What is nice about Manhattan distance is that it is much easier to code and compute. The MST generated will be roughly the same.)
Compute the MST of the points with the distances between them.

There are many existing libraries that computing MST. You can just select any popular one that is convenient for you. I guarantee you that they will be fast enough for your need.


Minimum spanning tree and its connected subgraph

Flaws in the accepted answer: When I re-read the accepted answer given by @Mahmoud A. today, I find flaws in it.

Consider the figures for an example:

In this example, $e = CE$. In figure (5), the edge $CD$ in the cycle created by adding edge $e = CE$ into $T_H$ is not in $T_G$ shown in figure (2), but we have $w(CD)<w(e=CE)$. So the claim "For every other edge $e' \notin T_G$ in the cycle we have $w(e′)=w(e)$" does not hold.

Note: In the following, I fix the flaws. I leave the answer given by @Mahmoud A. as accepted because it is original and insightful.

Correction: While where is an edge $e \in T_G \cap H$ such that $e \notin T_H$ do:

Adding $e$ to $T_H$ to create a cycle $C$.

1.1 Because $T_H$ is an MST of $H$, for every other edge $e' \in C$ we have $w(e') \le w(e)$. Otherwise, for any edge $e' \in C$ such that $w(e')>w(e)$, $T_H + \{ e \} - \{ e' \}$ has smaller weight than $T_H$.
1.2 Let $e = (u,v)$. Remove $e$ from $T_G$. Then vertices $u$ and $v$ are separated into two different connected components, denoted by $U \ni u$ and $V \ni v$, of $T_G$. Because $T_H$ is an MST of $H$ (which includes vertices $u$ and $v$) and $e \notin T_H$, there must be an edge $e'' \in C$ which connects the two components $U$ and $V$ again.
We claim that $w(e'') = w(e)$. In 1.1, we have proved that $w(e'') \le w(e)$ (replacing $e'$ there by $e''$). If $w(e'') < w(e)$, then $T_{G} - \{ e \} + \{ e'' \}$ has smaller weight than $T_G$.
1.3 According to 1.1 and 1.2 above, there are an edge $e'' \in C$ such that $e'' \neq e \land w(e'') = w(e)$. We replace $e''$ with $e$ in $T_H$ to obtain $T'_H = T_H - \{ e'' \} + \{ e \} \in MST_H$.
Since $e'' \notin T_{G} \cap H$ and $e \in T_{G} \cap H$, $T'_H$ contains one more common edge with $T_{G} \cap H$ than $T_H$ does.

Rename $T'_H$ to $T_H$

EndWhile

After the loop we have $T_{G} \cap H \subseteq T_H$.


Why are these FIRST sets not combined into a single set?

There are three $A$-rules, each one with its right-hand side: $aB$, $bAb$, and $Bb$. Each produces a set as its value for $FIRST$. $FIRST(aB) = \{a\}$, and $FIRST(bAb) = \{b\}$.

In its turn, $FIRST(Bb) = FIRST(B)$ (because  $B$ does not derive the empty string), and $FIRST(B) = FIRST(cB) \cup FIRST(d) = \{c\} \cup \{d\} = \{c,d\}$.

Naturally, $FIRST(A) = \{a, b, c, d\}$.


Constructing a data structure supporting prioritized key lookup

One approach is to use $d$ binary search trees, one tree per element in $\mathcal{K}$.

The tree for $k \in \mathcal{K}$ stores all items $\hat{x_i} = (p_i, k_i, v_{k_i})$ such that $k_i=k$, keyed on the value $v_{k_i}$.

To insert an item, insert it into the appropriate tree.  This can be done in $O(\log n)$ time.

The lookup operation can be done by searching in each binary tree, and taking the best match.  When searching in the tree for $k \in \mathcal{K}$, you search for the key $y[k]$.  This takes $O(d \log n)$ time.

The successor operation can be implemented similarly to the lookup operation, and also takes $O(d \log n)$ time.

You can speed up the operations to take expected $O(1)$, $O(d)$, and $O(d)$ time (respectively) by replacing each binary search tree with a hash table.


FM-index and pattern search with wildcards

You are correct that w* is already addressed by fixed-substring search.  I'll give some pointers on general regex search; most text indexes can be searched for variable patterns with a bit of extra work.

First, backwards search is a consequence of the fact that the FM index and most full text indexes use suffix sorting with the most significant digit on the left, because virtually no one thinks in terms of prefix sorting with the MSD on the right.  If the latter were used the FM index would use forward search; it's simply a product of the choices made when setting up the data structure.   Another fact to note is that regex's can be reversed, so any pattern in the forward direction can be reversed and applied using backward search.

Search with wildcards is not hard to do, but it requires multiple branches through the wildcard matches, which must be searched through some sort of tree-traversal strategy, with backtracking and so on. This paper describes pattern-matching on Patricia trees for instance.

It's not that different from searching sequential text; in the FM index case you can always find the characters immediately preceding the matches found so far and determine if they match the pattern correctly.


How to use Sigma Scaling in a genetic algorithm

Well I just tried this :

(1.0/f(x,y))+1.0

a) 21.37858466 | After the reciprocate | 1.046775781
b) 1.425432689 | After the reciprocate | 1.701541369
c) 15.48548031 | After the reciprocate | 1.064576621
d) 14.56668667 | After the reciprocate | 1.068649791
e) 41.0387647  | After the reciprocate | 1.024367205

With these new fitness I used S=1

  fscaled = S + (fraw −fmean)/2σ

Mean = 1.181182154
Dev Std = 0.260649227

And this was my final result :

a) 0.742170015 | 14.8434003 %
b) 1.998198272 | 39.96396544 %
c) 0.776317134 | 15.52634267 %
d) 0.784130642 | 15.68261284 %
e) 0.699183937 | 13.98367874 %

These can be used with proportional selections.
I think this is the right way to use sigma scaling.
And I used the reciprocate plus one to make this a minimization problem.


Often, in mathematical terminology, the prefix co- refers to a dual in some sense. For complexity and computability classes, the prefix co- has a fixed meaning: if X is a class of decision problems, then co-X is the class of problems whose complement is in X. That is, if the problem “does this object have the property $P$” is in X, then the problem “does this object have the property $\neg P$?” is in co-X.

For example, RE is the class of semi-decidable problems, that is, problems for which there is a Turing machine that can verify a positive answer. Co-RE is the class of problems for which there is a Turing machine that can verify a negative answer. A well-known problem that is in RE but not in co-RE is the halting problem (intuitively, you can verify that a Turing machine halts by running it to completion, but if the machine runs forever, you'll never be sure).

NP is the class of problems for which a solution can be verified in polynomial time; equivalently, NP is the class of problems that can be solved by a non-deterministic Turing machine in polynomial time. Co-NP is the class of problems for which the absence of a solution can be proved in polynomial time. It is not known whether $\text{NP} = \text{co-NP}$.


An easy contradicting example is three points forming an obtuse triangle. Note that any Axis-parallel square containing $A$ and $B$ on its boundaries, contains $C$ in its interior and hence, the outer face is not bounded by a cycle since $AB$ is not an edge in the graph.


Complexity class of Determining Hamiltonian cycle

If every node has degree two, then the test for a Hamiltonian cycle boils down to testing connectivity, since the graph must then consist of 0 or more disconnected cycles.

The algorithm is as follows:

Choose a starting node v
marked[v] = true
x := v
while x has an unmarked neighbour u
    x := u
    marked[u] = true
if all nodes in the graph are marked, return true, else return false

Suppose we see $v_1 \cdots v_n$ in this process. Since each node has degree 2, we only stop when we see a node with both its neighbors marked, so $v_1 \cdots v_n$ is a cycle in the graph. Since we see two edges from each $v_i$, there can be no other nodes connected to any $v_i$ that are unmarked. Thus, either $v_1 \cdots v_n$ is all nodes in the graph, and there is a cycle, or there is another connected component, and there is not a cycle.

Clearly this test is linear time, so the problem is in $P$.


Pairwise hash functions that are independent from each other

If you select $h_1,h_2$ independently at random, then by definition

$$\Pr_{h_1,h_2}[h_1(x)=y \land h_2(z)=w] = \Pr_{h_1}[h_1(x)=y] \times \Pr_{h_2}[h_2(z)=w].$$

If your hash family is universal, then both probabilities on the right-hand side will be $1/|D|$.

In other words, if $H$ is universal, then it automatically follows that

$$\Pr_{h_1,h_2}[h_1(x)=y \land h_2(z)=w] = 1/|D|^2.$$

Every universal collection works -- no extra conditions or requirements are needed.


Where is the original literature for the specification of an Associative Array ADT?

The consensus from the available information I've found points to SNOBOL4, released in 1967, as the earliest implementation of "associative arrays".

This post on the Software Engineering community is very similar to your question and has some great info.

Chicago University - Intro to TCL course: Associative Arrays

  Associative arrays were first used in the programming language Snobol4 in the mid-1960s. They are a very common data structure in the Unix environment, being provided as the major data structure by languages like Awk, Perl, etc.


Could my algorithm be considered Divide-and-Conquer?

TL;DR
Divide and concur doesn't have any rigorous definition.  So any argument you make for or against will be just an emotional argument.  The situation is made worse by the fact that the task accomplished by this algorithm doesn't need D&C.  So, the answer is "probably".
Long version
One scenario where it would make sense to use D&C in finding the minimum is a distributed system (eg. Hadoop), where the size of input may require from you that you do computation in chunks.  The algorithm as you designed it is not suitable for this task because it would have to communicate the best result found so far to all parts of the program handling the computation of each chunk.  The version I've written below eliminates this problem by computing local minima for given sublists and then calculating the minima of the previously computed minima and so on.  This feels (remember emotional argument?) more like D&C.  Besides, it makes the algorithm more language-agnostic and eliminates the corner-case errors.

Empty lists have no minimum.
Lists with only one element have only one minimum (not two).
If a list happens to have more than one minimum element, then the second minimum will be equal to first minimum.
Solution doesn't require guessing the minimum before running the algorithm.

The code is set in Prolog.  I believe it is better than conventional pseudo-Pascal in that it allows to avoid "uninteresting" parts of the algorithm.
two_mins([], _, _) :- !, fail.  /* Empty list has no minimum */
two_mins([Min1], Min1, _) :- !. /* There is only one element */
two_mins([Min1, Min2], Min1, Min2) :- Min1 < Min2, !.
two_mins([Min1, Min2], Min2, Min1) :- !.
two_mins(List, Min1, Min2) :-
    length(List, N),
    LenA is N div 2,
    length(A, LenA),
    append(A, B, List),
    two_mins(A, Min1A, Min2A),
    two_mins(B, Min1B, Min2B),
    Min1 is min(Min1A, Min1B),
    /* In case A or B had only one element, we will get
       rid of non-instantiated solutions. */
    include(ground, [Min2A, Min2B], Ground),
    min_list([max(Min1A, Min1B) | Ground], Min2).


Any way to find a 3-vertex cycle in a graph using an incidence matrix in O(nm) time?

Let's assume first that your graph is connected, so that $m \geq n-1$. Convert your incidence matrix into an adjacency matrix in time $O(n^2) = O(nm)$. Now go over all $m$ edges, and for each edge $(i,j)$, go over all vertices $k$ and check in $O(1)$ whether $i,j,k$ is a triangle in the graph (using the adjacency matrix), for an overall running time of $O(nm)$.

If your graph is not connected, then use DFS/BFS to find its connected components, and run the procedure above on each of them. Assuming that the $i$th connected component consists of $n_i$ vertices and $m_i$ edges, the running time is $O(\sum_i n_i m_i) \leq O(\sum_{ij} n_i m_j) = O(nm)$.


Why isn't an edge-map graph implementation used in practice?

Assume we are dealing with the representation of a weighted graph. I will use Python as the programming language to illustrate the points, which will remain true largely if another programming language is used.
Let us call the graph representation raised in the question "hashmap from edges to their weights" or "edge-weight hashmap". I would agree that an edge-weight hashmap is seldom used to represent a weighted graph.
One overwhelming reason is that compared to edge-weigh hashmap, it is usually preferred to use the following popular variation of adjacency list, which I will call "adjacent hashmaps" or "nested hashmaps". The entire graph is represented by a big hashmap $g$, a.k.a. the outer hashmap, which is a collection of $(v, g[v])$ pairs, where $v$ is a vertex and $g[v]$ is a smaller hashmap, a.k.a. the inner hashmap. $g[v]$ is a collection of of $(u, w)$ pairs, where each vertex $u$ is a vertex that is adjacent to $v$ and $w$ is the weight of edge $(v,u)$.
An example

$\begin{array}{c|c}
 \text{Nested Hashmap} & \text{Edge-weight Hashmap} \\\hline
  \begin{array}{l@{}l@{}l@{}lll}
\{\\
\quad1: &\{2:2,&4:5\},\\
\quad2: &\{1:2, &3:14, &4:5, &5:4\},\\
\quad3: &\{2:14,&5:34\},\\
\quad 4: &\{1:5, &2:5, &5:58\},\\
\quad 5: &\{2:4, &3:34, &4:58\}\\
\}\end{array}                &
\begin{array}{lllll}
\{\\
\quad(1,2):2,           &(1,4):5,\\
\quad(2,1):2, &(2,3):14,&(2,4):5,&(2,5):5,\\
\quad(3,2):14,&(3,5):34,\\
\quad(4,1):5, &(4,2):5, &(4,5):58,\\
\quad(5,2):4, &(5,3):34,&(5,4):58\\
\}\end{array} \\
\end{array}$
The alignment of data entries above is meant for easy reading of Python code. By the general nature of hashmap, the actual storage locations of the entries in a hashmap are sort of unpredictable.

Comparison of complexity between nested hashmaps and edge-weight hashmap
$\begin{array}{|l|c|c|}\hline
&\text{Nested Hashmap} & \text{Edge-weight Hashmap}\\\hline
\text{Store graph} &O(|E|) &O(|E|)\\\hline
\text{Add vertex} &O(1) &O(1)\\\hline
\text{Add edge} &O(1) &O(1)\\\hline
\text{Remove vertex} &O(|V|)&O(|V|)\\\hline
\text{Remove edge} &O(1) &O(1)\\\hline
\text{Check if two vertices are adjacent} &O(1) &O(1)\\\hline
\text{List neighborhood of a vertex }&O(|V|) &?\ O(|E| )\ ?\\\hline
\end{array}$
The entry "$?\ O(|E| )\ ?$" entry on the column of "edge-weight hashmap" means that it is not clear how to list neighborhood of a given vertex $v$ efficiently. $O(|E|)$ refers to the time-complexity of the natural way, which goes over all the edges, keeping only the edges that contain $v$.
So both implementations have the same asymptotic time-complexity and space-complexity for all operations, except for listing the neighborhood of a vertex, arguably the most popular iteration on a graph, for which nested hashmaps are significantly faster. In practice, nested hashmaps should also exhibit better cache-friendliness.
Comparison of programming friendliness
Here are the code that does the basic iterations over a graph represented in variable $g$ using nested hashmap or edge-weight hashmap.
$\begin{array}{|l|l|c|}\hline
&\text{Nested Hashmap} & \text{Edge-weight Hashmap}\\\hline
\text{Iterate over all vertices} &\text{for v in g:} &???\\\hline
\text{Iterate over the neighborhood of vertex u} &\text{for v in g[u]:} &???\\\hline
\text{Iterate over all edges} &\begin{array}{c}\text{for u in g:}\quad\quad\\\text{ for v in g[u]:}\end{array} &\text{for e in g:}\\\hline
\end{array}$
The "???" entries on the column of "edge-weight hashmap" means that it seems rather clumsy to write that piece of code in Python or other programming languages, assuming their generally-available implementations of hashmap.
Nested hashmaps are far more programmer-friendly than edge-weight hashmap.
Summary
Although the time-complexity of the most basic operations using edge-weight hashmap are very good, it does not support the basic iterations well. It should be replaced by nested hashmaps in general.
Exercises
Exercise 1. Verify that this answer is applicable for weighted directed graph after slight adaptation. Verify that this answer is applicable for (unweighted) directed or undirected graph as well.
Exercise 2. Compare edge-weight hashmap with adjacent-weight list in detail. An adjacent-weight list for the graph above in Python can be $g=[[], [(2,2), (4,2)],$ $[(1,2), (3,14), (4,5), (5,5)],$ $[(2,14), (5, 34)],$ $[(1,5), (2,5), (5,58)],$ $[(2,4), (3,34), (4,58)]]$, where $g[v]$ is a list of $(u,w)$ pairs for vertex $v=1,2,3,4,5$ (g[0] is ignored since 0 is not a vertex), where $w$ is the weight of edge $(v,u)$.


Theoretical justification of "halting problem avoidance"

It is absolutely theoretically justified.

First realize that a loop is just a form of recursion: do the loop body, then either stop or do the loop body again with different variable values.

System F is a lambda calculus (programming language) with no recursion built in, and it is known to be strongly normalization. That is well typed every computation in this system halts. It's also powerful enough to compute basically every function you can think of, including the infamous Ackerman function.

In this system, you can use Church numerals to simulate the finite looping you mention in your question.

If you take a programming language without loops, you can model it in System F, which will give you a guarantee that all programs in this system halt.

It's implicit that if you remove loops, you also remove GOTO, which can be used to build loops.


When do we need U(n+2) to solve a problem that can be formulated in U(n)?

This question on the theoretical CS stack exchange asks if pentation is implementable on Church numerals in a predicative variant of System F. In the normal, impredicative system, this is quite easy, because we have:

ℕ : Type
ℕ = forall (R : Type). (R -> R) -> (R -> R)

1 : ℕ
1 R s z = s z

hyper : (ℕ -> ℕ -> ℕ) -> (ℕ -> ℕ -> ℕ)
hyper op m n = n ℕ (op m) 1

So, because a Church numeral can be instantiated to work on the type of Church numerals, we can easily iterate an operation to get to the next hyper operation.

However, in a predicative system, the quantification over types increases the size of the quantifying type to be larger than the size of the types quantified over. So, a Church numeral that can be instantiated to operate on Church numerals must be one that quantifies over a higher universe.

The person asking the question links to a paper on the functions representable in such a stratified system with $\omega$ universe levels (I.E. one for each natural number). The paper shows that the representable functions are the super-elementary functions, which includes tetration, particular finite compositions of tetration, and products and sums of those functions. However, the only reason that all these functions are even representable is that they make use of Church numerals for all universes. So, for instance, tetration has a type (something) like:

_^^_ : Church 0 -> Church 1 -> Church 0

That is, to compute tetration for 0-level numerals, you must make use of higher level numerals. And depending on the complexity of the function, you may have to use much higher levels to compute 0-level numerals (arbitrarily high levels).

I showed in the answer there how if you add even more universes, it is possible to give a uniform type for tetration, which then means pentation can be defined. But now the universes involved are indexed by transfinite ordinals (if at all), and you still (seem to) need to go up levels to define some functions on lower (but still very high) levels.


Disconnecting a complete graph by removing edges randomly

For your first question, an empty graph becomes connected roughly when $n\log n$ random edges are inserted into it, in a way quantified in Erdős and Rényi's fundamental paper On the evolution of random graphs, and recounted in textbooks on random graphs.

Your second question is not stated precisely and so is difficult to answer.


A simple way is the following:

Suppose that the increments are $+1, -1$; the number of states of the machine is $m$ and the current value of the counter is $n$.

You can notice that if the counter reaches $n+m+1$ without hitting the $0$, then by the pigeonhole principle the machine from value $n$ to $n+m+1$ has entered the same  state $s_i$ two times ($s_i \to ... \to s_i$), and the difference in the counter value is positive; so it will continue to repeat the same loop and increase the counter.

After hitting the $0$ - for the same reason - if the counter reaches $m+1$ then the machine will never halt.

So it's enough to simulate the machine up to $m(n+m+1)$ steps; if it doesn't halt in that time it will never halt: it will loop forever on the same values  $(s_i,c_j) \to ... \to (s_i,c_j)$ or increase forever the counter: $(s_i,c_j) \to ...\to (s_i,c_k) \to ...;\; c_k > c_j+m$ .

If the increments are $\pm v, v \in [1,h]$ then the machine can be reduced to an equivalent one with $\pm 1$ increments.


What kind of pattern recognition algorithm would Facebook use to detect suicidal users?

I would take march average to calculate several indicators from posts of the same user including but not limited to:
 - emotional-tagged words from posts (using available dictionary for this purpose)
 - sudden changes in the writting style
 - response times to messages
 - relationship changes
 - job changes

Also tagged messages reported by users, if it abides with policy also filtering concerns from private messages (reading them is probably illegal, but feeding machine learning scripts, maybe would be ok). For the supervised learning, the morbid idea is to feed learning algorithm the posts of people who made attempts.

To feed any data it should be preprocessed (to get rid of noise - texts that have no indicating value), possibly with included data about gender, age, education. Since it may not be properly filled in, maybe some additional scavenging and recognition of profile images (to determine age fir example) may be needed.

From reading the link it looks like scheme to allow flagging concerns, also the group of experts is reviewing the reports, so it is for sure mixture of unsupervised, supervised and experts learning system, scrapping every possible data.

To answer the main question, it depends on data acquired, resources available (for example how many review hours from experts they are willing to afford). The gathered data (and assumed certainty) shapes the used algorithms. The other problem is that there are no good enough tests to tell apart depressed or suicidal people apart based only on social media or written tests, so my bet is there are at least several algorithms formed into polling system, quite like ICD-11 or DSM-V diagnostic manuals, poll-based operationslisation of state to detect disorders. But the sentiment analysis gives roughly 20% of good results when used for opinions, for emotion detection it vastly degrades, so this approach would not be considered as is for safety reasons. The Stanford NLP unit works hard on higher level understanding of text, with sentiment analysis demo available. It works poorly for short texts, peaking at moderately long ones. It may be incorporated into longitudal working (time based consecutive tests), where afaik it could yield 25% for negative mind state of user.

Your idea of spam filtering may work in this context, where filter detects anomalies of behaviour or predefined patterns comming from tagged messages, but it must yield many false positives (due to weak patterns available).

The natural choice would be RNN, as Martin wrote, to account for dynamic temporal behaviour, if any other NN is used, such feature would be simply emulated, to match temporal behaviour of suicide plans. Estimating risk factors and including personal data (some auxiliary tests are required to asses personality traits, hopefuly these are quite accurate and work even in transparent setting, when someone is evaluated from behaviour), there should exist several time scale factors independently at least for every main personality type. The main disadvantage here is accuracy of profile data, for example five years inaccuracy in the age field filled by user matters. If someone for some reasons fills birthday date wrongly, the learning system cannot depend on valuable data what user does that day and whom meets. This may seem as tangential, but users privacy is important here, if someone feels insecure, the important data is lost, otherwise inferrence is inaccurate.

TLDR;
The algorithms used is not arbitrary chosen, it does not matter which one is performant or accurate for some tasks, it is data dependend choice, so it is hard to pick. Another factor is assesment, which is far from ideal. We can conclude that there are non-standard algorithms created solely for this task (perhaps including several known ones), but the heavy lifting is still done by people, as the machine learning works as screening test, flagging for review.

The fresh and interesting article about Predicting Risk of Suicide Attempts Over Time Through Machine Learning claims 80-90% accuracy, but is not applicable here, because it uses medical records to work.


Depth of binary tree with few single children

You can construct a tree with no single children which has height $(n-1)/2$:
.


How can I convert a for loop to a recursive function?

Here is a recursive version of this procedure, in python:

def cat(a,b):
  if a == b:
    return [a]
  else:
    return [a] + cat(a+1,b)

Another option is

def cat(a,b):
  if a == b:
    return [b]
  else:
    return cat(a,b-1) + [b]

These conversions are heavily geared toward this particular function. Here is a more general conversion, in the context of state machines without input (inputs can easily be added):

def run_my_algorithm(state = None):
  if state is None:
    state = initial_state
  if is_final_state(state):
    return extract_answer(state)
  else:
    state = next_state(state)
    return run_my_algorithm(state)

Hopefully the notation is self-explanatory.


Is any randomized Algorithm a probability distribution over the set of deterministic Algorithms?

You can think of a randomized algorithm as having access to a random variable $\mathbf{r}$, which informs its random decisions. For any fixing of $\mathbf{r}$, you get a deterministic algorithm, and in this way you can view the original randomized algorithm as a distribution over deterministic algorithms.
As an example, consider the randomized algorithm for solving MAX-3SAT. The algorithm chooses a random assignment. You can think of this assignment as specified by $\mathbf{r}$. Any particular assignment corresponds to a deterministic algorithm, and the original randomized algorithm is just the uniform distribution over these deterministic algorithms.


If O(log n) vs O(n) is exponential what is O(1) vs O(n)?

There's no name for that, but the closest would be "infinite" speedup. $O(\log n)$ is considered an exponential speedup over $O(n)$, because $n$ is exponential in $\log n$: if we take the exponential function $f(n)=2^n$, we get $f(\log n)=2^{\log n}=n$.

However, $n$ isn't anything in $1$: there's no way to recover $n$ from $1$, no matter how quickly the function $f$ that we take grows, $f(1)$ will always be a constant (and never equal $n$). As $n\to \infty$, $1$ becomes infinitely smaller than $n$.


How is the Longest Common Sub-sequence of two sequences is a special case of the Sequence Alignment problem?

The problem of finding a longest common subsequence can be answered by
computing the alignment where match is rewarded by +1 while mismatch and
insdel penalty are both 0.


Post numbers in DFS tree of an undirected graph

You conclusion is correct.

Here is (the sketch of) a proof.

If pre($u$) < pre($v$), the search must discover and finish $v$ before it finishes $u$, since $v$ is on $u$’s adjacency list. That is, post($v$) < post($u$) and $v$ is in the subtree rooted at $u$.
If pre($v$) < pre($u$), the search must discover and finish $u$ before it finishes $v$, since $u$ is on $v$’s adjacency list. That is, post($u$) < post($v$) and $u$ is in the subtree rooted at $v$.


If the matrix is diagonalizable then taking the $n$th power can be done in time
$$O(D(n)+ n\log n)$$
where $D(n)$ is the time to diagonalize $A$.

Just to complete the details, if $A=P^{-1}DP$ with a diagonal $D$, then
$$A^n = (P^{-1}DP)^n = P^{-1}D^nP$$

and $D^n$ can be computed by just taking each element of the diagonal (each eigenvalue of $A$) to the $n$th power.


Closure of regular Language - Transition Function : Sipser Proof

The idea is that whenever $A_1$ reaches an accepting state, it "guesses" that this is a good place to split the word, and run the second part in $A_2$. But maybe this guess is wrong? There are many ways to split a word, and you only need one such splitting to work.

As an example, consider the languages $L_1=(a+b)^*a$ and $L_2=b(a+b)^*$. Now consider what would happen in your suggestion with the word $aab$.
After reading the first $a$, $A_1$ will be in an accepting state, so it will move to the initial state of $A_2$, and upon reading the second $a$, will move to a rejecting sink.

However, as Sipser suggests, $A_1$ may continue using $\delta_1$ for the second $a$ as well, and only then move to $A_2$.

Same goes for the construction for Kleene star.


How to solve this max contiguous subarray sum with a twist?

Let the input array be $A[1 \dots n]$ and consider any contiguous subarray $A[i \dots j]$ of $A$ such that $i \le M-1$ and $j \ge M$ (that is, $A[i \dots, j]$ includes both $A[M-1]$ and $A[M]$).
The subarray $A[i \dots j]$ maximizes $\sum_{k=i}^j A[k]$ if and only if:

$A[i,\dots M-2]$ is a (possibly empty) suffix of $A[1 \dots, M-2]$ that maximizes $\sum_{k=i}^{M-2} A[k]$;
$A[M+1,\dots j]$ is a (possibly empty) prefix of $A[M+1 \dots,n]$ that maximizes $\sum_{k=M+1}^{j} A[k]$.

This is easy to prove using a cut-and-paste argument.
Notice that 1. and 2. are essentially the same problem, which can be solved by a trivial $O(n)$-time algorithm that computes the sum of all prefixes/suffxes of $A$.


Why do we need two variables for implementing kleene star operation on a language using context free grammars?

In the general case, your grammar generates more words than those in $L^*$. Consider this grammar:
$$
\begin{array}{l}
    S \to A
\\
    A \to (S)\ |\ a
\end{array}
$$
The above grammar generates $L = \{ a, (a), ((a)), \ldots \}$.
Using Kleene's star, we get $L^* = \{a,aa,a(a), ((a))(a), \ldots \}$. Note that $(aa)\notin L^*$.
However, if we add your proposed productions, we get
$$
\begin{array}{l}
    S \to A\ |\ SS\ |\ \epsilon
\\
    A \to (S)\ |\ a
\end{array}
$$
whose language is $L' = \{a,(aa),((a)a)(a), \ldots \}$, and this is a strict superset of $L^*$.
Your construction looks correct in the cases where $S$ never occurs in the right-hand side of a production in the original grammar.


Path optimization in a DAG: maximizing number of least cost arcs

I've not thought completely through it, but some thoughts on 1) which might be useful:

If you add a constant value k to each edge traversed, you could take into account the number of nodes traversed. In your case, this constant value k should be negative (e.g. the negative value of the maximum edge weight, in your example 11).

Then you might be able to state the following:

The path maximizes the number of least links if $\sum_{i=0}^n (a_i + k)$ < $\sum_{i=0}^m (b_i + k)$.

For your example: (let $P_i$ denote the $i$-th path and $C_i$ denote the costs of path $P_i$)

$P_A=[R, B, S], C_A = -2$

$P_B=[R, A, D, S], C_B = -11$

$P_C=[R, A, C, E, S], C_C = -20$

So $C_C < C_B < C_A$ and hence $P_C$ is your optimal path.

As mentioned, I've not spent too much time to look if there is an example where this approach does not work, but maybe it's a good point to start with.

Of course you get some ties with this approach as well but I think all of these ties are equivalent in the sense that the least cost arcs are traversed and the number of traversed vertices are equivalent. Correct me, if I'm wrong.


Ordering of conditions in multi-way conditional constructs

On what basis you want to sort out conditions conditions are not specific. If they are specific then you may sort out the conditions to not follow top down approach.

And conditions are the only thing that decide which condition next to be tested.
That is they handle the flow of your code and one condition is dependent on other.


How do I calculate Instruction Per Clock?

The computation of instructions per cycles is a measure of the performance of an architecture, and, a basis of comparison all other things being equal.  IPC can be used to compare two designs for the same instruction set architecture, as in the question you're asking comparing two design alternatives for a MIPS architecture.

Or, IPC can be used to compare vastly different designs (like CISC vs. RISC).  If the processor can execute one instruction per cycle, then the IPC=1. Especially processors in the 1970's were usually were microcoded, and instructions completed in a variable number of cycles, like some in 2 cycles or some instructions in 4.  So, for these machines IPC < 1.  Some processors using VLIW or EPIC or other architectural designs might complete several instructions in one cycle.

A MIPS processor attempts to execute one instruction per cycle using its pipelined design.  However, certain conditions cause it to stall:

waiting for a result that isn't ready, like multiply or divide
waiting for a cache miss to resolve

Other times, it does work, but the work must be thrown away — this is the case of the branch instruction.  More specifically, the issue of how soon the processor can get back onto the right instruction stream.

Let's look more closely at the pipeline for the question you're asking about:
Here the code sequence is

<x>
B trg
<a>
<b>
<c>

In the following, @trg represents the instruction at the target of the branch, and this is the proper instruction to execute immediately after the branch.

    IF       ID      EX     MEM      WB
-1  <x>
0   B trg   <x>
1   <a>     B trg   <x>
2   <b>     <a>     B trg   <x>
3   <c>     <b>     <a>     B trg   <x> <--- if the branch executes here in the MEM stage, then <a>,<b><c> are unwanted and have to be discarded.
4   @trg    <c>     <b>     <a>     B
5           @trg    <c>     <b>     <a>
6                   @trg    <c>     <b>
7                           @trg    <c>
8                                   @trg

The above shows the branch executing in the MEM stage.  Thus, the fetches the processor did for < a >, < b >, and < c > are invalid and have to be discarded.  Three cycles are lost or wasted.

    IF       ID      EX     MEM      WB
-1  <x>
0   B trg   <x>
1   <a>     B trg   <x>                 <--- if the branch executes here in the ID stage, then only <a> is lost
2   @trg    <a>     B trg   <x>
3             @trg  <a>     B trg   <x>
4                   @trg    <a>     B
5                           @trg    <a>
6                                   @trg

Since the ID stage is 2 stages earlier, this processor has a larger IPC.  We can use the IPC to ascertain exactly how much faster this design would be, and this demonstrates the value of the IPC definition.

(There is term in sailing and yachting called Velocity Made Good, VMG — the idea is that even though you're going a certain speed (in sailing: knots, in computing: cycles per second aka hertz), only some of that speed goes to useful work being done (in sailing: reaching the finish line, in computing: completing instructions from the program).  VMG for a processor would be instructions / hertz.  So, compared to VMG which includes a time component, IPC factors out the time component.)


Amdahl’s formula assumes that you know the percentage of execution time, but you only know the percentage of instruction. The percentage of execution time is 53.33%, not 30%.

The approach “total time before, divided by total time after” also works in more complicated cases.


How can I download a streaming file without the file's specific address?

What do you suppose happens in the back-end when you request a download of a file from a given location? The file gets converted to some encoding (in the most basic/general case: binary) and streamed over a network connection to you as a receiver.

Really for all practical purposes you wouldn't be able to distinguish downloading a 'real' file from download/receiving an active (bit)stream of that file as they're generally the same thing: bits being pushed across a connection.


Please refer this solution. Or see the paper by S. R. Mahaney, Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis (Journal of Computer and System Sciences, 25:130-143, 1982).


AI approach for exploring a static grid environment

Obviously one of the best learning methods that matches this problem is the Reinforcement Learning and to be more specific Q-Learning.
You'll find a good starting point here.
Hints: Q-learning is quite well-known and I don't repeat others here, but I give you the key point here.

At each step keep track of what happens (reward/punishment - no need to agent types,... if the environment stays fixed and you want to learn this Env. not the agents) using for example an array (Fortunately you're not learning anything so far!). Keep doing this until the agent stops, that as you said can have two reasons :

Agent's health drops to zero : Do nothing! (discard the array)
Agent leaves from the other corner : Apply the following rule with the values in the array


"Smallest set" term in the trees set definition

The set of unranked $Σ$-trees, denoted by $T$, is the smallest set of strings over $Σ$ and the parenthesis symbols ‘)’ and ‘(’ such that for each $a∈Σ$ and $w∈T^∗$, $a(w)$ is in $T$.

What we have here is an inductive definition. The base case is implicit because $\epsilon \in T^*$ even if $T = \emptyset$; making is explicit, the definition is (reading $a$ as free variable):

$\qquad\begin{align*}
&\ \phantom{\implies}\ a() \in T \\
 w \in T^+ &\implies a(w) \in T
\end{align*}$

The term "smallest set" is established, but somewhat silly, since all these sets are infinite; we mean the minimal set. Formally speaking, it's the smallest fixed point of this inductive definition; see here and here for some more on that.

As for you question, imagine this definition unfolding in an infinite process:

$a \in T \implies a(a) \in T$.
$a(a) \in T \implies a(a(a)) \in T$.
... and so on...

All you can ever do is wrap things in parentheses; thus you can never creates mismatching pairs like you propose.

A formal proof would be an induction along the inductive definition, of course!

Base case: all alphabet symbols have matching parentheses.
Inductive step: taking elements of $T$ with matching parentheses, those that are "one step larger" have matching parentheses as well.


It seems you are doing nothing wrong. Like you say, for a B-tree of order $n$ the number of children is between $\lceil n/2 \rceil$ and $n$, the number of keys is one less.
For $n=5$, keys are between $2$ and $4$. When you add a key to a node of size $4$, you get two new nodes of size $2$ and one new key which is pushed upwards. When this happens at the root, a new root with a single key is formed.

Your example. Add $T$ to the tree. At the root $G$ go right, to $\{H,K,N,Q\}$. With $T$ this becomes $\{H,K,N,Q,T\}$ which is too heavy and we split into $\{H,K\}$ and $\{Q,T\}$. Middle key $N$ is pushed upwards to the root. In the new configuration the root $\{G,N\}$ with two keys has three children $\{A,C,E\}$, $\{H,K\}$ and $\{Q,T\}$.


What parts of linear algebra are used in computer science?

The parts that you mentioned are basic concepts of linear algebra. You cannot understand the more advanced concepts (say, eigenvalues and eigenvectors) before first understanding the basic concepts. There are no shortcuts in mathematics. Without an intuitive understanding of the concepts of span and linear independence you won't get far in linear algebra.

Some algorithms only work with full rank matrices – Do you know what that means? Do you know what can make a matrix not full rank? How to handle this? You will have no clue if you don't know what linear independence is.

The Gaussian elimination algorithm that is used to solve linear equations can actually be numerically unstable if implemented improperly, and this is something that you might have to worry about in some cases. Without understanding the algorithm you won't know where the problem comes from and whether there's anything you can do about it – not at the level of algorithms for solving linear equations, but at the level of coming up with the correct linear equations to solve.

In short, don't be lazy, and take it on faith that these things are useful.


Subtracting a two's complement value from another two's complement value

Converting 6AD3 to binary gives 0110 1010 1101 0011 (the division to 4's is just to make it readable)

Converting AF20 to binary gives 1010 1111 0010 0000
To complement the latter in two's complement, we take the bitwise negation (one's complement) and add 1.

So the one's complement is 0101 0000 1101 1111, and adding 1 gives us
0101 0000 1110 0000
Adding this to 0110 1010 1101 0011 we have:

0101 0000 1110 0000

+

0110 1010 1101 0011

=

1011 1011 1011 0011

Which is BBB3.


Data structure with constant time operations

It is impossible to build a data structure that supports insert, maximum, and delete all in constant time. Such a data structure is a priority queue, and a priority queue with all constant-time operations can do heapsort in linear time. Since there is a superlinear lower bound on sorting, this is impossible. One of insert, maximum, or delete must be logarithmic time.

Certain species of tree (like those with lazy deletion and incremental partial rebuilding) require only insert to be linear time. A skew binomial heap requires only delete to be linear time.


Poly-time reductions for proving EXPTIME-hardness are _not_ enough?

If your problem can be solved in time $O(2^k)$, where $k$ is some number in the input, all you can say about its membership in conventional complexity classes is that it's in $\mathrm{2EXP}$, since an instance of length $\ell$ can be decided in time $O(2^{2^\ell})$.  You've not established that the problem is in $\mathrm{EXP}$.

$\mathrm{EXP}$, like all conventional complexity classes, is defined in terms of the length of the input, not the values represented in that input.


Question about the definition of complexity class oracles

Either you're misunderstanding what they said, or you're not misunderstanding anything.

If $B$ is a complexity class, then the class $P^B$ is defined as $\bigcup_{L \in  B} P^{L}$. (That applies even when $B$ does not have a complete problem.)

If $B$ is a complexity class and $K$ is complete for $B$ under polynomial-time Turing reductions, then $P^B = P^K$.

Proof: If those hypotheses hold then for all languages $L$ in $B$, by using the reduction to simulate oracle queries to $L$, one has $P^L \subseteq P^K$.

Thus, if those hypotheses hold then $P^K \subseteq \bigcup_{L \in B} P^{L} = P^B  = \bigcup_{L \in B} P^{L} \subseteq \bigcup_{L \in B} P^{K} = P^K$.

Therefore, if those hypotheses hold then $P^B = P^K$.


O(n) sorting array by value - get indexes

Every problem can be solved with yet another indirection:

First create B as an array of self-indexes - i.e set B[i] = i for all i.  Next create a 'comparator' object around A, which compares integers i and j by actually comparing A[i] with A[j].  Now sort B using this comparator.


How can Turing machines loop forever given that the input is finite?

It might help to think of Turing machines as a programming language. It's easy to see how a program in your favourite language might loop (its input is finite, too!) so you can translate that to a Turing machine.


What is the time complexity of this atrocious algorithm?

We can write a recurrence relation for this procedure as follows. Let $T(n)$ be the worst-case time for running sort on a list of length $n$. When calling sort on a list of length $n$, we can have up to $n$ recursive calls which rotate the list to the left until its minimum reaches the first entry. Each such call involves an invocation of minimum, and so takes $T(n-1) + O(n)$. The final one descends to sorting a list of length $n-1$. In total, we get the recurrence
$$
T(n) = n T(n-1) + O(n^2).
$$
Opening this recurrence, we get
$$
T(n) = O(n^2 + n(n-1)^2 + n(n-1)(n-2)^2 + \cdots + n!) = O(n!).
$$
(We get $O(n!)$ since the terms decrease very quickly from $n!$ to $n^2$, faster than a geometric series.)

Of course, without giving a matching lower bound, we don't know whether this analysis is tight.


I'm looking for a construct that is to semantic-analysis what NFA/DFA are to scanning and DPDA is to parsing

Repeated substring string replacement is Turing complete.

To emulate a Turing machine you can use the following:

The current string encodes the tape with a new symbol $\$$ followed by an encoding of the current state inserted before the position where the current head is. The allowed replacements can be encoded by taking each transition $\delta(n, b) = (m, c, N|L|R)$ by creating the replacement rules to replace $a\$nb$ with $a\$mc$ $\$mac$ or $ac\$m$ for not moving the head or moving it left or right where a is every symbol in the alphabet.


How to represent a double push or double pop operation in push down automata

There are several different definitions of pushdown automata. In the definition I know, every transition pops one stack symbol and pushes an arbitrary number of stack symbols. Thus you cannot "double pop", but you can push more than one element. You can simulate a double pop using $\epsilon$-transitions, but I'll let you figure that out.


Training and testing image sizes for classification in computer vision

It's important that all of the training and test images have the same aspect ratio but it doesn't necessarily have to be the natural one. If you think about it for a while you can see why that is. For example, if you're making a face detector and you have altered the aspect ratio to make all the faces look abnormally tall and skinny then you have a tall and skinny face detector. It won't work unless you do the same transform on the input images.

I'm not sure if I believe you about opencv making all the inputs to the cascade classifiers square. There is no reason it has to be square as long as all of the training images are the same size.


If $b$ is not a constant, then no, you can't say the number of levels is still $\log_b n$.

In your example, we have $T(n) = a T(\sqrt{n}) + c$ (since $n/\sqrt{n} = \sqrt{n}$).  There are more than 2 levels in the recursion tree.  In fact, there are $\lg \lg n$ levels in the recursion tree.  So, no, you can't just compute $\lg_{\sqrt{n}} n = 2$ and conclude that there are 2 levels in the recursion tree -- that gives the wrong answer.

(Why $\lg n$?  Suppose $n=2^k$.  Then each level halves $k$, so we do a total of $\lg k$ levels we get down to a constant.  Since $k = \lg n$, we get a total of $\lg k = \lg \lg n$ levels.)

The Master theorem gives a formula for solving this kind of recurrence, but it's only valid when $b$ is a constant.


The pumping lemma states that if a language $L$ is regular, then there exists a pumping length $p\gt0$ such that for all strings $s$ in $L$ with length at least $p$, there exists a way to split $s$ in the form $xyz$ such that all of the following are true:

$xy^iz\in L$ for all $i\ge0,i\in\mathbb Z$
$|y|\gt0$
$|xy|\le p$

The contrapositive is:

For all pumping lengths $p\gt0$, if there exists a string $s$ in $L$ of length at least $p$ such that for all ways to split $s$ in the form $xyz$, at least one of the three statements (those mentioned above) are false, then the language $L$ is not regular.

When you prove that a language $L$ is not regular using the pumping lemma, you generally assume that it is regular, and prove that the premise of the contrapositive of the pumping lemma is true. This implies that the language is not regular, leading to a contradiction.

Now, in your problem, you would like to choose the string $a^pa^p$. As you can see in the contrapositive statement, the choice of choosing $x,y,z$ does not lie with you. So, you need to show that the contrapositive holds true for every choice of $x,y,z$, i.e., at least one of the three statements in the pumping lemma is false for every choice of $x,y,z$.

So, in general,
$$a^pa^p=a^{2p}=a^ia^ja^k$$
for some $i,j,k\ge0$ and $i+j+k=2p$. Note that $j\gt0$ for statement 2 to be true, and $i+j\le p$ from statement 3.

Now, all that needs to happen is $j$ to be even and $i=k$,which, in general, is possible as all possible ways of splitting the string need to be taken into account that suppose $j=2l$ for some $l\gt0$.
Then,
$$a^pa^p=a^ia^{2l}a^i=a^{i+l}a^{i+l}$$

Now, as per statement 1, suppose we pump $y$, we get $a^i(a^{2l})^na^i\in L$ for all $n\ge0,n\in \mathbb Z$. Note that for every choice of $n$,
$$a^{i+ln}a^{i+ln}\in L$$

So, for this string $s$, we have managed to find a way to split it, for any $p$, such that all the conditions of the pumping lemma hold. This does not show that the premise of the contrapositive is true, and hence does not lead to a contradiction. Thus, to show that it is not regular, you need to choose a more suitable string $s$ for all $p$ that results in the premise being true, which would imply that $L$ is not regular, leading to a contradiction.


Formula for sufficiently lengthy encryption key?

That's not how security works. Sometimes you want to use encryption in circumstances in which there are two possible messages, and you want encryption to be secure even in these cases. That's because encryption is used as a building block in more complicated cryptographic protocols. Also, attacks could be based on multiple related (or even unrelated) messages.

Instead, security is based on the fact that nobody can try and decrypt a message with respect to all possible keys since there are too many, and there is no better way of finding the key. The second requirement is security of the cryptosystem, and currently there is no way to prove it. Instead, we use standard systems which are being researched and so far have revealed no weaknesses.

Suppose that our system is cryptographically secure. How can we guarantee that there are too many keys to try all of them? The standard approach is to agree on a key length in advance, usually 128 bits (or more). Classical (rather than quantum!) computation cannot run $2^{128}$ steps even if you parallelize it across atoms of the universe, and wait a million years. That's considered secure enough.


How do I calculate response time of a multiple core cpu when given certain information?

I think you don't need to add (7*number of cores) to the total response time. The overall execution time requires just 7 more seconds, because each piece of code is running in parallel with others. So just divide 200 by the number of cores and add 7 to it. Obviously in the ideal case you don't need to add anything. Also look at the Amdahl's law in the Wikipedia... It also states a law about speedup with parallelism and these problems share the same concept.


Unable to understand control flow in KMP algorithm

As explained in the comments, indentation marks code blocks. It is a standard way to denote them. while of line 6, repeats line 7, but has nothing to do with the if on line 8.
Indeed it only matters whether q and k are not zero.


What determines valid and invalid turing machines?

If you are referring to what I think you are referring to then your understanding seems correct.

A Turing machine has a precise definition: It is a tuple ... see for example
http://en.wikipedia.org/wiki/Turing_machine#Formal_definition

Any system with the same components and conditions as described by the definition is indeed a Turing machine.  Anything else (which may at first glance appear to be a Turing machine) is not a Turing machine.

This distinction is to weed out some wrong intuitions.
Here is an example adopted from:
https://stackoverflow.com/questions/2435607/why-is-this-an-invalid-turing-machine

For example (given a polynomial P as input):

Start counter at 0
   Start Zero at False
   while(not Zero) {
      eval P(counter)
      if ^^ is 0 set Zero to True
   }
   Return True

Can be computed by a Turing machine (i.e. describes a valid Turing machine) while

Start list at []
   Start counter at 0
   while(true){
      add eval P(counter) to list
   }
   if any element of list is 0 return true else return false

Describes an invalid Turing machine, i.e. the code does not correspond to a Turing mahcine.

Well ^^ is all I can come up with.  Maybe it will help.


Meaning of Steve Wozniak's epiphany on register addition/subtraction in 1975?

This was 1975. Microprocessors were not common knowledge. Wozniak had some experience with mainframe computers, but most likely hadn't seen a 4004 processor ever.

Reading the instruction set of the 6502 processor showed him that this wasn't a useless toy but a real computer. The original price for a 6502 was 25 dollars plus 10 dollars for the documentation (which you were encouraged to copy), compared to a 6800 for $300 including added chips that were required.

Wozniak's epiphany was realizing that you could take a $25 microprocessor and turn it into a real computer. Apple Inc. is now valued a bit over 700 billion dollars, a direct consequence of Wozniak's realisation, so this was a kind of important event.

Not that it has much to do with computer science, except that eventually it put computers into everyone's hands.


Why SAT Requires A Non-determinstic Algorithm?

It is not true that it requires a non-deterministic algorithm.

You are right; if it is solvable, it should be solvable by a deterministic algorithm. And it is. This deterministic algorithm needs exponential number of steps (with respect to number of propositional variables $n$) because only known general case approach so far is to test all combinations of truth values of propositional variables, and we have $2^n$ possible combinations (rows of a truth table).

However, we can (theoretically) solve it with a non-deterministic algorithm in polynomial time which is how a class of NP problems is defined. This is where your confusion, and maybe a bad choice of words in the literature, probably comes from.

All non-deterministic algorithms can be simulated by a deterministic algorithm. In fact, all that is computable can be computed with a deterministic algorithm. It is just the time complexity that varies.


Let me restate the problem.  We're given an array $A_0$ and a sequence $(\ell_1,r_1),\dots,(\ell_m,r_m)$.  Set $A_{i+1}=\text{reverse}(A_i,\ell_i,r_i)$.  The goal is to compute the array $A_m$.

The naive way to solve this is to just incrementally apply the reverse operations, i.e., incrementally invoke Yuval's reverse algorithm $m$ times.  The running time of the naive solution is $\sum_{i=1}^m (r_i-\ell_i)$.  The question is, can we do better?

The answer is, yes, in some cases.  It's possible to build a data structure to optimize the sequence of reversal operations, in a way that's faster than the naive solution.  With sufficient cleverness, you can get the total running time down to $O(n + m \lg n)$ -- in comparison, the naive algorithm could potentially be as large as $O(nm)$, in the worst case.  I'll explain how to do it below.

We can model the desired rearrangement by a permutation $\pi$ on the array indices.  Such a permutation acts on arrays: given any array $\pi$ and any permutation $\pi$ on the indices, we can obtain an array $\pi A$, namely, the array $A'$ given by $A'[\pi(j)]=A[j]$.  Notice that the operation $\text{reverse}(A,\ell,r)$ should return the array $\pi A$, where $\pi(j)=\ell+r-j$ for $\ell \le j \le r$ and $\pi(j)=j$ for all other $j$.  Let $\text{rev}(\ell,j)$ denote this permutation.

This gives us a new strategy for solving the problem: first, compute $\pi = \text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_1,r_1)$; then, compute $A_m = \pi A_0$.  The latter step can be done in $O(n)$ time, with no additional space.  So, how quickly can we compute $\pi_m$?

Here is one way to compute $\pi_m$.  We will represent a permutation $\pi$ as an interval tree, i.e., a binary tree where each leaf has an interval on the indices.  The intervals on the leaves will be pairwise disjoint, their union will be $\{1,2,\dots,n\}$, and they will be in sorted order (from left to right).  Each internal node will hold an interval representing the union of the intervals on all of its descendants.  Also, we'll annotate each leaf with an affine function of the form $f(x)=x+\alpha$ or $f(x)=\alpha-x$.  The idea is that if we have a leaf with interval $[a,b]$ and function $f$, then $\pi(j)=f(j)$ for $j=a,a+1,\dots,b$.

In this way, we can represent a permutation as this sort of interval tree.  Notice that the identity function can be represented as an interval tree with one leaf, with interval $[1,n]$ and function $f(x)=x$.  Also, the permutation $\text{rev}(\ell_m,r_m)$ corresponding to a single reversal operation can be represented as an interval tree with three leaves, namely $[1,\ell_m-1],f(x)=x$, $[\ell_m,r_m],f(x)=\ell_m+r_m-x$, and $[r_m+1,n],f(x)=x$.

Now suppose we have an interval tree representing $\text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_{i+1},r_{i+1})$.  Let me explain how to derive an interval tree representing $\text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_i,r_i)$.  Basically, we search the interval tree to find all leaves whose interval overlaps with $[\ell_i,r_i]$, and split them in two pieces if they partially overlap (one piece that doesn't overlap, the other piece containing the rest that is contained within $[\ell_i,r_i]$).  Then, for each such leaf that overlaps $[\ell_i,r_i]$, if it currently contains the function $f$, we replace it with the function $g \circ f$, where $g(x)=\ell_i+r_i-x$.

So, we iteratively do this.  When we're done, we have an interval tree representation of $\pi$.  Now we can compute $\pi A_0$ in linear time.  The running time to construct the interval tree is now dependent on the number of intervals that get treated differently.  In other words, say that indices $j,j'$ are treated differently if there exists some $i$ such that $j\in [\ell_i,r_i]$ but $j'\notin [\ell_i,r_i]$ (or vice versa); otherwise, say that $j,j'$ are treated the same.  Now construct the equivalence classes of the "treated the same" equivalence relation.  Each equivalence class is one interval in the final interval tree, so the total running time is related to the total number of such equivalence relations.  In particular, if there are $k$ intervals in the final interval tree (i.e., $k$ such equivalence classes), then the running time is $O(mk+n)$.

It's possible to speed this up even further by annotating each internal node with an affine function as well.

The idea is that such an interval tree represents a permutation $\pi$ as follows: if we have a leaf with interval $[a,b]$ and function $f_0$, and its parent has function $f_1$, and its grandparent function $f_2$, and so on up to the function $f_d$ on the root, then for every $j \in [a,b]$, we have $\pi(j) = (f_d \circ \cdots \circ f_1 \circ f_0)(j)$.  In other words, the effective function on this leaf is the composition of all of the functions on the path from the leaf to the root.

This tree representation is even better: it allows you to derive the tree for $\text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_i,r_i)$ from the tree for $\text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_{i+1},r_{i+1})$ in $O(\lg k)$ time, where $k = $ the number of intervals in the tree.  Basically, we may have to split at most two intervals (one on the left side, if it partially overlaps $[\ell_i,r_i]$ on the left, and one on the right).  Then, we need to compose a function $g(x)=\ell_i+r_i-x$ to all of the leaves whose intervals is contained within $[\ell_i,r_i]$.  The latter can be done by identifying $O(\lg k)$ nodes of the tree whose (disjoint) union is $[\ell_i,r_i]$ (by construction you can always find such a set of nodes), and then composing $g$ with the function at each of those nodes: for each such node, if its function was $f$, you update it to $g \circ f$.

Consequently, the total running time of this improved solution is $O(n + m \lg k)$, where $k$ is the number of intervals in the final interval tree.  A conservative upper bound is $O(n + m \lg n)$ to perform $m$ reversal operations on an array of size $n$.  This is better than the naive algorithm, whose running time could be as bad as $O(nm)$.


I know of no convention; the right result depends entirely on what you want to do with the result.  As an example, if you're trying to use strongly connected components to find satisfying assignments for 2SAT instances, then you likely want all the singleton cycles returned along with the larger components.  But if you're just trying to find out if a graph contains a cycle, then the singletons won't be of interest to the caller so the SCC function could usefully omit returning them.


Is this relation in Boyce-Codd's Normal Form?

Assuming that each book has a different title, you are correct in thinking that the relation is not in BCNF.
In fact, the (only) candidate key of the relation is  Book_title, so the functional dependency User_id -> User_name violates the definition of BCNF. Assuming that a cover of the dependencies are:
User_id -> User_name    (each user_id identifies a user with a certain name)
Book_title -> User_id   (each book can be borrowed only by a certain user)

a decomposition of the original relation in BCNF is:
R1(User_id, User_name)  with candidate key User_id
R2(Book_title, User_id) with candidate key Book_title


Solve a recurrence by drawing the recursion tree?

Use the Akra-Bazzi method. In terms of the notation there you have:
$$
\begin{align*}
g(x) &= \frac{x}{2} = O(x^c) \\
a_i  &> 0 \quad \forall i \\
0 &< b_i < 1 \quad \forall i \\
\end{align*}
$$
The requisites check out (and the somehow implied differences $h_i(x)$  due to truncation if the divisions don't come out exact also check out). So we need the $p$ for which:
$$
\left( \frac{1}{5} \right)^p + \left( \frac{4}{5} \right)^p = 1
$$
which is seen to be $p = 1$. Plugging into the equation:
$$
T(x) = \Theta \left( x^p \left( 1 + \int_1^x \frac{g(u) d u}{u^{p + 1}} \right) \right)
     = \Theta (x (1 + \frac{1}{2} \ln x))
     = \Theta (x \ln x)
$$


How to search an almost sorted array faster than O(n) time?

Let's say you have n = 100, $a_1 = 50$, $a_{100} = 100$, and $a_{50} = 73$. You would then know that the range from $a_1$ to $a_{50}$ contains all numbers from 50 to 73, and maybe some others, and the range $a_{50}$ to $a_{100}$ contains all numbers from 73 to 100, and maybe some others.

I think binary search will actually work, if the number you are looking for is within the interval from the first to the last array element. You will always know one half which must contain the number you are looking for, and one half which might contain the number so obviously you search the half that must contain it.

If the number is outside that range, you may have to check every single item: You could have $a_i = 0$ for every $i$ except $a_k = 1$. You can examine $n-1$ items $a_i$ which are all 0, and you still don't know if 1 is in the array or not; the one remaining element could be $-1$, $0$ or $+1$.


Algorithm: Finding shortest path through a dungeon in a game

Travelling Salesman Problem, even if you allow repeating nodes is NP-hard. See Computational Complexity of TSP.

Umans and Lenhart show hardness results for Hamiltonian Graphs in Solid Grid Graphs, 1997.

TSP for Euclideal Case (or graphs with triangle inequality) also imply NP-hardness of TSP with node repetition. TSP even for manhattan distance $L_1$ (or $L_\infty$) metric is NP-complete. See the original Papadimitriou's paper on the topic.

You may be able to prove NP-hardness of TSP for your case by adding arcs to nodes that have corresponding distance as length of shortest path between nodes which will simulate repetitions of the nodes. TSP for your special case looks like an NP-complete problem.

So either write a sufficiently good (heuristic wise) exponential branch and bound algorithm to compute a shortest tour (which may not be all that inefficient, if your graph is small) , or forget about optimization and calculate a good enough approximation.


Understanding lexical grammar for multi-line comments in JavaCC

Let's write this in a more manageable way. I'll use $x$ for any symbol other than $/$ and $*$. Your expression is
$$
/* (/+x)^* * (x(/+x)^** + *)^* /
$$
Now let us apply the following identity to the part "$*(x(/+x)^**+*)^*$":
$$
r(sr)^* = (rs)^*r
$$
We get
$$
/* (/+x)^* (*x(/+x)^*+*)^* */
$$
It's clear what the outer parts $/*$ and $*/$ do, so let's focus on the inner part
$$
(/+x)^* (*x(/+x)^*+*)^*
$$
which captures all strings not containing the substring $*/$. Using the identity
$$
(rs+r)^* = (r^+s)^*
$$
we can simply it to
$$
(/+x)^* (*^+x(/+x)^*)^*
$$
Essentially, each run of stars is "guarded" by a following $x$.


Polynomially reducing NP-Complete problem clarification

Since 3COL is NP-hard and X is clearly in NP, by definition there is some many-one reduction from X to 3COL, though it may be awkward to state. There is a simple oracle reduction along the lines outlined in the other answer: remove each edge at a time, and check if the resulting graph is 3-colorable.

More interesting, perhaps, is a reduction going the other way, thus showing that X is NP-hard (and so NP-complete). Given a graph, we adjoin to it $K_4$, the clique on 4 vertices. The new graph is a Yes instance of X iff the original graph is 3-colorable (exercise).