Haskell type classes as ontological categories

The code in Listing 1 represents my attempt to test the claim. I have simplified the classes, while retaining that ability to test the original claim, which is repeated here:
The Haskell code given so far is complete and type checked, explaining the entire refined concept hierarchies. With instantiations for types of boathouses and houseboats, values can be declared and axioms stated and evaluated to demonstrate semantic properties and differences. For example, it can be shown that a passenger on a boat in a boathouse cannot be said to be an inhabitant, while a passenger on a houseboat can.
Here is the simplified class hierarchy:

If we interpret an inhabitant as being directly in the boathouse then the claim is somewhat reasonable. This is because in Listing 1 whatsIn is not defined for type BoatHouseD, attempting to evaluate in GHCi:
whatsIn (BoatHouseDc (PeopleDc "joe"))

will cause error. In general, if a function is not defined for a data type that function will fail to type check. Note whatsIn is defined in an instance of ContainersC class for the type BoatD  and also defined in an instance of ContainersC class for the type BoatHouseD.  whatsOn  is defined for an instance of SurfacesC. These functions cannot be defined in the sub-classes  HousesC, BoatHousesC, and HouseBoatsC of ContainersC or BoatsC, BoatHousesC, and HouseBoatC of SurfacesC.
On the other hand the semantics of the Haskell code can be used to refute the claim. The test in Listing 1 shows that if someone is on a boat and that boat is in a boathouse then they are indirectly in the boathouse.
Conclusion
Based on the Haskell code in Listing 1 we can refute the claim. Reasoning about the Haskell code there is some credibility in the claim. The sub-classes seem to be redundant, because functions can only be defined in instances of the class where they were originally declared, not in any sub-class of that original class. So the functions whatsIn and whatsOn cannot be defined for the sub-classes.
Listing 1
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-#  OPTIONS_GHC  -Wno-missing-methods #-}
 -- The suffix D=data type,Dc=constructor
 -- The data types were chosen to match the type variables in the type classes
            data PeopleD = PeopleDc [Char] deriving (Show,Eq)
            data BoatD a  = BoatDc a deriving (Show,Eq)
            data HouseBoatD a  = HouseBoatDc a  deriving (Show,Eq)
            data BoatHouseD a  = BoatHouseDc a deriving (Show,Eq)

            class ContainersC a b where -- suffix C= class
             insert :: b -> a b -> a b
             remove :: b -> a b -> a b
             whatsIn :: (a b) -> [b]

            class SurfacesC a b where
             put ::  b -> a b -> a b
             takeOff :: b -> a b -> a b
             whatsOn :: (a b) -> [b]

            class PeopleC p
            class ContainersC h o => HousesC h o
            class (SurfacesC v o) => BoatsC v o
            class (HousesC h (v p), BoatsC v p) => BoatHousesC h v p
            class (BoatsC v p, HousesC v p, PeopleC p) => HouseBoatsC v p

            instance ContainersC BoatD PeopleD where
               whatsIn (BoatDc (PeopleDc x)) = [PeopleDc x]

            instance ContainersC BoatHouseD (BoatD PeopleD) where
                whatsIn (BoatHouseDc (BoatDc (PeopleDc x))) = [(BoatDc(PeopleDc x))]

            instance SurfacesC BoatD PeopleD where
               whatsOn (BoatDc (PeopleDc x)) = [PeopleDc x]

             test =  (head (whatsOn(head (whatsIn (BoatHouseDc (BoatDc (PeopleDc "joe"))))))) ==
                  (head (whatsOn(BoatDc (PeopleDc "joe"))))


It can be done in $O(L \log L)$ time, which is optimal by reduction from sorting.

Consider a Red-Black Tree $T$ (or any other self-balancing tree) where each node $v$ is augmented with $s(v)$, the number of nodes in the subtree rooted in $v$. Keeping such information updated between insertions is trivial.

In order to show that such structure supports median queries in $\log L$ time, it is sufficient to show that we can perform the following operations in $\log |T|$ time:

Given $v \in T$, determine $\#v$.
Given $n \in \mathbb{N}$, find $v \in T$ such that $\#v = n$.

To solve the first problem, initialize a variable $x := 0$ and then find $v$. Whenever in the search you are located at a node $w$, if you move right, it means that $v$ is higher than $w$ and each node in the left child of $w$. In such a case, we set $x := x + s(w.left) + 1$. When we reach $v$, we similarly set $x := x + (v.left) + 1$.

After that last update, it will hold $x = \#v$, that is true because $v$ is the minimum of the tree $T_L$ obtained starting from $T$ and cutting the left branch every time you moved to the right while searching $v$, and, conversely, the maximum of the analogous $T_R$.

The second problem can be solved by a similar idea: initialize $x:=0$ to keep track of how many elements you "discarded" by going right, and then perform a dichotomic search.


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

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

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

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


Why LL(1) grammar generate all regular languages?

The quoted answer does not claim that every right regular grammar is LL(1). That statement would not be true.
What the answer claims is that the grammars produced by the indicated algorithm are LL(1). That statement is correct.
So, no-one is saying "every right-linear grammar" satisfies condition 1 (of the LL(1) definition) (your Q1). They don't all do so.
Alos, no-one is saying that just removing left-recursion is sufficient to guarantee LL(1) (your Q2). It isn't.
Finally, no-one is saying that every RLG is LL(1) (your Q4), not even the unattributed quote which starts your question. That quote says that every regular language has at least one RLG which is LL(1). Regular languages have many RLGs, and often not all of them are LL(1). These other RLGs are not relevant to the claim that all regular languages are LL(1).
That leaves your Q3, which is really about how to demonstrate the RLG produced by the algorithm satisfies conditions 2 and 3.
It's clear why that particular RLG passes condition 1. The algorithm starts with a DFA, and the DFA has only one out-transition on each symbol, by definition. One production is generated for each out-transition, whose first symbol is the out-transition's symbol. So it's not possible for two productions starting with the same symbol to be generated for the same state (= non-terminal).
Now, under what circumstances does the algorithm produce productions which derive $\epsilon$? Answer: these productions are generated for final states. @templatetypedef wrote the quoted answer thinking about the augmented grammar/language, in which every sentence ends with an end-marker $ which does not appear elsewhere. [Note 1]
Instead of augmenting the grammar or writing the LRG as implied by the cited answer, we could invent a new state F with no out-transitions on any symbol. We then add the production $A\to F$ to every final state $A$. And we add the production $F\to\epsilon$.
Now condition 2 is met becaus the only unit productions in the grammar are $A\to F$, so no non-terminal derives $\epsilon$ in any way other than directly through $F$. And condition 3 is met rather trivially because $FOLLOW$ of every non-terminal is empty, so no terminal is in any $FOLLOW$ set.
Since conditions 1, 2 and 3 are verified, we know that the grammar produced by converting a DFA is necessarily LL(1).

Notes

This augmented language is prefix-free, since all sentences end with the endmarker. Also, as we'll see, the augmented grammar produced by the algorithm is LL(1) and therefore deterministic. A deterministic prefix-free language is LR(0), which might explain the error you refer to in your Q5. The original unaugmented grammar is not necessarily prefix-free, and therefore might not be LR(0) although it is still LL(1). This is an illustration of why augmented grammars are useful.


What is the difference between A-normalization and K-normalization in compilers?

As far as my search-foo led me; K-Normal Form is inspired by A-Normal Form, but instrumented for use in Storage Mode Analysis, which is a static program analysis used for inferring memory mangement directives for functional programs.

The term seems to originate from the following publication:
L. Birkedal, M. Tofte, and M. Vejlstrup. From region inference to von Neumann machines via region representation inference.

A copy of the publication can at the time of writing be obtained from L.Birkedal's faculty webpage under publications.


Heuristics & Constrain Satisfaction Problem Differences

CSP is a problem.

Backtracking is an algorithm that searches for a solution, basically, by trying every possibility, and backtracking as soon as it knows it is wrong. Thus it can be applied to many problems, by searching the solution space.

A heuristic algorithm is an algorithm that finds a solution using some trick to speed it up. Some heuristic algorithms might work well for particular types of problems, while remaining slow in the worst-case. Other heuristic algorithms might terminate quicker, but in the worst-case might not find a solution, or it can find an approximate solution.

From wikipedia:

  This is achieved by trading optimality, completeness, accuracy, or precision for speed.


Regular languages
Regular languages are in $\mathbf{P}$ because a deterministic finite automaton is a restricted deterministic Turing machine that runs in linear time.
Context-free languages
In fact, any context-free language is in $\mathbf{P}$: Valiant showed in the 1970s that context-free grammars in Chomsky normal form can be parsed in time $O(n^3)$ [1]. $\mathbf{P}$ strictly includes the set of context-free languages, since $\{a^nb^nc^nd^n\mid n\geq 0\}$ is not context-free but is clearly in $\mathbf{P}$.
Context-sensitive languages
Context-sensitive languages can be parsed in nondeterministic linear space [2]. We don't know the exact relationship between this class and $\mathbf{NP}$ but, since a linear space Turing machine can use exponential time, probably there are context-sensitive languages that aren't in $\mathbf{NP}$. However, showing this would be a major advance in complexity theory as it would imply that $\mathbf{NP}\neq\mathbf{PSPACE}$.
The problem of "Here's a context-sensitive grammar $G$ and a string $w$: is $w\in L(G)$" is $\mathbf{PSPACE}$-complete [2], so certainly every problem in $\mathbf{NP}$ can be reduced to the parsing problem for context-sensitive gramars. However, that's not the same thing as saying that every language in $\mathbf{NP}$ is defined by a context-sensitive grammar, since the $\mathbf{PSPACE}$-completeness result allows arbitrary polynomial-time computation in the reduction and also allows the grammar to depend on the instance. Hopefully, somebody can post a comment or answer clarifying this.
Unrestricted grammars
Unrestricted grammars define all recursively-enumerable languages. This includes all of $\mathbf{NP}$ and includes undecidable languages such as the halting problem, which definitely aren't in $\mathbf{NP}$.

References
[1] L. G. Valiant, General context-free recognition in less than cubic time, Journal of Computer and System Sciences 10(2):308–315, 1974.
[2] Context-sensitive language, Wikipedia.


How to prove a greedy algorithm that uses the longest increasing subsequence?

The most intuitive way to prove such an issue, where you're ordering elements by rank in a list, is to use an exchange argument. In short, it comes down to proving that whenever an inversion exists in the list, your algorithm inverts them so that they become ordered correctly. By proving this to be the case for every value/index pair it follows naturally that the list ends up completely ordered.

Many universities have publicly available courses on the matter. For example the TU Delft has an excellent Open CourseWare page on algorithmics that includes the subject, to be found at:

https://ocw.tudelft.nl/course-lectures/3-greedy-algorithms/


Betweenness centrality measurement ignoring inverse paths?

The algorithm that you have mentioned here is definitely correct. You can refer to the correctness proof in the paper.

This algorithm is implemented in many libraries and ready to be used including NetworkX, Boost, GraphStream, and MATLAB (3rd party I guess) and many others. Also, many other people (including myself) and companies have employed the same algorithm.

If you are getting unexpected results, please revise your implementation.


Constructing a PDA for the language $\{a^mb^n | m > n\}$

You can think about the scheme you proposed (push a symbol for every a, pop for every b) as using the stack as a counter. When you see an a, you increment the counter (push a symbol onto the stack) and when you see a b, you decrement the counter (pop from the stack). In the case where $m=n$, the stack should be empty after processing the whole string, or in other words the value of the counter should be 0. Following the same scheme, how would we know from the count that $m > n$? What would the stack have to look like in that case?


Is 'double max-$k$ vertex-cover' NP-hard?

It was easier for me to show that the $k$-clique problem is a special case of this problem.

On an input graph $G$ and an integer $k$, the this special case is defined by  $G$,$k$,$t$, with $t=\binom{k}{2}=k(k-1)/2$.
Observe that some $V'\subseteq V$ of size $k$ is a clique in $G$ if and only if the set $V'$ covers at least $\binom{k}{2}$ edges twice.

Since the NP-hard problem $k$-clique is a special case of 'double max-$k$ vertex-cover', the problem 'double max-$k$ vertex-cover' is NP-hard.


I made a program to brute force this.

This means that a very close low bound of this would be $\frac{36}{441}$, so a not that big chance.

If you wanted to avoid overlaps, I suggest you either use a different algorithm or block out all the duplicates, because the chance of this overlapping is pretty high ($8\%$).


How to explain the steps in the implementation of hashing functions like SHA1

I recommend you spend some time with some crypto textbooks, in particular the Handbook of Applied Cryptography and Antoine Joux's Algorithmic Cryptanalysis.  They explain some of the details of hash functions.  You might also try reading some of the questions on Crypto.SE; there's a lot written there.

In addition, do some self-study about unbalanced Feistel networks.  They are part of the core of SHA1.  You can find information about them on Wikipedia and in the cryptographic literature.

You might also like to read the submissions to the SHA3 competition.  Every one came with a detailed technical document that explains the design criteria and security analysis of the hash function.


I assume that by "grammar" you mean type-0 grammars. One can probably extend those to capture more languages.

Type-0 grammars are equivalent to Turing machines in expressive power. So, in order to show that a given language does not have a grammar, we can proceed as follows with suitable $L$:

  Assume there was a grammar for $L$. Then, we could semi-decide the word problem of $L$. That contradicts the known fact that $L$ is not recursively-enumerable.

Note the semi here; assuming a grammar does not give us decidability, so the halting problem is not a suitable candidate -- we need a problem/language that is not even semi-decidable/recursively enumerable. From your computability background you should know that the complement of the (special) halting language, namely

$\qquad \overline{H} = \{ \langle M \rangle \mid M \text{ loops on } \langle M \rangle \}$,

is not semi-decidable. Thus, by the reduction outlined above, there is no (Chomsky) grammar for $\overline{H}$.


Is there a running hash algorithm that can efficiently handle arbitrary updates to a file's contents?

One way to achieve it is to keep a dynamic balanced tree augmented with hashes. This will give you logarithmic slowdown for overwrites and truncation, and also will work with any hashing algorithm.

Let the file be partitioned in blocks of fixed size, $H$ be a hash-function, and $h_t$ be a value stored in a node $t$. If $t$ is a leave, then $h_t$ is a hash of the corresponding block. If $r$ is a parent of $a$ and $b$, then $h_r = H[(h_a,h_b)]$.


Algorithm to find shortest lightest path in a graph from source

The whole point about Dijkestra is that it finds the best path on it's own. You don't need BFS. In fact, Dijkestra is sort of a BFS.

Use tuples as weigths. Then your question becomes simply "find the lightest path".

How it works on your graph:

Start with a lists of undiscovered vertices and discovered ones. I labeled the unlabeled vertices E and F. I use tuples length, edgeweigth as weigth in terms of Dijkestra.

undiscovered
[B, C, D, E, F]

discovered (length, edgeweigth)
A (0, 0)

Enumerate all paths from discovered vertices to undiscovered ones along with the resulting weigth

A -(1)-> B (1, 1)
A -(1)-> C (1, 1)
A -(0)-> E (1, 0)  <

Find the best one according to your objective function. In your case: smaller length, on equal length smaller edgeweight. Add it to the discovered vertices.

Iteration 1

undiscovered
[B, C, D, F]

discovered (length, edgeweigth)
A (0, 0)
E (1, 0)

Paths
A -(1)-> B (1, 1)  <
A -(1)-> C (1, 1)

Iteration 2

undiscovered
[C, D, F]

discovered (length, edgeweigth)
A (0, 0)
B (1, 1)
E (1, 0)

Paths
A -(1)-> C (1, 1)  <
B -(10)-> D (2, 11)

Iteration 3

undiscovered
[D, F]

discovered (length, edgeweigth)
A (0, 0)
B (1, 1)
C (1, 1)
E (1, 0)

Paths
C -(1)-> D (2, 2)
C -(0)-> F (2, 1)  <
B -(10)-> D (2, 11)

Iteration 4

undiscovered
[D]

discovered (length, edgeweigth)
A (0, 0)
B (1, 1)
C (1, 1)
E (1, 0)
F (2, 1)

Paths
C -(1)-> D (2, 2)  <
B -(10)-> D (2, 11)

Iteration 5

undiscovered
[]

discovered (length, edgeweigth)
A (0, 0)
B (1, 1)
C (1, 1)
D (2, 2)
E (1, 0)
F (2, 1)

No more undiscovered vertices -> we're done.


Turning generative recursion results (leaves of a tree) into connected components (where each neighbour differs by one element)

EDIT My initial interpretation was clearly incorrect although some of the content may be useful to someone so I'll leave it at the bottom of all this.

With that, it seems like each step further into the tree will lead you to a mutually exclusive path (e.g. timetables can't have $A_1$ and $A_2$). This split is what we can call a "decision point". Assuming all your leaf-node timetables are stored in a list, you could figure out where the decision point was, and then bounce over to the corresponding node with the alternate decision.

Example: Let's say, similar to your example we have courses $A$ and $B$, with sections $A_1, A_2, A_3, B_1, B_2$. We then get a decision tree:

You can see the decision point of course $A$ is at the first level. Similarly you see the decision point of course $B$ is at the second level. The red line in there represents an example of two timetables that differ only by their grandparent, rather than just their parent. We can use some math and indexing to figure out how they're related.

As long as your course decision at each level is consistent, we can use some math and indexing to figure this out pretty easily.

Let's say you have $n$ courses: $c_1, c_2, \dots, c_n$.

Now let's define the size of a course as the number of sections = $|c_i|$.

It's pretty clear to see that, in the end, the number of leaf node timetables we'll have is $m = \prod_{i=1}^n |c_i|$. Let's assume courses are decided in increasing order (i.e. $c_1$ is decided at level 1 in the decision tree, $c_2$ is decided at level 2, etc.). If your leaf nodes are contained in a list, we can easily find related nodes based on the level of a particular course decision.

Let's say we look at leaf node timetable $j$. If we want to find all timetables that only differ at course $i$, we know they will be $\frac{m}{\prod_{k = 1}^i |c_k|}$ away.

An example might help, it's extremely clear if we're only dealing with a binary tree (each course has 2 sections). Let's say we have 3 courses: $A, B, C$. We then end up with a list of leaf nodes:

$$\left[(A_1, B_1, C_1), (A_1, B_1, C_2), (A_1, B_2, C_1), (A_1, B_2, C_2), (A_2, B_1, C_1), (A_2, B_1, C_2), (A_2, B_2, C_1), (A_2, B_2, C_2)\right]$$

We can represent these in binary:

$$\left[000, 001, 010, 011, 100, 101, 110, 111\right]$$

If we wanted to find where $111$ differs at course $B$. We find the distance between them is:

$$
\begin{align}
d & = \frac{m}{\prod_{k = 1}^i |c_k|}\\
& = \frac{8}{\prod_{k = 1}^2 |c_k|}\\
& = \frac{8}{2 \cdot 2}\\
& = 2\\
\end{align}
$$

Now deciding whether to subtract or add this distance is left up to simple edge case handling. But we see that 2 indices away from $111$ is $101$, which is the difference at course $B$ we were looking for. You should be able to take this approach to determine each differing timetable without having to compare everyone.

Misinterpretted Response Below

This algorithm seems similar to itemset lattice generation in association rule mining. Not the actual machine learning part, just the itemset generation. With this in mind, memoization in general would help downsize the repeated timetables. If you find that a child subproblem has already been solved, you can link the parent to that memoized solution, reducing the amount of links in your tree while keeping the children/parent connections consistent.

Memoization could also help with the "one section swap" connection. You already know all siblings will be "one section swap" connections. From there, it's simple to see that all leaf siblings will be connected. Using memoization these leaf-to-leaf sibling relationships will be much tighter and should basically figure themselves out.

Let's take an example with 5 sections $A, B, C, D, E$, assume a timetable is full when it gets 3 courses and just to add some variation let's say section $A$ conflicts with section $E$. If my understanding is correct your graph should look like the following, where green edges are "memoized" edges from parent to memoized child. Red crossed nodes are conflicting timetables.

Then, you may notice that we can construct a sibling graph of the leaf nodes:

Interestingly (but expected) the sibling graph connects all valid complete timetables and all connections are "one section swap" connections! So I definitely think memoization is the way to go.


What properties of a discrete function make it a theoretically useful objective function?

No, I don't think your formalization is heading in a useful direction.  It seems convoluted and focused on one particular algorithm, but there might be other optimization algorithms that you haven't considered.
I don't expect there to be a useful characterization of which objective functions can and can't be optimized effectively.  It's a notoriously hard problem.  There is work on the literature on identifying classes of problems that can provably be optimized efficiently (e.g., convex objective functions, linear programming, semidefinite programming), but the reality is that what we can prove falls short of what empirically often seems to be feasible in practice.
For instance, what you're looking for is at least as hard as the P vs NP problem, since every NP problem can be expressed as an optimization problem; and I don't expect there to be a simple characterization of which NP problems are NP-complete.


Same notation/terminology for union of sets and concatenation (Kleene star)?

Wikipedia is using $\cup$ in its usual meaning, set union. When Wikipedia defines
$$
V^* = \bigcup_{n \geq 0} V^n = V^0 \cup V^1  \cup V^2 \cup \cdots,
$$
it literally means that $V^*$ is the union of the sets $V^0,V^1,V^2,\ldots$

The concatenation happens in the definition of $V^n$, which can be defined as follows: $V^0 = \{\epsilon\}$, and $V^{n+1} = \{ xy : x \in V^n, y \in V \}$. In words, $V^n$ is the concatenation of $n$ words from $V$.


Is there an example of how SOS can be used to show infeasibility of a set of multivariable equations?

The theorem you are referring to is known as the Positivstellensatz, but you are citing it incorrectly; given only polynomial equations, the relevant theorem would be the Nullstellensatz. See also lecture notes of Laurent and blog posts of Amir Ali Ahmadi.

Regarding pseudodistributions, Barak defines them as linear operators for low-degree monomials which satisfy the crucial property $E[P^2] \geq 0$ for low-degree $P$. These are all the properties you need when looking at low-degree moments.


If $L_1,\,L_1L_2$ are regular languages with $L_1\neq \emptyset,\,\lambda\notin L_1,\,\lambda\notin L_2,$ is $L_2$ regular?

How about this? $L_1=\{a^n\mid n>0\}$, $L_2 = \{a^{m^2}\mid m>0\}$. Certainly $L_1$ and $L_1L_2$ are regular, but $L_2$ certainly isn't.


Probabilistic analysis of finding 2nd largest value in vector

Let's assume for simplicity that $v$ is a random permutation of the numbers $1,\ldots,n$. In step $i$, largest is assigned to if $v_i$ is the maximal element among $v_1,\ldots,v_i$ (a "record"), and second_largest is assigned to if $v_i$ is the second maximal element among $v_1,\ldots,v_i$. The probability of each of these events is $1/i$ (the second, assuming that $i \geq 2$), since $v_1,\ldots,v_i$ is a random permutation of $\{1,\ldots,i\}$.

Linearity of expectation shows that the expected number of times that largest is assigned to is
$$
\sum_{i=1}^n \frac{1}{i} = H_n = \log n + \gamma + O\left(\frac{1}{n}\right).
$$
Similarly, the expected number of times that second_largest is assigned to is
$$
\sum_{i=2}^n \frac{1}{i} = H_n - 1 = \log n + \gamma - 1 + O\left(\frac{1}{n}\right).
$$
In both formulas, $H_n$ is the $n$th harmonic number, $\log$ is the natural logarithm, and $\gamma$ is Euler's constant.


How to solve $T(n)=n+T(n/2)+T(n/4)+\cdots+T(n/2^k)$?

Suppose that the base case ensures that $T(n) \geq 0$. Clearly $T(n) \geq n$. On the other hand, guessing that $T(n) \leq Cn$, an inductive proof would work as long as
$$
n + C(n/2 + n/4 + \cdots + n/2^k) \leq Cn.
$$
Now the left-hand side is at most $n(1 + C(1-1/2^k))$, so we would need $C$ to satisfy
$$
1 + (1-1/2^k)C \leq C.
$$
In other words, $1 \leq C/2^k$, and so we can choose $C \geq 2^k$. Concluding, we have shown that $T(n) = \Theta(n)$. While this is true for every finite $k$, the hidden constant depends on $k$ and on the initial conditions.

The case in which $k$ is unbounded – let's say goes all the way to $\lfloor \log_2 n \rfloor$ – is more interesting. In this case we guess a solution of the form $T(n) \approx nf(n)$. The function $f(n)$ has to satisfy the recurrence
$$
f(n) = 1 + \frac{f(n/2)}{2} + \frac{f(n/4)}{4} + \cdots.
$$
A reasonable guess is $f(n) = \log_b n$, under which the right-hand side reads
$$
1 + \frac{\log_b n - \log_b 2}{2} + \frac{\log_b n - 2\log_b 2}{4} + \cdots = \log_b n - \kappa + o(1),
$$
where the constant $\kappa$ equals
$$
\kappa = 1 - \sum_{m \geq 1} \frac{m}{2^m} \log_b 2 = 1 - 2\log_b 2.
$$
Choosing $b=4$, we see that $T(n) \approx n \log_4 n$, and certainly $T(n) = \Theta(n\log n)$.


True Postcondition, with true Precondition

A true postcondition means there is no restriction on outputs.

Think about it. The condition x > 5 means: it's true (anything goes), as long as x is greater than 5. The only way for that condition to be invalidated is when x isn't greater than 5. The condition true means: x doesn't even need to be greater than 5. There is no way to invalidate that condition at all. Anything goes.

(If you don't mind, I'll leave the rest to you.)


Finding topologically sorted connected components in directed acyclic graph

Standard algorithms for computing strongly connected components label each vertex with a number indicating which component it is part of.  Then, you can use that to construct the "metagraph" of components (where each component of the graph is a vertex of the metagraph, and there is an edge $i \to j$ in the metagraph iff there is an edge $v \to w$ in the original graph where $v$ is in component $i$ and $w$ is in component $j$) in linear time.  Finally, you can apply a topological sorting algorithm on the metagraph.

Some algorithms for computing strongly connected components (such as Tarjan's algorithm) already do that for you for free.  Or, you can do it yourself as a postprocessing phase; since it takes only linear time, it won't increase the asymptotic running time of the algorithm.

See, e.g., https://en.wikipedia.org/wiki/Strongly_connected_component, https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm, and https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm.


Prove that my NP-complete problem is strong

You've asked two questions.  To answer the first question:

Not quite right.  It depends on the running time of your dynamic programming algorithm.  To show that the problem is weakly NP-complete, you should show that there is an algorithm whose running time is polynomial if the input is represented in unary.  So, you'll first need to prove that your dynamic programming algorithm has that property.

To answer the second question:

If in doubt, go back to the definition.  Wikipedia has a page with a definition of strongly NP-complete; it says

  A problem is said to be strongly NP-complete (NP-complete in the strong sense), if it remains so even when all of its numerical parameters are bounded by a polynomial in the length of the input.

So, that's what you need to prove.  It's hard to say much more without knowing what the specific problem is.


NP complete language having no Polytime decidable superset

A slightly simpler proof is to note that $\Sigma^* \setminus \{w\}$ is polynomial-time decidable and a superset of any language $L$ where $w\notin L$. Formally:

Suppose $P\not = NP$ and let $L$ be some $NP$-complete language. Then there exist at least $2$ strings $v\not = w$ so that $v\not \in L, w\not \in L$ or $L$ would not be $NP$-complete (since $L$ would either be $\Sigma^*$ or $\Sigma^*\setminus L$ would be a singleton). Then $\Sigma^{*}\setminus \{w\}$ is polynomially decidable and a superset of $L$ (since $v\in \Sigma^{*}\setminus \{w\}$).

If $P=NP$ then every language that is not $\emptyset$ or $\Sigma^*$ is $NP$-hard, so in particular $\Sigma^* \setminus \{x\}$ is $NP$-complete (where $x$ is any string in $\Sigma^*$). However, $\Sigma^* \setminus \{x\}$ has no (proper) superset that is not $\Sigma^*$. So if $P=NP$, there is a a language having no superset $\in P$ that is not $\Sigma^*$.


Calculating Tag Bits in a Direct-Mapped Cache

Since Hennessy & Patterson uses MIPS architecture as the basis for all its examples, we can assume that this example is no exception. MIPS is byte addressable. Hence a byte offset of 2 bits (to address the four bytes in the 32-bit word size) need to be included in the 32 bit address.

These 2 bits occupy the least significant two bits of the 32 bit address's binary representation. Hope that helps!


Complexity of Context Sensitive Languages

When the book says

  Following the analysis leading to Equation (5.2),

it implies that if you apply the same kind of reasoning that resulted in Equation (5.2) to context-sensitive languages, then you will get the similar equation

  $$ N = |P| + |P|^2 + \ldots |P|^{cn} = O(|P|^{cn+1}). $$

This equation is the analog of Equation (5.2) for context-sensitive languages. To prove this equation, you use reasoning similar to that used to prove Equation (5.2).


Getting sum of all numbers contained in substrings of S on a segment

$O(N \log K)$ running time looks achievable.

Hints:

Suppose you know the answer to the query $l,m$ and the query $m+1,r$.  Can you work out the answer to the query $l,r$ efficiently?  Would precomputation help?  What information do you need to know?
Use a balanced binary tree, where each digit is at a leaf.  At each internal node $\eta$, you will store the answer to the query $l_\eta,r_\eta$, where $l_\eta$ is the leftmost leaf under $\eta$ and $r_\eta$ is the rightmost leaf under $\eta$.  Also, story the sum of all numbers that can be made by starting at index $i$ (for $l_\eta \le i \le r_\eta$) and ending at index $r_\eta$, as well as the sum of all numbers that can be made by starting at $l_\eta$ and ending at some index $j$ (where $l_\eta \le j \le r_\eta$).

Now for any particular query $l,r$, the answer can be obtained efficiently given only $O(\lg K)$ numbers in the tree.

I'll let you have the joy of working out the rest, since this sounds like a programming contest problem and you should probably make some effort on your own.


The fact that $f$ is non-decreasing makes the problem much easier, solvable in polynomial time.

You have to find a way to split the weights so that weights $1,\ldots,x$ go to bucket $1$, weights $x+1,\ldots,y$ go to bucket $2$, weights $y+1\ldots,z$ go to bucket $3$, and so on.

If you define $D(i,j)$ to be the best way to assign weights $j,\ldots,m$ to buckets $i,\ldots,n$ you can apply dynamic programming.


First of all your question is quite confusing:

There is at least one edge $w \in V$

Is it an edge or a vertex?
Maybe it would be easier for you to look at some edge $(u,v) \in E$ and think about the moment in time $\tau$, when the BFS algorithm reached either $u$ or $v$ for the first time (it could reach them both at the same time).


Points at distance $k$ or less in 2D grid

Read your question more carefully. The formula you give is for

  the total number of mesh points $k$ or fewer jumps away

(my emphasis).  And there are indeed five points one jump or fewer away from $e$: $b$, $d$, $f$, $h$ and $e$ itself.


How does one change the probability bounds in probabilistic complexity classes without changing the class?

Suppose that $\Pr[M(x) = L(x)] \geq 1/2 + \epsilon$. Run $M$ repeatedly $m$ times (for $m$ odd), and take the majority vote. Let $x_i$ be the indicator for the event that the $i$th run of $M$ gives the correct solution. The success probability of the majority vote algorithm is
$$
\Pr[x_1+\cdots+x_m > m/2] \geq \Pr[\operatorname{Bin}(m,1/2+\epsilon)>m/2].
$$
At this point you apply the Chernoff–Hoeffding bound. You take it from here.


Conditional Shortest Path Through Weighted Cyclic Directed Graph

The problem is NP-hard, even when you ignore the constraints about categories.  See https://cstheory.stackexchange.com/q/17462/5038 for a simple proof based on a reduction from the longest path problem (or from the Hamiltonian path problem).  Therefore, you should not expect any efficient algorithm.

There are algorithms whose running time is polynomial in the size of the graph but exponential in $m$ (the length of the path). See https://en.wikipedia.org/wiki/Longest_path_problem#Parameterized_complexity.

The categories don't increase the complexity of the problem by more than a constant factor, since there are only 4 categories.  For instance, if the path is required to use at most 3 different categories, you can enumerate all ${4 \choose 3}$ subsets of 3 categories, and for each, construct a smaller graph that contains only the vertices in that subset and then solve the problem on that graph without the restriction on the number of categories.  So for an algorithm design perspective, I suggest you first solve the problem while ignoring the categories.  It will then be straightforward to extend your solution to deal with the categories.


You can do it in $O(N \log N)$ time and $O(N)$ space.

Instead of finding the billboards that you want to keep, find the billboards that you want to get rid of.  You need to find the minimum cost set of billboards such that there is no gap of more than $K$ between two billboards. Do this by constructing a table where the $i$th entry is the minimum cost to remove the $i$th billboard and enough previous billboards to make this legal. Now, to add an entry to the table, you need to find the minimum of the previous $K$ entries to the table. You can do this in $O(\log N)$ time using a priority queue.

If $K \ll N$, you might want to use a fancier priority queue that takes $O(\log K)$ time instead; but I'd guess that for large $K$, the simpler priority queues such as heaps that don't admit deletion of a non-MIN item are quicker for this problem. I don't know how tight time limits Interview Street has set for this problem.


Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$

Yes, here the idea of one with three states. I don't know stuff formally enough to write tuples.

Keep track of the parity of 'a's you read in two states.
If you read 'aa', push A on the stack
When you hit b, you better be on odd parity
Pop 'A' for every 'b' you read
At the end of the input, succeed if the stack is exactly empty.

This accepts only when i == 2j+1. Then, invert the last step, while keeping the requirement to keep it in the format $\{a^ib^j\}$ to get the version below. This requires adding one more state.
This might be a valid formal version, or it might not:
state,      input (z=end-of-string),
               top of stack (E=empty, *=anything),
                  action
q_a_even,   a, *, do nothing and transition to q_a_odd
q_a_even,   b, *, transition to q_b_ok
q_a_even,   z, *, succeed
q_a_odd,    a, *, push 'A' and transition to q_a_even
q_a_odd,    b, E, transition to q_b_ok
q_a_odd,    b, A, pop and transition to q_b_danger
q_a_odd,    z, *, succeed
q_b_danger, a, *, fail
q_b_danger, b, E, succeed
q_b_danger, b, A, pop and transition to q_b_danger
q_b_danger, z, A, succeed
q_b_danger, z, E, fail
q_b_ok,     a, *, fail
q_b_ok,     b, *, transition to q_b_ok
q_b_ok,     z, *, succeed


It's a term coming from abstract algebra. When you quotient a set $S$ with respect to some equivalence relation $\sim$, you are replacing the set $S$ with its equivalence classes under $\sim$. Often the set $S$ has operations defined on it, and in that case we want these operations to be well defined for the quotient $S/\sim$, in the sense that if $x_i \sim y_i$ then $x_1 \circ x_2 \sim y_1 \circ y_2$. This allows us to define $\circ$ on the quotient.

An example in real analysis is $L^p$ spaces, in which functions are defined "up to measure zero".


Show there exists a turing machine with the following properties

Look again at your definitions. $\psi$ is a formula of $n$ variables, eg.
$\psi_1 = x_1 \vee x_2$ or $\psi_2=x_1 \wedge x_2$, on 2 variables.

Now the question asks whether or not there are more than $2^{n-1}$ assignments to $x_1, x_2, ...$ that satisfy the formula. In other words, assignments that make $\psi$ evaluate to true.
For the above example, $\psi_1$ has 3 satisfying assignments (out of the $2^2=4$ possible assignments), while $\psi_2$ is satisfied only by a single assignment (namely, $x_1=x_2=\text{true}$). So $\psi_1 \in L$ and $\psi_2 \notin L$.

If you understand so far, then finding a probabilistic TM that accepts any formula with the above conditions with probability at least $1/2$ is trivial. I'll let you think about it some more.


prove no DPDA accepts language of even-lengthed palindromes

As Luke notes, there is a Pumping Lemma for deterministic CFL. If there are two strings  $zz_1$ and $zz_2$ in the language with common prefix $z$, then for deterministic devices the computation in both substrings $z$ must be the same. The idea behind that Lemma is that now also the pumping must be the same for both strings. In context-free languages pumping is of the form $uvwxy$. The Lemma states that either $vx$ are inside $z$ for both $zz_1$ and $zz_2$  or $v$ is inside $z$ and there are $x_1$ and $x_2$ inside $z_1$ and $z_2$  so we can pump both words that way.

For full details check the Lemma.

Now consider $K = L \cap ( a^*bba^* \cup a^*bba^*bba^* ) = \{ a^nbba^n \mid n\ge 0 \} \cup \{ a^nbba^{2m}bba^n \mid m,n\ge 0 \} $. If $L$ is DCFL then so is $K$. Can we pump $z_1 = a^{2n}bba^{2n}$ and $z_2 = a^{2n}bba^{2n}bba^{2n}$ in the same way? No. The $v,x$ parts are situated differently when we pump for $z_1,z_2$ which contradicts the DCFL Pumping.

Again, one has to be slightly more precise, and quote the proper parts of the Lemma.


Can we find a Turing machine such that there is no Turing machine to decide whether it halts on $\epsilon$?

Suppose you had such a TM, namely a machine $M$ for which the problem was "Does $M$ halt on empty input?" Certainly that problem would be decidable: one of two algorithms must be correct, (1) Answer "yes" or (2) Answer "no". The fact that we might not know which one is the correct algorithm is immaterial here; the only thing that matters is that we're sure one of the algorithms is the right one, so we know the problem is decidable. In more general terms, any decision problem with a finite number of instances is decidable.


How to compare computational complexity of algorithms

Since you have three different variable it is not easy to compare their running times. For example if $d = 1/n$ then $nd = 1$. But if $d = n$ then $nd$ is $n^2$. If $d$ and $n$ are unrelated to each other asymptotically or functionally I think you may not compare them. Analogously for $p$.

Update:
If $M,p,k$ and $d$ are constant then we have Alg1 is $O(n)$, Alg2 is $O(min(p^3, n^3)) = O(p^3) = O(1)$, and Alg3 is $O(n)$.


How to represent the interests of a Facebook user

The interests are categorical data and may be modeled as binary variables (a user either likes them or he does not). You can subsume little-used categories under broader categories. For example, a user who likes a little-known horror movie can simply be marked as liking horror movies. You can even subsume such items under multiple categories if it belongs to several.

For what you can do with the data see A Review on Data Clustering Algorithms for Mixed Data


Determine if a line going through n rectangles exists

There is a line through the four rectangles if and only if you can pick one edge from each rectangle such that the line intersects each of those four edges -- or equivalently, if there is a point on each of those edges such that the resulting four points are colinear.  So a plausible algorithm is to enumerate all $4^4$ ways to choose one edge from each rectangle; then check whether there exists a line that goes through those four edges.

How do we do the latter test?  Let's suppose the endpoints of the first edge are the two points $P',P''$ (i.e., these are two adjacent corners of the first rectangle).  Then any point $P$ on that edge can be expressed as $P = (1-\alpha) P' + \alpha P''$ for some $0 \le \alpha \le 1$.  Similarly, we can express any point $Q$ on the second edge as $Q = (1-\beta) Q' + \beta Q''$ where $Q',Q''$ are the endpoints of the second edge, and similarly for the two remaining points $R,S$ on the two remaining edges.

We can express algebraically the condition that $P,Q,R$ are colinear (on the same line).  Let $P_x$ be the x-coordinate of the point $P$, and $P_y$ be its y-coordinate.  Then $P,Q,R$ are colinear iff

$$(Q_x-P_x)(R_y-P_y) = (Q_y-P_y)(R_x-P_x).$$

We can plug in $Q_x = (1-\beta)Q'_x + \beta Q''_x$, and so on, to get an equation in terms of the three $\alpha,\beta,\gamma$ unknowns.  Similarly, the condition that $P,Q,S$ are colinear can be expressed as an equation in terms of $\alpha,\beta,\delta$.  Now there exists a linear through these four edges iff there exists a common solution to these two equations such that $0 \le \alpha,\beta,\gamma,\delta \le 1$.  This reduces the problem to solving two quadratic equations over four real unknowns.  Now you can apply standard methods for solving such equations to determine whether a simultaneous solution exists.


The problem is in P.
You can solve the decision problem in $O(n^2)$ time, where $n$ is the number of vertices (i.e., linear time in the size of the input).  Delete all edge whose weight is above the bottleneck threshold.  Form the strongly connected components of the resulting graph, and examine its metagraph.  The original decision problem has a bottleneck TSP iff the metagraph is a simple path, i.e., it has the form $w_1 \to w_2 \to \dots \to w_k$ where $w_1,\dots,w_k$ are the components and the only edges are $w_i \to w_{i+1}$.
You can solve the optimization problem in $O(n^2 \log n)$ time.  Sort the set of edge weights, and remove duplicates.  Then, use binary search on this set of weights to find the smallest bottleneck threshold such that the decision problem has a solution.  You will do $O(\lg n)$ iterations, and each iteration runs the decision problem above, so the total running time is $O(n^2 \lg n)$.


Yes, I suppose you could, though it might be viewed as a somewhat informal usage of the term "topology".  "Shape" would probably be a better word, as @Raphael suggests.

A more precise way would be to say that these two trees are not isomorphic.

Background: Two graphs $G,G'$ are considered isomorphic if there exists a map $f:V \to V'$ that is a graph isomorphism.  Since any tree can be viewed as a graph, you can consider two trees to be isomorphic if they are isomorphic as graphs.  One can also define a natural notion of a tree isomorphism directly; this happens to be equivalent to the notion of a graph isomorphism for unrooted trees, but is slightly different (and more appropriate to use) for rooted trees.  You can read more about isomorphisms in standard sources.


Proving that the language of satifiable CNF formulae with primes is NP-complete

For 1): You have to prove that the language is solvable by a nondeterministic TM in polynomial time. The easiest way is indeed to use previously defined TMs, e.g. the TM to solve SAT. So your approach is correct.

For 2): You don't have to prove it for every $L'$ $\in$ $NP$ explicitly, it suffices to give a reduction from a language that is NP-complete. The idea is that you reduce every word $w' \in L'$ to a word $w \in L$, so if you find an efficient way to solve $L$, you also have an efficient way to solve $L'$. So you can choose any NP-complete language that should provide a simple reduction to $L$.

The next step therefore would be to choose such NP-complete language $L'$.

Next you have to find a reduction $f$ to reduce your previously chosen language $L'$ to your language $L$. Depending on your choice of $L'$, this can be a very simple process in your case. Note that $\{$ $f(w') \mid w' \in L \} \subseteq L$, not $\{$ $f(w') \mid w' \in L \} = L$


Sorted array with odd indexed elements swapped randomly

Hint:

Use binary search to find the possible locations of $x$ in the original array.
If you find two even elements $y,z$ with $y<x<z$ and the element between them $w$ is does not belong there, then $w$ might have been switched with $x$. Find the proper position of $w$ using binary search and look if $x$ is there.


How do cycles of non-consuming transitions in NFAs influence their halting properties?

No, the $\lambda$-loops you talk about are not forbidden.  But they do mean one has to be careful.

The actual way to determine if an NFA accepts its input is as follows.  Note that this takes linear time in the length of the input, not constant time as you say in the question.  First, for each state $q$ of the automaton, use a graph reachability algorithm to compute the set of states $\Lambda(q)$ that can be reached from $q$ using only $\lambda$-transitions. For a fixed automaton, with a fixed number of states and fixed transition function, this can be done in constant time. Note that $q\in\Lambda(q)$ for every $q$, since you can reach $q$ from itself by doing some number of $\lambda$-transitions: specifically, that number is zero.  This means that $\lambda$-transitions from a state to itself are completely harmless.

To determine whether the automaton accepts its input, we just keep track of the set of states that the automaton "might" be in after reading each successive character of the input.  Initially, it could be in any state in $\Lambda(q_0)$.  If, after reading some characters, it could be in any state in $S\subseteq Q$ then, when it reads character $a$, it could be in any state in $\Lambda\Big(\bigcup_{s\in Q}\delta(s,a)\Big)$. It accepts if, at the end of the computation, the set of states it might be in includes at least one accepting state.  Note that, at any time, the set of states the automaton could be in is bounded by the fixed constant $|Q|$ so all the manipulations needed on the set of possible states can be done in constant time per character the machine reads, independent of the length of the input.


How to prove that a language is not context-free using pumping lemma

Here is the simplest way. Suppose that your language were context-free, and consider its intersection with $0^*(10)^*110^*(10)^*$. Applying further simple manipulations, you reach the language $\{a^nb^mc^nb^m : n,m \geq 0\}$, which is known not to be context-free.

If you insist on using the pumping lemma, perhaps you can get inspiration from this argument.


What does `Dv` mean in $F\star$ language?

In the theory of computation "diverge" means "does not terminate" or "runs forever". This is a computational effect (of a peculiar kind).


Finding a segment which has equal number of segments before and after it

Here is an algorithm that achieves $O(n\log n)$ complexity without any elaborate data structures. Just a simple sort and a couple of loops.

Sort all the $\{a_i,b_i\}$ together. Call the resulting sequence $(x_1,\ldots,x_{2n})$.
Set $n_a\gets0$, $n_b\gets0$.
Loop for $n_b$: For $t$ going from $1$ to $2n$ do:

If $x_t=b_i$ for some $i$, increment $n_b$
Else if $x_t=a_j$ for some $j$, set $L_j\gets n_b$

Loop for $n_a$: For $t$ going from $2n$ down to $1$ do:

If $x_t=a_i$ for some $i$, increment $n_a$
Else if $x_t=b_j$ for some $j$, set $R_j\gets n_a$

Now for each interval $[a_i,b_i]$, $L_i$ and $R_i$ contain the number of intervals to its left and to its right, respectively
Final loop: For $i$ going from $1$ to $n$

If $L_i=R_i$, return $i$

Found nothing: Return null.

You might need to make some additional checks to take care of cases where $a_i=b_j$ for $i\not=j$.

Note that equality checks of the form $x_t=b_i$ can be done by saving the sorting indices. In other words, if you sort an array $u$ into another array $v$, you can save indices $\pi_t$ such that $u_t=v_{\pi_t}$.


You can't.  If the function $V$  (for computing the $v_i$'s) is arbitrary, in the worst case you will need to try all possible combinations of quality levels -- there is no algorithm faster in the worst case.  That takes exponential time.

To do better, we need to know something about the function $V$: e.g., about its structure or proeprties.


Is this grammar right associative (why?)

$\left<expr\right> \to \left<term\right>×\left<expr\right> | \left<term\right>$

could certainly expand $\left<term\right>$. But the operator in that expansion (if there is one) is certainly not $×$; it would have to be $+$. So associativity doesn't apply, since associativity is only about expressions involving two of the same operator.

So yes, in both operator productions in that grammar, the operator is right-associative.


Connection between KMP prefix function and string matching automaton

First of all, note that by definition

$\delta(q,a) = \sigma_P(P_{0,q}\cdot a) =: s_1$ and
$\delta(\pi_P(q),a) = \sigma_P(P_{0,\pi_P(q)}\cdot a) =: s_2$.

Let us investigate $s_1$ and $s_2$ in a sketch:

[source]

Now assume $s_2 > s_1$; this contradicts the maximal choice of $s_1$ directly. If we assume $s_1 > s_2$ we contradict the fact that both $s_2$ and $\pi_P(q)$ are chosen maximally, in particular because $\pi_P(q) \geq s_1 - 1$. As both cases cases lead to contradictions $s_1=s_2$ holds, q.e.d.

As requested, a more elaborate version of the proof:

Now we have to show $s_1=s_2$; we do this by showing that the opposite leads to contradictions.

Assume $s_2 > s_1$. Note that $P_{0,s_2} \sqsupset P_{0,q}\cdot a$ because $P_{0,s_2} \sqsupset P_{0,\pi_P(q)}\cdot a$ and $P_{0,\pi_P(q)} \sqsupset P_{0,q}$ by definition of $s_2$. Therefore, $P_{0,s_2}$ -- a prefix of $P$ and a suffix of $P_{0,q}\cdot a$ -- is longer than $P_{0,s_1}$, which is by definition of $s_1$ the longest prefix of $P$ that is a suffix of $P_{0,q}\cdot a$. This is a contradiction.

Before we continue with the other case, let us see that $\pi_P(q) \geq s_1 - 1$. Observe that because $P_{0,s_1} \sqsupset P_{0,q}\cdot a$, we have $P_{0,s-1} \sqsupset P_{0,q}$. Assuming that $\pi_P(q) < s_1 - 1$ immediately contradicts the maximal choice of $\pi_P(q)$ ($s_1 - 1$ is in the set $\pi_P(q)$ is chosen from).

Assume $s_1 > s_2$. We have just shown $|P_{0,\pi_P(q)}\cdot a| \geq s_1$, and remember that $P_{0,\pi_P(q)}\cdot a \sqsupset P_{0,q} \cdot a$. Therefore, $s_1 > s_2$ contradicts the maximal choice of $s_2$ ($s_1$ is in the set $s_2$ is chosen from).

As neither $s_1 > s_2$ nor $s_2 > s_1$ can hold, we have proven that $s_1 = s_2$, q.e.d.


On the analysis of Christofides's algorithm

Since $P$ is a minimum weight perfect matching, by definition
$$ \operatorname{cost}(P) = \min_N \operatorname{cost}(N), $$
where $N$ goes overl all perfect matchings. In particular, $\operatorname{cost}(P) \leq \operatorname{cost}(N)$ for any particular perfect matching $N$.


Is #P closed under exponentiation? modulo?

No.  Take $f(n)=g(n)=2^n$ for a counterexample.


Does Peterson's 2-process mutual exclusion algorithm account for dying processes?

This depends on how locks are implemented. If you do it as in the Wikipedia article, i.e. guarding the critical section with one boolean per process¹, you are certainly in trouble. If one process dies, it never resets its flag so the other process loops forever.

In practice, you can safeguard your code against many ways of dying. For example, take this Java-style implementation:

flag[1] = true;
turn = 1;
while ( flag[0] == true && turn == 1 ) { Thread.yield(); }
try {
  // critical section
}
finally {
  flag[1] = false;
}

This will make sure the flag is reset whatever happens in the critical section, as long as the system is handling the error. In Java, that is true even for stack and heap overflows. So unless the process literally vanishes (kill², processor failure, network disconnect, ...) you are safe. Note that most non-critical software fails in these cases -- how can it handle an error it it's not running? -- so that has to be accepted in many cases. You can handle inconsistencies upon restart if necessary.

If you use proper, language-level locks, the runtime system may handle vanishing lock owners, i.e. release locks with dead owners. You can simulate this yourself by giving each process a dead man's switch the others can read, or check directly whether the lock owning process is still alive (if the system supports it).

That does not scale well, anyway.
In Java, I think finalize should execute even on kill, but this is not guarenteed by the spec. kill -9 is probably a death sentence for any solution that requires the dying process to do something.


Valid actions of Reductions to NP-Completeness

Your understanding is correct.

The only restriction is the one you mention: the reduction must work in polynomial time. That is, there must be some algorithm and some polynomial function $t(n)$ (e.g. $t(n)=n^5+n^3+42$) such that, on all inputs $x$ of length $n$, the algorithm outputs $f(x)$ and the time it takes the algorithm to do that is less than or equal to $t(n)$.

To answer concretely what "things" you may do, I can't! Anything you can think of that takes polynomial time: perfect matching, integer multiplication, some variants of linear programming... graph isomorphism? Counting the number of solutions to the traveling salesman problem? If you can do it in polynomial time, then yes!

To read some posts on this site about NP Completeness, click here to search for posts about that topic.


How is $\text{PCP}[O(\log n),O(1)]$ NOT P?

A language $L$ is in $\mathsf{PCP}(r(n),q(n))$ if there is a randomized polytime algorithm $V(x,y)$ which acts as follows:

The algorithm is given $r(n)$ random bits.
Given these random bits, it chooses (deterministically) $q(n)$ locations in $y$.
It reads $y$ at these locations, and based on that, decides whether to accept or reject.

Furthermore, $V$ satisfies the following two conditions:

If $x \in L$ then there exists $y$ such that $\Pr[V(x,y) \text{ accepts}] = 1$.
If $x \notin L$ then for any $y$, $\Pr[V(x,y) \text{ accepts}] \leq 1/2$.

Let $n = |x|$. Since $V$ uses only $r(n)$ random bits and reads at most $q(n)$ bits of $y$, at most $2^{r(n)} q(n)$ bits of $y$ can potentially be read. when $r(n) = O(\log n)$ and $q(n) = O(1)$, this means that at most polynomially many bits are read from $y$, and so we can assume that $y$ has polynomial length.

Every language in $\mathsf{PCP}(O(\log n), O(1))$ is in $\mathsf{NP}$. Indeed, given $y$, we can compute $\Pr[V(x,y)\text{ accepts}]$ in polynomial time (since there are only polynomially many choices for the random bits). However, the language is not obviously in $\mathsf{P}$, since there are exponentially many choices for $y$.


Minimum amount of time for two enemies to reach their destinations?

Generate the graph $G'$ of all legal configurations. A legal configuration is an ordered pair of vertices $\langle u, v \rangle$ in $V^2$ such that $d_G(u,v) \ge k$, where $d_G(u,v)$ denotes the distance between $u$ and $v$ in $G$.

There is an edge from $\langle u_1, v_1 \rangle$  to $\langle u_2, v_2 \rangle$ in $G'$ if and only if $d_G(u_1, u_2) \le 1$ and $d_G(v_1, v_2) \le 1$.

The amount of time you are looking for is now equal to $d_{G'}(\langle s_x, s_y \rangle, \langle t_x, t_y \rangle)$.


Doubt with the halting problem undecidable proof

The main problem with your analogy is the construction of Diag. The usual proof goes as follow:

Assume Ends exists.
Then we can construct Diag with a Turing machine calling Ends. As follows:

Diag(P) = If Ends(P,P) then Loop indefinitely Else Terminates.

This leads to a contradiction thus Ends does not exist.

What you are doing is the following:

1'. Construct Ends(P,I,S).

2'. Construct Diag(P,S).

3'. This leads to a contradiction.

The main problem is that you do not provide the actual construction of Diag in step 2' as we did it in step 2. How can you implement Diag with a TM machine calling Ends? I do not think so as you need more than S steps to run the program Ends.


I have not (nearly) read enough books to name $5000 worth of them. Therefore, I will suggest some groups of literature you should cover as well as point you towards selected representatives. I can not claim to have read most of the books in full myself, so I have to rely mostly on descriptions, cursory impression and reputation. I have looked into or worked with most of them to some extent, or had them recommended by experts.

I assume that you want your people to learn what can be done, and how to do it, as opposed to learning what they can't do. In particular, I will leave out books about computability and complexity theory as such; I expect your people to have taken away the relevant messages from their undergraduate education.

The Basics
Even though your people have learned them at some point, expect them to look
up the basics. Since sources like Wikipedia are frequently substandard
or outright wrong, you want to get them proper reference texts.

Popular choices include

Introduction to Algorithms by Cormen, Leiserson et al.
Very broad introduction that covers many elementary algorithms and data structures as well as basic analysis techniques. A standard text used frequently for teaching purposes and available in its 3rd edition (so most mistakes should have been purged by now). Lots of exercises.
Algorithms by Sedgewick and Wayne
Another standard text in its fourth edition. Less broad than Cormen, but with more attention to implementation details. Lots of material online, including a free course on Coursera. Lots of exercises.
Introduction to Algorithms -- A Creative Approach by Udi Manber
Also rather slim a selection of topics, but presented with attention to didactics. The focus is on inductive strategies. Contains lots of exercises and solutions (or at least hints) for some. A good secondary reference if you don't like the recommended textbook because of its unusual style.
Concrete Mathematics by Graham, Knuth and Patashnik
Covers discrete mathematics as relevant to algorithm analysis. Rare in its focus on computer science needs and rigor. Very high quality. Lots of exercises with solutions.

Analysis of Algorithms
In most standard text books, analysis of algorithm usually stops at the level
of $O$-asymptotics and RAM model. In order to estimate real-world efficiency
more reliably, it can be necessary to investigate runtime more precisely and
consider effects like memory hierarchy and communication.

An Introduction to the Analysis of Algorithms by Sedgewick and Flajolet
Basic techniques for precise analysis of algorithms. Written by the
pioneers of the field. Also has a free online course.
The Art of Computer Programming by Knuth
The reference for high-quality, low-level, precisely analysed
algorithms for a whole range of problems. Also serves as reference.

Advanced Surveys

Purely functional data structures by Okasaki
Classic and basic literature often focuses on the procedural paradigm. If
you want to work in the functional paradigm, new techniques for efficient
data structures are needed. This book is a detailed overview over the area.
Advanced Data Structures by Brass
Sometimes, the basic techniques are not enough. This is an overview over
advanced data structures, with code and many references.
Algorithmics for Hard Problems by Hromkovič
Complexity theory tells us (as practitioners) not to bother looking for
exact yet efficient algorithms for many natural problems. There are plenty
of techniques for practically solving these problems; this text shows
you how.

Specialised Literature

Compilers: Principles, Techniques, and Tools aka The Dragon Book by Aho et al
Should you ever need to build or tinker with a compiler, this is the
standard text on the area.
Network Flows: Theory, Algorithms, and Applications by Ahuja
Many problems can be modeled as network  flow problems; this book gives you
a full coverage of the field.
Probabilistic Graphical Models by Koller and Friedman
Graphical models are a major tool in modeling scenarios for machine
learning (among others) probabilistically. This is a comprehensive overview
about the complex. There is a related free online course.
Handbook of Exact String Matching Algorithms by Charras and Lecrog
String matching is an ever important task when dealing with data.
This book lists most (if not all) relevant algorithms for the job,
including high-level descriptions as well as implementations.
Analytic Combinatorics by Sedgewick
and Flajolet
The deep mathematical dive after "An Introduction to the Analysis of
Algorithms" by the same authors. Not for everybody, but gold for the
interested.
Algorithms on Strings, Trees and Sequences by Gusfield
Should you ever have to deal with huge amounts of string data (in
particular in biology contexts) this is the go-to book as it provides an
overview over the relevant data structures and algorithms.

For the Practitioner

Patterns for Parallel Programming by Mattson et al.
In practice, you might want to utilise multiple machines to deal with
large problems. This book is a high-level, example-driven overview
over ways to do so, that is how to organise and move data and computing
agents. It also addresses ways to implement them with existing tools.
A Guide to Experimental Algorithmics by McGeoch
When theoretical analysis is too hard or too coarse, you have to perform
experiments. This is an introduction into how to properly design
experiments on algorithms.
The Definitive ANTLR 4 Reference by Parr
You often need domain specific languages and tools to parse them. ANTLR is
a mature and convenient compiler generator, and this is the book best
suited for learning how to use it. Parr also has some other books on
DSLs worth checking out.

If you want very recent material, you should consider getting your people access to journals and conference proceedings, maybe by cooperating with a university library. You can also actually let them attend conferences on topics relevant to them resp. your company.

Also, consider asking your people. Have them do their own research (including free samples or copies on the web or libraries) and they will tell you which books they consider relevant to their work. There is no use in buying stuff no one will read.


comments summary:

The language $L$ is decidable.

Hint:

   $L$ is in fact empty! It contains all the machines that decide the halting problem. But, the halting problem is undecidable => there are no machines that decide it.


Questions about programming are off-topic, however there are a few computer science questions hidden in here: what n & -n does, and how floating point is represented.
The n & -n operation isolates the rightmost bit of a word in two's complement arithmetic. This is a very useful operation to know about.
Consider, for example, the following 8-bit word:
10010000

You can find the two's complement of this by taking the logical not of all the bits:
01101111

And then adding 1:
01110000

If you then take the logical and of this with the original word, you get:
00010000

This is the rightmost set bit of the original word. Please try a few examples for yourself to understand how this operation works.
Once you understand that, the rest is simply calculating base-2 logarithm of this number, essentially finding the highest/leftmost set bit, using an unnecessarily complicated method:
$$\log_2 x = \frac{\log_{10} x}{\log_{10} 2}$$
Quite apart from the fact that this is going to raise a floating point exception if you pass it zero (because what's $\log 0$?), and quite apart from the fact that the computational complexity of Math.log10 is not specified in the Java standard, floating-point numbers are stored in scientific notation in base-2 internally. The number $128.0$, for example, is stored as $1.0 \times 2^7$. So this is just an overly-complex way of extracting the exponent field of a floating-point number:
public static int getFirstSetBitPos(int n)
{
    return (int)Math.getExponent((float)(n & -n)) + 1;
}

The idea that you were probably supposed to have, however, is to use some kind of binary search. For a 32-bit integer, for example, you can tell if there is a set bit in the lowest-order 16 bits using a logical and with an appropriate mask:
(n & 0xFFFF) == 0

If there is a bit set in this range, then the answer to your question, the "find first set" of a number, is between 0 and 15, otherwise it's between 16 and 31. Either way, you have halved the search space. Turning this into an algorithm is left as an exercise.


There's a rather simple algorithm for this.

You start at the end of the array, day 10. If you only wanted to travel from that day onwards, you could buy a 1 day, 7 day, or 30 day ticket. 1 day is optimal at a cost of 2.

Then you check the second to last entry, day 9. If you only wanted to travel from that day onwards, you could buy a 1 day ticket (and add the optimal combination of tickets from day 10 at cost 2, total cost = 4), or a 7 or 30 day ticket, which is more expensive.

Again from day 8, the cheapest is a day ticket plus the optimal combination from day 9 on, total cost 6. But then you check day 5: If you buy a single day ticket, you pay 2 plus 6 for travel from day 8, total 7. But if you buy a weekly ticket, the cost is only 7. You then proceed to the beginning of the array.

int n = 6;
int dates [n+1] = { 1, 3, 5, 8, 9, 10, infinity };
int ticket [n];
int cost [n+1];

cost [n] = 0;

for i = n-1 downto 0
    cost for 1 day = 2 + cost [i+1]
    let k7 = smallest k where dates [k] ≥ dates [i] + 7
    cost for 7 day = 7 + cost [k7]
    let k30 = smallest k where dates [k] ≥ dates [i] + 30
    cost for 30 days = 25 + cost [k30]

    if cost for 1 day is smallest
        ticket [i] = 1
        cost [i] = cost for 1 day
    else if cost for 7 day is smallest
        ticket [i] = 7
        cost [i] = cost for 7 days
    else
        ticket [i] = 30
        cost [i] = cost for 30 days
    endif

That's easily done in O (n) for any fixed number of different tickets. The answer would be a bit different if you have "weekly" tickets that are valid from Monday to Sunday, or from Sunday to Saturday, depending on the country, and "monthly" tickets that are valid from the 1st to the last day of a month.


A double recursive function (ping-pong) between function to itself complexity analysis

Notice that the outer RecFunc call is just a "decoy" thrown in there to make the exercise seem more complicate than it is.
Indeed, it is irrelevant as far as the asymptotic time complexity is concerned. This is because every call to RecFunc eventually returns $1$ (that's the only possible returned value, you can prove by induction that RecFunc eventually returns), and therefore the last (outer) call to RecFunc will just be RecFun(3), which terminates in constant time. We can charge this constant time to the caller function.
Since the caller is going to spend $\Theta(1)$ time anyway, this doesn't change anything.
Then you want to analyze:
def RecFunc(n):
   if n <= 3:
      return 1

   return RecFunc(n/3) + RecFunc(n/2) + RecFunc(n/2)

Whose running time is described by the recurrence equation:
$$
T(n)=2T(n/2) + T(n/3) + \Theta(1),
$$
which can be solved using the Akra–Bazzi method. Let $p$ such that:
$
2 \cdot \frac{1}{2^p} + \frac{1}{3^p} = 1.
$
Clearly $p>0$. Then:
$$
\int_{u=1}^n \frac{1}{u^{p+1}} \mathrm{d}u =
\int_{u=1}^n {u^{-p-1}} \mathrm{d}u =
-\frac{1}{p} \cdot  \left| u^{-p} \right|_{u=1}^n
= \frac{1}{p} \cdot \left( 1 - \frac{1}{n^p} \right)
= \Theta(1),
$$
and you have:
$T(n) = \Theta(n^p)$. An approximation of $p$ is $1.3646$.
The space complexity is clearly $\Theta(\log n)$ since this is the maximum recursion depth.


Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space

The following approach is often referred to as reservoir sampling. Start scanning the set $S$ and maintain an index $j$ to the set. The first element you encounter satisfying the predicate, set $j$ to it with probability $1/1$. Update your choice for $j$ when you encounter the second such element with probability $1/2$. When you encounter the $k$th element satisfying the predicate, set $j$ to it with probability $1/k$.

The algorithm works in $\Theta(n)$ time and in constant space. For correctness, it should be shown that every item has an equal probability of being chosen and that the events they are sampled are independent. The second claim of independency is obvious: our decisions are not based on whether we have previously sampled items. The first claim (equal likelihood) can be proven quite easily with induction.

For details, see J. S. Vitter, Random Sampling With a Reservoir, algorithm R. For a more compact presentation, see for example these slides.


pseudo clique with at least connectivity x and maximum weight of the nodes

Your problem is NP hard, because with $x=1$ (real clique) and the same weight for each node you get the  maximum clique problem, which is NP complete. You can try to find a reduction in order to use a SAT solver, or just enumerate the $2^N$ subgraphs.

Furthermore, unless P = NP, there can be no polynomial time algorithm that approximates the maximum clique to within a factor better than $O(n^{1 − \varepsilon})$, for any $\varepsilon > 0$. Wikipédia

We can't even find a good probabilistic algorithm, unless NP is in BPP.

If your $x$ is fixed and $<1$, look at the following article:

An Efficient Algorithm for Solving Pseudo Clique Enumeration Problem.  Takeaki Uno.  Algorithmica, January 2010, Volume 56, Issue 1, pp 3-16.

It considers a variant of the problem with no weights, but you can substitute each vertex by a clique of size square root of its weight, if the weights are not too big, and then apply their techniques.


Transform PDA with acceptance of final state + empty stack to just final state

Given a PDA $M$, you can define the following associated languages:

The language of all words $w$ such that there is a computation path for the PDA on $w$ in which it ends at a final state with an empty stack. We denote this language by $L_1(M)$.
The language of all words $w$ such that there is a computation path for the PDA on $w$ in which it ends at a final state. We denote this language by $L_2(M)$.

The two languages are not always the same, that is, it could well be that $L_1(M) \neq L_2(M)$. You have to show that for each PDA $M$ there is another PDA $M'$ such that $L_1(M) = L_2(M')$.


Number of binary trees with given height

I assume that a binary tree is given by the following specification: a binary tree is either (a) empty or (b) is composed of a root and two (ordered) subtrees.

I also assume that height is defined so that a complete binary tree of height $h$ has $2^{h+1}-1$ nodes (for example, a single node has height $0$).

Let $A_h$ be the number of binary trees with height at most $h$. Then $A_{-1} = 1$ and $A_h = 1 + A_{h-1}^2$. This is A003095. The number of trees with height exactly $h$ is $A_h - A_{h-1}$, which is A001699. Both sequences have asymptotics of the form $\alpha^{2^h}$ for some $\alpha > 1$.


For $8$-bit floating point, you should look at $A$-law and $\mu$-law encoding standards:

http://en.wikipedia.org/wiki/%CE%9C-law_algorithm

http://en.wikipedia.org/wiki/A-law_algorithm

Depending on your input range, you may need some scaling.


LL1 parsing algorithm for strings generated by a given grammar

Here's a possibly useful quote from Aho, Lam et al ("the Dragon Book"). (Emphasis added.)

A grammar $G$ is $LL(1)$ if and only if whenever $a \to \alpha | \beta$ are two distinct productions of $G$, the following conditions hold:

For no terminal $a$ do both $\alpha$ and $\beta$ derive strings beginning with $a$.

…


Algorithm to maximize $j-i$ subject to $A[j]>A[i]$

As you mention, the candidate $i$s are those who are left-to-right minima, and they form a decreasing sequence. Similarly, the candidate $j$s are right-to-left maxima, and they form an increasing sequence going from right to left (so a decreasing sequence in the usual order). Now imagine keeping two points, one on the left-to-right minima, starting at the leftmost, and another on the right-to-left maxima, starting at the rightmost. Is there a way to traverse both lists in $O(n)$, answering your question on the way?


finding all cyclic substrings of a string

Any algorithm that runs in $O(n^2)$ time can access at most $O(n^2)$ different memory locations during the course of its execution.  Thus, if you replace memory with a hashtable (instead of accessing address $a$, access the hashtable at key $a$), you obtain an algorithm with expected running time $O(n^2)$ and space $O(n^2)$.  If you care about theoretical proofs, you can use a balanced binary search tree instead of a hashtable and obtain a worst-case time bound of $O(n^2 \log n)$ time and $O(n^2)$ space.


No.
Note that given languages $A,B$ and a reduction $A\le_L B$, you get that $B$ is at least as hard as $A$, but that's about it.

You can contradict the above statement with the following extreme:

Take $A = \{0\}$, then $A\in \text{PSPACE}$, and take $B= H_{TM}\cup\{0\}$.

Define $f$ to be the following reduction $A \le_L H_{TM}\cup\{0\}$ (we can assume that $1\notin H_{TM}$):

$$f(0) = 0$$ $$\forall x\in \Sigma^*\setminus\{0\}  . f(x)=1$$.

Clearly $f$ works in logarithmic space, but $B$ is clearly not in $\text{PSPACE}$. In fact, it isn't even in $\text{R}$.


Acquiring the necessary background for research

In my experience, it is better to learn stuff as you need it. Otherwise, you don't have the motivation to really "get" it, and there is always the risk of getting lost in the forest of interesting stuff out there (that in the end is of no use). Be at the lookout for results that could help you (Google or citeseerx or ..., or even this site, are your friends).

Another piece of advise: Start writing right now. Editing your ramblings into something coherent later on is easy, sitting in front of a blank screen with writer's block when the deadline approaches is extremely painful. Write down what you do right now; if it works out it stays for later, if not it gets erased (and you don't get embarassed by your dumb attempts ;-). That way it doesn't happen to you that you know something is right, but don't remember why... and have to redo lots of work (happened to me!).

Make a short (3-4 line) summary of each paper or other reference that looks relevant, add it to your bibliography. Reading the stuff so you are able to extract what is relevant to you helps understanding the stuff, the summaries help in locating material later. And the collection of summaries will be your chapter on state of the art (after cleanup).

As a final comment, use LaTeX (it looks much nicer, has very good handling of bibliographies ;-), and perhaps asymptote for figures (it is a bit hard to learn, but has C++-like syntax to manipulate points and define lines, and produces excelent results). Put the whole stuff under version control (my favorite is git, but use whatever you are confortable with). That  way you'll be able to have an up-to-date backup (preferrably on some other machine!), and go back if you really mess up (Murphy's lat assures us you will).


$NL=P$ is not considered likely by the experts.
I found a few SE questions on this topic: [1] [2]
The corollaries include:

$P\subseteq L^2$ by Savitch's theorem
$NC=P$ by the Squeeze theorem
$EXP=PSPACE$ by $P\subseteq polyL$

I would like to include or exclude $P=L^k$, $k\in[1,2]$, but I have not collected sufficient evidence for or against that conclusion.


Yes the File has a binary representation and it can start with a leading zero.
To verify this open any file from your computer with an hex editor and modify the leading hex to 00.
You would most likely be unable to open the file, because you damage the signature but it still can be considered a valid file.


TM decidability using pigeonhole principle

I think since the input word is delimited by special symbols, which the machine cannot move past, the language accepted by such a device should be finite. We know that all finite languages are regular, and regular languages are decidable by a TM. Does it make sense for answering the question?

You can easily simulate any DFA in your model, and so your model accepts all regular languages. In particular, it also accepts some infinite languages, for example the language of all words.

Your class of machines is two-way finite automata, and it is known to accept the regular languages, that is, it coincides in power with one-way finite automata such as DFAs and NFAs.
However, that is not the answer that the setter had in mind. Rather, imagine the working of such a machine, having $m$ states, on an input word of length $n$. The head could be in $n+2$ different positions, and consequently the machine can be in $(n+2)m$ different configurations. Therefore, after that many steps, either the machine has halted (either accepting or rejecting the input), or some configuration has repeated (by the pigeonhole principle), in which case the machine is in an infinite loop, and will never accept. Hence after $(n+2)m$ steps we can already tell the fate of the input.


Does Church-Turing thesis also apply to artificial intelligence?

The Church-Turing thesis says that the informal notion of an algorithm as a sequence of instructions coincides with Turing machines. Equivalently, it says that any reasonable model of computation has the same power as Turing machines.

An artificial intelligence is a computer program, i.e., an algorithm. If the Church-Turing thesis holds, then you could implement that algorithm on a Turing machine. Since Turing machines cannot decide their own halting problem, it follows that, under the Church-Turing thesis, artificial intelligences cannot decide the halting problem for Turing machines.


What is the difference between a TM accepting and deciding a language?

There is major difference. A turing machine "accepts" a language, if it enters an accepting state for any input from the langue, while it "decides" the language if it "accepts" it and enters a rejecting state for any input not in the language.

These are different, because there is a third thing that a Turing machine can do: never stop. Such Turing machine accepts the language, but does not decide it.

See also this other question and definition of decidable language on WP.


Find lines segment portions close together

Here is a derivation that shows how to solve this problem, using a bit of vector arithmetic.

You can project a point $P$ onto the line $A_1B_1$ using vector arithmetic; in particular, the projection of $P$ is $${(B_1-A_1)^\top (P-A_1) \over \|B_1-A_1\|_2^2} (B_1-A_1) + A_1,$$ where $v^\top$ denotes the transpose of vector $v$, so the vector measuring the orthogonal distance from $A_1B_1$ to $P$ is

$$D=P-{(B_1-A_1)^\top (P-A_1) \over \|B_1-A_1\|_2^2} (B_1-A_1)  - A_1.$$

Every point $P$ on the line segment $A_2B_2$ has the form $P=\alpha A_2 + (1-\alpha)B_2$, for some $\alpha \in [0,1]$.  So, we can write $D$ in the form

$$
\begin{align*}
D=\;&\alpha A_2 + (1-\alpha)B_2 - A_1\\
 &- {(B_1-A_1)^\top (\alpha A_2 + (1-\alpha)B_2-A_1) \over \|B_1-A_1\|_2^2} (B_1-A_1).
\end{align*}
$$

Notice that this is a linear function of $\alpha$, when $A_1,B_1,A_2,B_2$ are fixed.

Let the $x,y$-coordinates of $D$ be $x_D,y_D$, i.e., $D=(x_D,y_D)$.  The above equation implies that there are constants $a_0,a_1,a_2,a_3$ such that

$$x_D=a_0 \alpha + a_1, y_D = a_2 \alpha + a_3.$$

The $a_0,\dots,a_3$ depend only on $A_1,A_2,B_1,B_2$ (but not on $\alpha$) and can be readily computed using the formula above.

Now we want this vector $D$ to be of length at most $\tau$, i.e., $\|D\|_2 \le \tau$.  In other words, we want

$$x_D^2 + y_D^2 \le \tau.$$

This is equivalent to

$$(a_0 \alpha + a_1)^2 + (a_2 \alpha + a_3)^2 \le \tau.$$

That is a quadratic in the unknown $\alpha$, so we can readily find the range of $\alpha$ where this inequality holds by using the quadratic formula (basically, find the roots of the quadratic equation $(a_0 \alpha + a_1)^2 + (a_2 \alpha + a_3)^2 = \tau$, and these are the endpoints of that range, except that you should clamp to the range $[0,1]$).  Say that the inequality holds for $\alpha$ in the range $[\alpha_\ell,\alpha_u]$.  Then it follows that the points on the line segment $A_3B_3$ are all of distance at most $\tau$ to the line $A_1B_1$, where $A_3 = \alpha_\ell A_2 + (1-\alpha_\ell) B_2$ and $B_3 = \alpha_u A_2 + (1-\alpha_u) B_2$.

This would describe how to find all points on the line segment $A_2B_2$ that are distance at most $\tau$ from the line connecting $A_1$ and $B_1$.  However, we really want to find all points that are distance at most $\tau$ from the line segment $A_1B_1$.  So, we want to constrain the projection of $P$ to be between $A_1$ and $B_1$, i.e., we want to constrain $D$ to be between $0$ and $B_1-A_1$.  By solving systems of linear equations, you can find $\alpha_0$ such that $(a_0 \alpha_0+a_1,b_0 \alpha_0+b_1)=(0,0)$ and $(a_0 \alpha_1+a_1,b_0 \alpha_1+b_1)=B_1-A_1$.  Then, we replace $[\alpha_\ell,\alpha_u]$ (obtained above by the quadratic formula) with the intersection of ranges $[\alpha_\ell,\alpha_u] \cap [\alpha_0,\alpha_1]$.  This gives us all points on the line segment $A_2B_2$ that are distance at most $\tau$ from the line segment $A_1B_1$.

This solves your question of how to find all points on the line segment $A_2B_2$ that are distance at most $\tau$ from the line segment $A_1B_1$.  You can repeat the same procedure a second time to find all points on the line segment $A_1B_1$ that are distance at most $\tau$ from $A_2B_2$.


Reducing TSP to HAM-CYCLE to VERTEX-COVER to CLIQUE to 3 CNF-SAT to SAT

A couple of the ones you're looking at here are pretty simple actually (at least to sketch!). For all of these, there are many other ways to do it, even many other sensible ways, so these are just attempts to pick the simpler approaches (we'll see if I succeed).

As mentioned in one of the comments on the question, $3SAT$ to $SAT$ is trivial, an instance of $3SAT$ is already and instance of $SAT$, so there's no work needed at all.

To get from $VERTEX$ $COVER$ $(VC)$ to $CLIQUE$ we can do a couple of short jumps, that'll also put another problem in the loop. $VC$ is the dual of $INDEPENDENT$ $SET$ $(IS)$, that is, we can find a vertex cover of size $k$ in a graph $G$ iff we can find an independent set of size $n-k$ in $G$. Play around with this a little and you'll see why this is true. If we then take the edge-complement graph $\bar{G}$ of $G$, an independent set of size $t$ in $G$ is the same as a clique of size $t$ in $\bar{G}$, so that gets us to $CLIQUE$.


What's the difference between declarative syntax and encapsulation?

They're orthogonal.

In declarative programming, you describe what would count as an acceptable solution, without necessarily describing how to find it.  For instance, a declarative program might have rules like "if you want to install the package gcc, you must have first installed the binutils and cpp packages" and "if you want to install the binutils package, you must have first installed coreutils".  It's up to the platform to figure out a way to meet all of these constraints.

Encapsulation refers to protections that prevent the client of an API from tampering with the internal state of the service that implements the API.   Nothing here says the API has to be declarative in nature.  You could have a API that is more declarative in nature (e.g., the client provides some constraints, and the service figures out how to meet them), or you could have an API that is more operational in nature (e.g., the client specifies what actions should be performed, rather than listing the desired goal and leaving it to the service to figure out what actions will accomplish that goal).

So, you can have an encapsulated API that is not declarative in nature.

To elaborate: invoking an API is not necessarily declarative in nature.  You can design APIs that are declarative in feel; and you can also APIs that are operational in feel.  Not all APIs will be declarative.  For example:

A declarative API might let you give it some rules/constraints, and then specify the goal (I want gcc to be installed), and then let the service infer a sequence of actions that will achieve your goal (a sequence of packages to install, and what order to install them in).  For example, the client might call findWayToInstall("gcc"), and the service comes up with a sequence of packages to install that ends with gcc installed -- that'd be a declarative API.
An operational API might let you repeatedly give it an action to perform (e.g., you repeatedly invoke installPackage(); this succeeds if you've met all the prereqs, and it's up to you to identify a valid sequence of packages that ends with gcc installed).  For example, the client might call installPackage("coreutils") then installPackage("binutils") then installPackage("cpp") then installPackage("gcc"), and if this sequence of operations meets all of the prerequisites, it ends with gcc installed.  With this API it is the caller's responsibility to identify a sequence of actions that ends with gcc installed.  Thus, this kind of API is more operational than declarative in nature.

Of course, declarative vs operational are just concepts to help us talk about properties of programming languages and APIs.  There's no hard, bright line between them.  It's not black-and-white; there's a spectrum.  But they are useful concepts nonetheless.


Why isn't TQBF part of the polynomial hierarchy?

What you're missing is the distinction between QBF and 2QBF.

It's an open problem whether TQBF is contained in any level of the polynomial hierarchy, but it'd be reasonable to expect that TQBF is probably not contained in any level of the polynomial hierarchy.

TQBF is PSPACE-complete.  Also, if PSPACE = PH, then the polynomial hierarchy collapses.  Thus, if TQBF is in some level of the polynomial hierarchy, then so is all of PSPACE, and thus the polynomial hiearchy collapses.

It is conjectured that the polynomial hierachy does not collapse.  However, this is merely a conjecture, analogous to the conjecture that P $\ne$ NP; whether or not this is true is an open problem.

  TQBF consists of alternating quantifiers, so does $\Sigma^2_n$ for fixed $n$.

Giraffes consist of atoms.  So do light bulbs.  Therefore, every giraffe is also a light bulb.

What's wrong with that reasoning?  The same thing that's  wrong with your reasoning.

Check your definitions.  $\Sigma_n^2$ allows formulas that contain only two alternations of quantifiers, i.e., 2QBF.  QBF allows an unlimited number of alternations of quantifiers.  2QBF is complete for $\Sigma_n^2$; QBF is complete for PSPACE.


BTSP asks to find a Hamiltonian cycle in a weighted graph, which minimizes the weight of its most weighty edge.

TSP asks to find a Hamiltonian cycle in a weighted graph, which minimizes the sum of weights of its edges.


How to determine(with some confidence) if two extremely long lists of numbers (terabytes) are similar?

Check out Jaccard Similarity, as it gives a measure of set similarity.  See MinHash, locality sensitive hashing.


Approximate probabilities of passing a NIST statistical test

Have a look at TestU01. It's another testing suite that has NIST built in. It also has implementations of most of the well-known RNGs, so you can compare. The documentation may have some results listed in it.


Suppose that $A=(Q,\Delta, \Gamma, \delta, q_0, \gamma_0, F)$.

Define $\operatorname{Prefs}(u)$ to be the set $\{v|\exists w, u = vw\}$ of prefixes of $u$.

Define $A':=(Q',\Sigma, \Gamma, \delta', q_0', \gamma_0, F')$ by:

$\displaystyle Q':= \left(Q\times \left(\bigcup_{a\in \Sigma}\operatorname{Prefs}(h(a))\right)\right) \sqcup \left(Q\times \Sigma \right)$. A state $(q,u)$ with $u\in\operatorname{Prefs}(h(a))$ will mean "I'm in state $q$ in $A$, I've read $u$ and am waiting for the rest of $h(a)$ and then I'll go to $(q,a)$" while a state $(q,a)$ means "I've read $h(a)$ and will now simulate a transition reading $a$ in state $q$ in $A$ to arrive to some state $(q',\varepsilon)$".
Transitions are (where if a transition doesn't mention the stack, it means it doesn't change it):

$(q,u)\overset{b}{\to}(q,ub)$ whenever the destination state exists (i.e. if you can read the letter while remaining a prefix of some $h(a)$, you can just keep reading)
$(q,h(a))\overset{\varepsilon}{\to}(q,a)$ (i.e. at any point, if the word I've read is the image of a letter by $h$, I can replace it by its preimage)
$(q,a)\overset{\varepsilon,...}{\to}(q',\varepsilon)$ whenever $q\overset{a,...}{\to}q'$ in $A$ (where both $...$ are the same thing) (i.e. if I just read the image of $a$, simulate reading $a$ in $A$)

$q_0':=(q_0,\varepsilon)$
$F':=F\times \{\varepsilon\}$

Then (I think that) $L(A')=h^{-1}(L(A))$.

What you call "buffer" would be the right component of the states used to remember the prefix of $h(a)$ you've read.


Lower bound on positive coefficients of the optimum of 0,1-linear programming problem

$\frac 1n$ is not a lower bound.
For example, let $n=10$.
Consider 3 set of equations (you can get equalities by considering both $a^\top v \le 1$ and $a^\top v \ge 1$):

\begin{align}
v_1 + v_2 + v_3 \qquad = 1\\
\qquad v_2 + v_3 + v_4 = 1\\
v_1 \qquad  + v_3 + v_4 = 1\\
v_1 + v_2 \qquad + v_4 = 1\\
\end{align}
It's easy to check that $v_1=v_2=v_3=v_4=\frac 13$ is the unique solution.

Consider $v_5 + v_6 + v_7 + v_8 + 0 \cdot v_9 = 1$ and, similarly to the above case, all cyclic shifts of $(v_5, \ldots, v_9)$. Again, the unique solution is $v_5 = v_6 = v_7 = v_8 = v_9 = \frac 14$.

The last equation is
$$v_1 + v_2 \qquad + v_5 \qquad + v_{10} = 1$$
Then $v_{10} = 1 - 2 \cdot \frac 13 - \frac 14 = \frac 1 {12}$.

Generalizing it, you can always obtain coefficient $\frac 1{k (k+1)}$ using $2k + 4$ variables.
I think that by properly selecting numbers $p_1, \ldots, p_k$, you should be able to get a coefficient as small as $O\left(\frac 1 {\prod_i p_i}\right)$ with $O\left(\sum_i p_i\right)$ variables.


How does modulus affect the regularity of language?

You seem to be assuming that, to determine whether $n(a)-n(b)$ is a multiple of $m$ requires us to computer $n(a)$ and $n(b)$, subtract them, and then calculate the remainder. You're correct that a finite automaton can't do that, but it's not the only way.

The first thing to note is that you can computer $n(a)-n(b)$ directly. Initially, you've seen no $a$s or $b$s so the difference is zero. Each time you see an $a$, the difference increases by one; each time you see a $b$, the difference decreases by one. OK, that's a bit smarter but it still requires us to compute the value $n(a)-n(b)$, which could still be arbitrarily big, so still can't be done with a finite automaton.

The second thing to note is that, because of the way that modular arithmetic works,
$$(x-y)\bmod m = ((x\bmod m) - (y\bmod m)) \bmod m\,.$$
In other words, you can do everything modulo $m$. Each time you read an $a$, the difference increases by one modulo $m$. and each time you read a $b$, it decreases by one modulo $m$.

This means that you can recognize the language with an automaton with $m$ states: one for each value of $n(a)-n(b)\bmod m$.


Concept of M-augmenting path to find a larger matching than $M$

Actually, I realized what I was missing shortly after posting the question and squinting at the pictures again. Instead of deleting, figured I'd simply post the answer for future reference. The thing I was missing was that the new matching won't have the same edges as the original matching. In the first figure, 3->5->2->4 is such a path and 2->4 $\cup$ 3->5 becomes a larger matching.


Pushdown Automaton to accept all strings such that no prefix has more 1’s than 0’s

If we have a word, $w=a_1a_2\dots a_n$ where the $a_i$ are characters from the underlying alphabet, then the prefixes of $w$ are the empty word, $\epsilon$, and the words $a_1$, $a_1a_2$, $a_1a_2a_3$, ..., $a_1a_2\dots a_{n-1}a_n$. In informal terms, the prefixes of a word consist of all left-hand segments of the word.


Chazelle's discrepancy book: greedy method

My oversight was that $|S| = m$, so there are $m$ events of the form "$S_i$ is bad".  Then since $Pr[\cup_{i=1}^m A_i] \le \sum_{i=1}^m Pr[A_i]$ for any collection of events $\{A_i \mid i=1,2,\dots,m\}$, it follows that $Pr[\text{some }S_i\text{ is bad}] < 1$, so $Pr[\text{no }S_i\text{ is bad}] > 0$.


Graphs that are connected vs strongly connected vs reachable

Connected: Usually associated with undirected graphs (two way edges): There is a path between every two nodes.

Strongly connected: Usually associated with directed graphs (one way edges): There is a route between every two nodes (route ~ path in each direction between each pair of vertices).

Reachable (from $A$ to $B$): A path exists in the graph between nodes $A$ and $B$. (Ability to get from one vertex to another)

Note: Got some terminology from:
https://mathoverflow.net/questions/6833/difference-between-connected-vs-strongly-connected-vs-complete-graphs


to some degree all refs on the subject have a formidable inherent complexity due to the subject matter. however, here is a classic, highly accessible ref on Gödel's thm that may be helpful, written in "popular science" style by a philosopher & mathematics historian for a broad audience, breaking it down into intuitive everyday language.

Gödel's Proof Nagel/Newman

here are some other similar but more technical refs that may be helpful

An Introduction to Gödel's Theorems Smith
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse Franzén

there are also many refs on Turing's halting problem. one worth mentioning, a step-by-step walkthrough/tour of the original proof, but which is very advanced due to retaining all the mathematical complexity/detail:

The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine Petzold

on the other hand most of the proof complexity of the halting problem is associated with the proof of the existence of the Universal TM, wikipedia has a pretty good outline. this can be understood as a simulation or emulation of one machine by another. therefore studying the theory of machine emulation (now quite frequently applied with video games) may be helpful.