Can a program exist that halts only if it can prove that it doesn't halt? Consider a program P that enumerates possible proofs in some proof system and halts only if it finds a valid proof that P does not halt. Clearly no such proof exists, or the program would eventually find it, causing a contradiction. But that argument itself appears to constitute exactly such a proof. It seems like that means that P cannot exist (for proof systems sufficiently powerful to express that argument), but I can't otherwise see why that should be the case.

We can define a sound proof system as a computable function $\Pi$ which maps strings (proofs) to strings (statements proved), with the following property: if $\Pi(\pi) = p$, then $p$ encodes a true statement. We think of $\pi$ as a proof of $p$. (If $\pi$ is not a valid proof, then $\Pi$ outputs some fixed true statement.) We consider sound proof systems which are rich enough to prove statements about the halting of Turing machines.
Let $Q(q)$ be the program that enumerates over all strings, and halts if it ever finds a string $\pi$ such that $\Pi(\pi) = p$, where $p$ is an encoding of "The Turing machine encoded by $q$ never halts when run on $q$". Let $[Q]$ be an encoding of $Q$. If we run $Q$ on $[Q]$, then $Q$ halts iff there is a $\Pi$-proof that $Q$ doesn't halt when running on $[Q]$.
(Using the recursion theorem, we can transform $Q$ to a Turing machine $P$ which runs $Q$ on $[P]$, which is the setup in the original post.)
If there is a $\Pi$-proof that $Q$ doesn't halt when running on $[Q]$, then $Q$ doesn't halt when running on $[Q]$. We conclude that there cannot be any $\Pi$-proof that $Q$ doesn't halt when running on $[Q]$, because if such a $\Pi$-proof existed, then $Q$ would halt when running on $[Q]$. Therefore $Q$ doesn't halt when running on $[Q]$. However, there is no $\Pi$-proof of this fact.
This is an example of incompleteness. The proof system $\Pi$ is unable to formalize the argument above. One reason is that $\Pi$ cannot even prove its own consistency (i.e., that it does not prove a contradiction, as per Gödel's second incompleteness theorem), not to say soundness (which $\Pi$ may not even be able to express).


Closure properties of undecidable languages I know that the decidable are close under: complementation, union, intersection and concatenation?

What about the undecidable languages? I think they are close under complementation, but not under concatenation, union and intersection. But I don't know how to prove it...

My prove

  "Lets say L is undecidable lang. Because L is undecidable lang we know
   one of the following:

  there is a word w1 from L that there is no TM that stop for this
   word
  there is a word w2 in L that stopping in reject state in every TM
  there is a word w3 Not from L that stopping in accept state in
   every TM

  L' is the complementation lang of L

  If 2, the word w2 that stopping in reject state, will stop in the
  accept state for every TM, but w2 not in L' so L' is Undecidable.

  If 3, the word w3 that stopping in accept state, will stop in the
  reject state for every TM, but w2 is in L' so L' is Undecidable.

  If 1, so all the TM are not stopping for w1 so L' is Undecidable???? "

Let $K$ be some undecidable language. Define languages $A_0,A_1,B_0,B_1$ as follows:
$$
A_0 = \{ 0 w : w \in K \}, A_1 = \{ 1 w : w \in K \}, \\
B_0 = A_0 \cup \{ 1 w : w \in \{0,1\}^* \}, B_1 = A_1 \cup \{ 1 w : w \in \{0,1\}^* \}.
$$
See if you can use these languages to show that the collection of undecidable languages is not closed under concatenation, union or intersection.

As for complementation, try to use the fact that if you can decide a language $L$ then you can decide its complement $\overline{L}$ (why?).


Partitioning a set to the maximum number of subsets summing to zero Given a multiset of numbers $X = \{x_1, \dots, x_n\}$, such that $\sum X = 0$, how can $X$ be partitioned to the maximum number of subsets so that each subset sums to zero?

I have searched around a lot, but none of the partition or packing problem variants seem to address this particular case.

3-Partition reduces to this problem, so it's strongly $NP$-hard. Moreover, 4-Partition also reduces to it (and the blowup is linear), so assuming the exponential time hypothesis there's no $2^{o(n)}$ algorithm.

Using dynamic programming there's a $O^*(4^n)$ algorithm, it would be interesting if you could do $2^n$ or even $1.99^n$.


In the PCP, can we remove all dominos with the same top and bottom strings and still get a match? Suppose we have an instance P of the PCP, and there exists a match for it.
I am wondering if we remove all dominos that has the same string on the top and bottom, would there still be a match?
My intuition is yes, there would still be a match, but i don't know how to justify.
Can someone please give me some hints or give a counterexample?

Intuitively this seems like it would be true at first, but it's because we think too literally about the domino example. Remember in the PCP the strings on the top and bottom of the domino are not necessarily the same length (i.e, the dominos are not necessarily rectangular)
Consider the following example
\begin{align*}
P=\left\{\left(\begin{array}[ccc] \\
1 & & \\
1 & 2 & 3 \\
\end{array}  \right),
\left(\begin{array}[c] \\
2  \\
2  \\
\end{array}  \right),
\left(\begin{array}[cc] \\
3 & 2  \\
4 &    \\
\end{array}  \right),
\left(\begin{array}[cc] \\
4 & 4  \\
4 &   \\
\end{array}  \right)
\right\}
\end{align*}
Here notice there is a match by placing each of the dominos exactly once, and in the order they appear above. On the other had let's try another version.
\begin{align*}
P'=\left\{\left(\begin{array}[ccc] \\
1 & & \\
1 & 2 & 3 \\
\end{array}  \right),
\left(\begin{array}[cc] \\
3 & 2  \\
4 &    \\
\end{array}  \right),
\left(\begin{array}[cc] \\
4 & 4  \\
4 &   \\
\end{array}  \right)
\right\}
\end{align*}
Notice $P'$ was obtained from $P$ by removing $\left(\begin{array}[c] \\
2  \\
2  \\
\end{array}  \right)$, which has the same string on top and bottom.
If there were a match in $P'$ it must start with $\left(\begin{array}[cc] \\
4 & 4  \\
4 &   \\
\end{array}  \right)$ since that is the only time starting and ending with the same letter that can be added to (there is no tile starting with $2$ on top to place after $\left(\begin{array}[ccc] \\
1 & & \\
1 & 2 & 3 \\
\end{array}  \right)$.
This can be followed by either another $\left(\begin{array}[cc] \\
4 & 4  \\
4 &   \\
\end{array}  \right)$, or $\left(\begin{array}[cc] \\
3 & 2  \\
4 &    \\
\end{array}  \right)$. The first is not helpful, and the second places the substring $32$ on the top, which can never be formed on the bottom. So $P'$ does not have a match.


Can input to a Turing machine be of infinite length? Considering only the alphabet $\Sigma = \{0,1\}$, the strings which can be given as input to the Turing machines are from the set $\Sigma^{*}$. But does it make sense for the input to be an infinite binary string ? For example if a Turing machine accepts all strings starting with a 0, does a binary string of infinite zeros also belong to the language accepted by the Turing machine ?

There is no problem in running a Turing machine on a tape initialized with an infinite string, although this is not usually considered. We still need the machine to terminate in finite time, though. There are also notions of infinite-time computation, which may be appropriate here.


Any mathematical tools for analyzing mutable memory Wondering if there are any documents, theories, or methodologies for dealing with mutable memory mathematically. Basically a formal algebraic model of how computers manipulate memory. Along the lines of, say I want to model an add operation at a low level, and it writes its output to a register. Then we can model the computer state as a memory, and:

$$add : a \times b \times m \to m'$$

the function $add$ transforms the memory into a different state, holding the final value. Then the second time we call add, the memory is different than it was before. So it's always changing:

$$m \neq m' \neq m'' \neq \dots \neq m^{(n)}$$

Wondering if there are any formalisms out there that deal with this. I would specifically like to see it applied to abstract algebra or category theory. Whereas in abstract algebra typically, everything is immutable and you never worry about "state". I would like to explore the state / mutable memory from a math framework.

See separation logic and theory of arrays in SMT solvers.  Both of these provide a principled, mathematically rigorous foundation for reasoning about mutable memory.


how to calculate time complexity of non terminating loops I'm studying about data structures and algorithms in that Time complexity  and calculating time complexity of the programs.

I just wondered that how to calculate time complexity of  non terminating loops such as infinite loops

If the program runs forever, its running time is infinite.  So, if it always enters an infinite loop, its running time is infinite.

This is a degenerate case.  Normally we focus only on algorithms that are certain to terminate (but see footnote).

See also How to come up with the runtime of algorithms? and Is there a system behind the magic of algorithm analysis?.

Footnote: When studying randomized algorithms, this gets relaxed a bit, and we frequently look at algorithms that in principle could run forever if they keep getting an unlucky choice of random bits, but whose expected running time is finite.  However, if you're just starting with algorithms, it's likely that you are dealing with deterministic algorithms, not randomized algorithms, so this is unlikely to come up.


Knight on a chessboard This is a Hackerrank challenge

$Knight$ is a chess piece that moves in an L shape. We define the possible moves of $Knight(a,b)$ as any movement from some position $(x_1, y_1)$ to $(x_2, y_2)$ satisfying either of the following:
 $x_2 = x_1 \pm a$ and $y_2 = y_1 \pm b$, or
 $x_2 = x_1 \pm b$ and $y_2 = y_1 \pm a$

Given the value of $n$ for a square chessboard, answer the following question for each $(a, b)$ pair where :
$1 \leq a \leq b \lt  n$

Constraints
$1 5 \leq n \leq 25$

What is the minimum number of moves it takes for $Knight$ to get from position $(0, 0)$ to position $(n-1, n-1)$? If it's not possible for the Knight to reach that destination, the answer is -1 instead.

If $a = b$ then it is simply $(n-1) / 2a$ if it is evenly divisible

What I cannot figure out is when some of the steps need to be backwards $x_2 \lt x_1$.

Can this be solved with an algorithm other than brute force?
If so what is the algorithm?

Brute force to me is iterate over all possible moves.

If brute force is it safe to assume $a$ and $b$ would never both be negative on a move? Answer is no.  If brute force could it be limited to one diagonal or the other?  Answer is no.

You could use the breadth first search (BFS) algorithm. The knight may move at most to eight cell (from a single position) which means that if each cell is treated as a single node then degree of each node is at most eight and so the number of edges is at most $\frac{8N}{2} = 4N$, where $N = n^2$ is the total number of nodes/cells and $n\times n$ is the size of the chessboard. Since BFS' complexity is $O(V + E)$ your algorithm will run in $O(N+ 4N) = O(N)$.

Warning: do not try to create a graph from the chessboard. It is overkill. You just need to maintain queue and mark all visited cells as you iterate. While the knight is at the position $(i,j)$ just compute all possible moves from this position and push them into the queue if they are not already visited and you haven't yet reached $(n-1, n-1)$.


Using induction to prove a big O notation I'm trying to prove that the following recurrence relation has a runtime of O(n):

 fac(0)   = 1
 fac(n+1) = (n + 1) * fac(n)

I think that I can use induction in the following manner:

Base case

If n=0 then fac(n) = fac(0) = 1

Inductive case

Assume that fac(n) has a runtime of O(n)

fac(n+1) = (n + 1) * fac(n)

Therefore fac(n+1) has a runtime of O(n+1)

However, I have a suspicion that my inductive case doesn't really prove much. Maybe this is because the my assumption for the inductive case is wrong?

Can you point me in the right direction to prove this runtime?

In essence, your proof is correct. A more general solution that you can use for recursive algorithms is this.

The way to solve this is to create a function T(n) that measures the runtime of the function and figure out the big O notation for it.

To solve a problem of size n, I must solve a problem of size n - 1. Then I must perform constant time arithmetic to get the answer. Thus :

T(n) = T(n - 1) + O(1)

Prove T(n) is O(n) ie by definition

T(n) <= cn for all n >= n0

Assume:

T(n - 1) <= c(n - 1)

then

T(n) = T(n - 1) + O(1)
T(n) <= c(n - 1) + d
T(n) <= cn + d - c
T(n) <= cn for c >= d

use T(1) as a base case to complete the proof, giving you n0 = 1


Time Complexity of Memoized Solution I was solving Stone Game II on LeetCode. I was able to come up with a recursive (TLE) solution, which I optimized using memoization. The recursive solution computes a function $u(i,m)$, depending on an array $A_1,\ldots,A_n$, where:

$i$ is the starting index
$2m$ is the maximum size of the window at $i$

Here is the recurrence:
$$
u(i,m) =
\begin{cases}
\sum\limits_{j=i}^{n} A_j & \text{if } i + 2m-1 > n, \\
\sum\limits_{j=i}^{n} A_j - \min\limits_{\substack{0 \leq k \leq 2m-1 \\ i+k \le n}} u(i+k+1, \max(m,k+1)),
& \text{if } i + 2m-1 \le n.
\end{cases}
$$
(Using $O(n)$ preprocessing, the sums can be computed in $O(1)$.)
I am interested in the value of $u(1,1)$.
However, I am not sure about the time complexity of this solution.
According to me :

There are $m \times n$, where:

$n$ is the number of elements in $A$.
$m$ is the width of window that varies at each step.

Each state is being calculated only once.
$m$ can not be greater than $n$, the size of $A$.

Hence, the time complexity of the solution should be $O(n^2)$.
Is there something that I am missing? Is there a mathematical way to prove this?

For each $i,m$ in the range $n/3 \leq i,m \leq 2n/3$, computing the recurrence requires going over $\Theta(n)$ values of the parameter $k$, hence calculating $u(i,m)$ for all of these values of $i,m$ requires time $\Theta(n^3)$.
Do you actually encounter such values of $i,m$ when calculating $u(1,1)$? It's not immediately clear to me, but you'll have to rule it out if you want to prove a better upper bound on the running time of your procedure.


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

#include <stdio.h>

int ack(m,n)
int m,n;
{
int ans;
if (m == 0) ans = n+1;
else if (n == 0) ans = ack(m-1,1);
else ans = ack(m-1, ack(m,n-1));
return (ans);
}

int main (argc, argv)
int argc; char ** argv;

{ int i,j;
for (i=0; i<6; i++)
for (j=0;j<6; j++)

printf ("ackerman (%d,%d) is: %d\n",i,j, ack(i,j));
}

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


Dijkstra’s in a graph with negation of edges Let say I have a directed graph G with positive edges and I create a new graph, G', by replacing the weight of each edge by the negation of its weight in G. If for a given source vertex s, I compute all shortest path from s in G' using Dijkstra’s algorithm. Will the resulting paths in G’ be the longest (i.e., highest cost) simple paths from s in G. True or false? And please, justify.

The answer is FALSE.

Contradicting example: (starting from S)

Running Dijkstra on the following graph will not find the longest path from S to D (S->A->B->C->D). Due to removing node C from the queue too soon (before the relaxation of node B), hence prev(D) = E.

Please follow the correctness argument of Dijkstra's algorithm, which relies heavily on the edge weights being positive.

In addition, longest path problem is computationally hard. (NP-Hard).


Running Time of Sorting Algorithm Determine the asymptotic running time of the sorting algorithm maxSort.

Algorithm maxSort(A)
Input: An integer array A
Output: Array A sorted in non-decreasing order

1. for j <- n-1 down to 1 do
2.     m <- 0
3.     for i = 1 to j do
4.         if A[i] > A[m] then m <- i
5. exchange A[m], A[j]

Can you say anything about the "best-case" function $B_{maxSort}(n)$?

With a question like this, what is the way to tackle it? I have tried counting number of executions per line, but I can't translate it into asymptotic notation. My intuition is that it has something to do with $n^2$ due to the nested for loop, but I am not sure about this.

When the indexes of the for loops depend on each other you can think like this:

When the index of the outer for loop takes its first value how many times is the inner for repeated? What about when the index of the outer for takes its second value? ... What happens when the index of the outer for takes its last value?

In your case:
When $j = n-1$, $i$ is repeated $n-1$ times.
When $j = n-2$, $i$ is repeated $n-2$ times.
...
When $j = 1$, $i$ is repeated $1$ time.

In total, the inner for loop is executed $(n-1) + (n-2) + ... + 2 + 1 = \dfrac{n}{2} * n = n^2$ times. Therefore the complexity is $O(n^2)$.

The best case is obviously when the matrix is already sorted.


Any path detecting between A to B In my world there are nodes and lines, I want to see if there is any path between node A, and node B, that do not cross any line(including the lines of the path itself) and do not go thru the same node twice. What would be the efficiency of such algorithm and where can I find more information about it.

So far I been reading about A* algorithm, but I do not need the shortest path, just to see if there is any path like this exist at all.

Depth-first search or Breadth-first search. Note that Dijkstra's algorithm, essentially reduces to breadth-first-search with equal-cost-paths.

You can also do a sort of meet-in-the-middle (known as a bidirectional search), starting a search from both ends.

Any algorithm for detecting connected-components will work here as well (again, these essentially using one of the search algorithms and adding connected nodes to some collection). However, you can perhaps use the some sort of disjoint-set-data-structure to keep track of different components as you add "lines" into the graph, and thus quickly test if the component of $A$ is the same as $B$. See also: connected-component labeling, and partition refinement.

If your nodes have a special structure, you might be able to take advantage of it. For example, if you are thinking of nodes in euclidean space, you can use a spatial-index, such as a quad-tree, to speed the traversal/search by traversing whole globs of nodes in one shot when it is far from a line/obstacle. Another example would be to use A*, even if you don't care about shortest-path, it might be better than simple breadth-first/depth-first, because of the structure and heuristic you can provide (see best-first search and beam-search).

EDIT:

I thought of another formulation of the problem (which likely would use one or a combination of the above approaches): Is there an online-algorithm to keep track of components in a changing undirected graph:

  Poly-Logarithmic Deterministic Fully-Dynamic Algorithms
  for Connectivity, Minimum Spanning Tree, 2-Edge,
  and Biconnectivit (PDF).
  Near-optimal fully-dynamic graph connectivity (PDF)


Z-Specification = Routes Im trying to make an invariant for this Z schema about routes.

1) The invariant should express that each route should contain at least 20 different places. First of all i thought of doing a universal quantification such as:

∀x : ran routes • ( #x>20 ∧ x ≠ x')

However i'm really not sure if thats correct that implying 20 different places.

If you say

$\forall x, x': ran\  routes . x<>x'$

You're only saying that the sequences are different.  For example

$<London, Berlin, Paris>$ would be different to $<London, Paris, Berlin>$

Instead, you need two quantifiers

$\forall x: ran\  routes . \#x>20$

and

$\forall p,p': Place • p \in ran\ (ran\ routes) \land p' \in ran\ (ran\ routes)  \implies p<>p'$

One for the length as you had and one for the condition that all elements must be unique.  Note the double $ran$ expression since a sequence is defined as a function between its indexes and its values (the range).


Given N positive integers are they the integers 1-N : What is the relationship between this problem and NP? Here’s the decision problem:
Suppose I have N positive integers encoded in base-2 (as oppose to unary)
Are these integers precisely the integers 1-N in some order?
This is related to the Hamiltonian path problem which is NP-complete
Given a graph with N vertices you can nondeterministically walk a path of length N
If you could decide whether or not the sequence is precisely the integers 1-N in some order then you could decide whether or not the path is Hamiltonian
Hence the decision problem is related to the Hamiltonian path problem
What then is the relationship to NP?
Is it NP hard?
Is it NP complete?

Recognizing that a path is a Hamiltonian path is easy. Finding one in the first place may be hard (the number of candidates is large).
The defining property of problems in NP is that verifying a solution is "easy" (in P). Your problem is one part of verifying a solution of a Hamiltonian path problem. (You also have to verify that the path is a subgraph of the input graph.)


Task Dependency/Combinatorics here is a competitive programming question:

You have a number of chores to do. You can only do one chore at a time and some of them depend on others.
Suppose you have four tasks to complete. For convenience, we assume the
tasks are numbered from 1 to 4. Suppose that task 4 depends on both task 2 and task
3, and task 2 depends on task 1. One possible sequence in which we can complete the
given tasks is [3,1,2,4] - in this sequence, no task is attempted before any of the other
tasks that it depends on. The sequence [3,2,1,4] would not be allowed because task
2 depends on task 1 but task 2 is scheduled before task 1. In this example, you can
check that there exactly three possible sequences compatible with the dependencies:
[3,1,2,4], [1,2,3,4] and [1,3,2,4].
In each of the cases below, you have N tasks numbered 1 to N with some dependencies
between the tasks. You have to calculate the number of ways you can reorder all N
tasks into a sequence that does not violate any dependencies.

[Task, Dependency(s)] : [1, NA], [2,1], [3,2], [4,1], [5,4], [6, 3 and 5], [7,6], [8,7], [9,6], [10, 8 and 9].

I inferred the following:

Any sequence will always start with 1, since it has no dependencies.
6 will always be in the 6th position of any sequence.
10 will always be at the last position.

Then, by trial and error, and listing all possibilities for the two separate parts of the sequence (1 _ _ _ _ 6 and 6 _ _ _ 10), I got 6x3 = 18 possibilities. However, for a larger set of data, these deductions would not be easy. What is the way to calculate this logically and find the number of possibilities, and how can this be integrated into a program?

(I have tried to represent the question as clearly as possible, but you can visit this link to view the question (Q. No 4): http://www.iarcs.org.in/inoi/2013/zio2013/zio2013-qpaper.pdf)

I am a high school student preparing for a programming competition, and I haven't taken many courses on algorithm design, so this might be a trivial question - please excuse me!

It is a good question, certainly not trivial.

This problem is essentially counting the number of topological orderings. A topological ordering/sort is basically a valid ordering of completing the tasks in a dependency graph.

According to the link that @AndrásSalamon put into his comment, it is #P-complete: this means it is very hard to actually compute for a large number of tasks and dependencies.

They are expecting you to write a program that does it for just the small number of tasks that they give you. You probably need to do brute-force; i.e. try all possible orders, check if it is valid, and count them.

Alternatively, some smart variation of brute force, such as enumerating all possible topological orderings, and counting them.

Frequently this is the type of question asked by a competition:

An impossibly difficult question if extended to large input size,
Therefore, some sort of brute-force must be used,
But a smart variation of brute-force,
That can depend on the specific characteristics and limitations of the input they give you; if you don't take advantage of these limitations, and/or if you don't figure out the variation they want you to do, then your program will over-run its time limits.

You can also take a look at On Computing the Number of Topological Orderings of a Directed Acyclic Graph. To run this, you would make a dependency graph of the input tasks, then count the topological orderings using the algorithm(s) in this paper. I am not sure if this would finish in time on the input data you have; but one way to know would be to try it.


Kleene star differences We have languages $A= \{a\}$ and $B = \{b\}$. If we consider $(A\cup B)^*$, where ${}^*$ means Kleene star, we have a set of words like $\{\lambda, a,b,aa,ab,aaa,\dots\}$, where $\lambda$ is the empty word. Another example we do is $A^*(BA^*)^*$. If we concatenate two languages, $\lambda$ will not be in the set, but the Kleene star adds the $\lambda$. Question is, is this set same as the set with union so $\{\lambda,a,b,aa,ab,aaa,\dots\}$ or is the set for the second example $\{a,b,aa,ab,aaa,\dots\}$, in which case the langauages would not be equal. My opinion is that concatenation is the last operation so sets are not equal but I'm not sure.

Unless parentheses say otherwise, the customary precedence is ${}^*$ (like exponentiation), then concatenation (like multiplication), then union (like addition).

Your second example is the concatenation of starred expressions, so it does contain the empty string.


Question Regarding ECLOSURE in ε-NFAs I have a small question regarding the ECLOSURE of a certain state in an ε-NFA.

If we have a transition that has both a and ε transitions, is the ECLOSURE affected?

Also is there any rule that in ECLOSURE we should include the states that are accessible only from transitions containing ε?

The $\epsilon$-closure of a state $p$ is the set of all states, including $p$ itself, that are reachable by only by a chain of consecutive $\epsilon$-moves. Transitions on other inputs are not considered when computing $\epsilon$-closure$(p)$. They come in to play in the next step, when you compute the transition function for the equivalent NFA without $\epsilon$-moves.


Polynomial time optimization problems belong to which complexity class? I know that $\mathsf{P}$ class is only defined for decision problems. Therefore, a problem like "Does there exist an $(s,t)$ path of length $k$ in the graph $G$?" is in $\mathsf{P}$. One can first find the shortest path from $s$ to $t$ in polynomial time and check if it is smaller than $k$ or not.
Now, consider the optimization version of this problem that we popularly call the shortest path problem: "Find a shortest $(s,t)$ path in the graph $G$".
Since this is not a decision problem, is it wrong to say that "shortest path problem is in $\mathsf{P}$"? If so, in which complexity class does it belong to?

Take a look at the FP complexity class.
Technically speaking, it is wrong. However, usually people don't make a huge difference between the two. Its usually clear from the context whether the problem is a decision or a search problem, hence its clear whether it should be in $P$ or $FP$.
So, writing that "Finding the shortest $(s,t)$ path in the graph $G$, is a $P$ problem" would actually mean: "Finding the shortest $(s,t)$ path in the graph $G$, is an $FP$ problem" (since the context is clear)


In a 32-bit floating number with normalized mantissa and excess-64 exponent base 16, the number $16^{-65}$ denotes In a 32-bit floating number with normalized mantissa and excess-64 exponent base 16, the number $16^{-65}$ denotes

Floating point overflow.
Negative floating point overflow.
All 0's in the exponent and mantissa fields.
The minimum representable positive number .

I think that minimum representable number should be $1 \times 16^{-63}$
because the minimum mantissa should be 1 and and the possible exponent range in bias form is from 1 to 127 (where 1 corresponds to most negative exponent i.e. -63, and 127 corresponds to most positive exponent i.e. 63)

So according to me, the answer is: A positive floating point underflow.
Please correct me if i am wrong. The IEEE-754 representation is confusing me.

Someone also told me something along the lines of " the mantissa part is always taken as 0.M if the base is something other than 2". However I don't have any reference for this statement.

The format you are using is not IEEE-754 but an IBM FP format.  The mantissa is fractional, so the binary representation 0001_0000_0000_0000_0000_0000 means 0.1 (base 16).  With a zero value in the exponent field, the exponent would be -64.  So you can see that $16^{-65}$ would be the smallest normalized positive value ($1 * 16^{-1} * 16^{-64}$)


How to prove the NP-completeness of MOD-PARTITION MOD-PARTITION: Given a set of integers $A={a_1,...,a_n}$, their weights $w = \{w_1, w_2, \dots, w_n\}$ and the number $k$, does there exist a subset $X$ of $A$ such that: $(\sum_{x \in X} w(x) * x) \mod k \; = \; (\sum_{a \in A \setminus X} w(a) * a) \mod k$?

Can some please provide some idea on how to prove the NP-Completeness of this problem? I saw the proof of the set-partition problem (using a reduction from subset-sum) and I suppose, that this proof maybe will be some little modification of it.

Showing that this your problem is in NP is easy.

To show that your problem is NP-hard, reduce from PARTITION. The reduction simply chooses a large enough modulus $k$. Details left to you.


Reduce ATM to REGULAR_TM Consider $\mathsf{REGULAR_{TM}} = \{\langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is a regular language}\}$.
Let $S$ be the following algorithm, which solves $\mathsf{A_{TM}}$: “On input $\langle M, w \rangle$, where $M$ is a TM and $w$ is a string:

Construct the following TM $M_2$:
$M_2$ = “On input $x$:

If $x$ has the form $0^n 1^n$, accept.
If $x$ does not have this form, run $M$ on input $w$ and accept if $M$ accepts $w$.”

Run $R$ (a machine solving $\mathsf{REGULAR_{TM}}$) on input $\langle M_2 \rangle$.

If $R$ accepts, accept; if $R$ rejects, reject.”

I am trying to understand this proof, but I am really confused with step 1 of $M_2$.
The book says "$M_2$ works by automatically accepting all strings in $\{0^n1^n \mid n ≥ 0\}$. In
addition, if $M$ accepts $w$, $M_2$ accepts all other strings."
But I don't understand how could $M_2$ accept all strings. If $x$ is not of the form $0^n 1^n$ and $M$ does not accept $$, wouldn't $L( M_2 )$ be empty?. Or can we assume there are many different $x$ as an input to $M_2$?

First, note that $M$ and $w$ in $M_2$ are fixed. So whatever is the input, $M$ always accepts or rejects $w$. Second, note that $M_2$ is not built to run.

Then:

You want to map $<M,w>$ to a regular language $L$ if and only if $M$ accepts $w$. Fix $L$, in that case you choose $\Sigma^*$. However, if $M$ rejects $w$ you don't want $L$ regular (otherwise $R$ will accepts), so you choose $L'\subset L$ such that $L' = \{0^n1^n\}$ which is not regular.

Now you have two cases:

1) if $M$ rejects $w$, then $M_2$ will accepts only the strings of the form $0^n1^n$, then $R$ will reject.

2) if $M$ accepts $w$, then $M_2$ will accepts all  the strings of the form $0^n1^n$ and all other strings in $\Sigma^*-0^n1^n$, so $R$ will accept.

However in poor words, it consists to map an "yes istance" of $<M,w>$ to a single "yes instance" of $L$. Let me do an example:

You want to prove that $L=\{M |\ if\ M\ accepts\ w\ then\ M\ accepts\ flip(w) \}$, where $flip(w)$ is the bitwise of all the string $w$ (For example if $w$ = $100$ then $flip(w) = 011$.), is undecidable with a reduction from $A_{tm}$.

Suppose $L$ is decidable, then exists a $TM$ $R$ that decides $L$. So we can build a new $TM$  $S$ that decides $A_{tm}$.

We will doing something like this:

  $S$ on input $<M,w>$: "build a new $TM$ where $M$ and $w$ are constants. Call it $N_{<M,w>}$, then run $R$ on input $N_{<M,w>}$ and do what $R$ does."

Inside $N_{<M,w>}$ we have our reduction.
Take in mind we want this:

  $M$ accepts $w$ if and only if $R$ accepts $L(N_{<M,w>})$

First, we fix $L(N_{<M,w>})$ = $\{100,011\}$ (This is just an "yes instance" of $L(N_{<M,w>})$

Now our $N_{<M,w>}$

  $N_{<M,w>}$ on input $x$:

  if $x$ = $100$ then accepts

  else if $x$=011 then run $M$ on $w$ and do what $M$ does.

Then "run" $R$ on $N_{<M,w>}$ and $S$ will accept if $R$ does:

if $M$ rejects $w$, the only string could be accepted by $N_{<M,w>}$ is $100$ then both $R$ and $S$ will reject.

Otherwise if $M$ accepts $w$, $N_{<M,w>}$ will accept both $100$ and $011$ then both $R$ and $S$ will accept.

So $S$ can decide $A_{TM}$ which is impossible, the "error" was to suppose the existance of $R$.


Finding the lightest simple path in trees with integer weights A tree with integer weights (positive, negative or zero) is given. We want to design an efficient algorithm for finding a simple path with lightest weight in this tree. That is, we look for shortest paths where the length of the path is equal to sum of all edges weights.

I know that in a tree there is only one simple path between every pair of nodes.
So, even if you try every pair of nodes finding the path between then, you would have an $O(n^3)$ algorithm.

A better way is to find for every node the cost to every other node in a single visit. This lowers the algorithm to $O(n^2)$.

Is there any algorithm that runs in linear time?

Order the tree, so we can speak about a node and its subtrees. Now evaluate the tree recursively. In each node keep track of two values: (1) the value of the optimal path below the node (starting and ending somewhere below in the subtrees), and (2) the value of the optimal path below that additionally ends in the node itself.


Average branching factor of an undirected graph I'm trying to determine, given an unweighted undirected graph, the maximum number of leaves of any travelling of the graph, which means, the maximum number of leaves among all traversals of every spanning tree of the graph.

I know that, given a tree of $n$ nodes, an average branching factor $b_f$ and $n_l$ leaf nodes, these three variables are related as follow:

$$b_f = \frac{e}{n-n_l} \Rightarrow n_l = n - \frac{e}{b_f}$$

where $e = n - 1$ (the number of edges).

However, if instead of an undirected tree you have an undirected graph of $n$ nodes and $e = n - 1 + k$ edges (or with $k$ fundamental cycles), different traversals of the graph would give you different spanning trees, depending on which one of those $k$ edges are the one being ignored from the graph.

Is there any known property of graph's spanning trees that can offer an upper bound on the number of resulting leaves nodes of any traversal?

My best approximation so far is that, the maximum number of leaves must be bounded by $$n_l <= |\{n_{e^1}\}| + 2k$$ where $|\{n_{e^1}\}|$ is the number of nodes of the graph with degree 1, and $k = e - n + 1$.

That's a worst case scenario where there exists $k$ edges in the graph connecting nodes with degree 2 each, whose removal doesn't create new connected componentes, because removing them will give $2k$ nodes with degree 1 each, and thus $+ 2k$ leaves. If $k$ is very low that can be an acceptable good approximation, but the biggest the connectivity of the graph, the worst the significance of the approximation.

If someone could give a better approximation based on the average degree of the graph or something similar that can be calculated on a first traversal would be appreciated.

Just to make it clear, the problem of finding a spanning tree with a maximum number of leaves is NP-hard. There's a simple 2-approximation algorithm due to Solis-Oba [1] which looks implementable with reasonable effort. In fact, I don't think anything better is known. There are other algorithmic approaches as well (e.g., FPT algorithms), but I'm not sure if these are that practical.

For a good overview of spanning trees in general, you can have a look at the survey of Ozeki and Yamashita [2]. Particularly, Section 6.1 is on spanning trees with many leaves and gives some combinatorial results.

[1] Solis-Oba, Roberto. "2-approximation algorithm for finding a spanning tree with maximum number of leaves." European Symposium on Algorithms. Springer, Berlin, Heidelberg, 1998.

[2] Ozeki, Kenta, and Tomoki Yamashita. "Spanning trees: A survey." Graphs and Combinatorics 27.1 (2011): 1-26.


Best introductory "algorithms"/"more than just coding" comp sci book? I've been programming in languages (C/C++/Ruby/Java/HTML) for some time now and am currently entering my senior year of high school. I'm taking AP Comp Sci, which uses Java, but want to have a better grasp of some of the more "math-y" concepts in computer science, like hashes/algorithms/etc. For someone who has done basic object oriented programming but doesn't know any of the algorithmic aspects of computer science (And wants to know them before he goes off to college), what books would you recommend that cover algorithms and the more mathematical stuff in a way that's easy for your rudimentary programmer to understand?

Some examples I've heard given are "Introduction to Algorithms" and "Structure and Interpretation of Computer Programs"; I was going to go with Introduction to Algorithms but it's around 80 dollars new, and I'm not sure if SICP has any of the algorithmic math I want to pursue. Haha, I guess all I'm asking for is personal opinions from people that have studied algorithm books and can give honest personal opinions.

Any and all feedback is appreciated; Thank you!

-Neil

Check out From Mathematics to General Programming by Alexander Stepanov and Daniel E. Rose.

Beginning with the basics of number theory you progress up to dealing with content that is typically covered in a 3/400 level abstract algebra course (depending on the institution).


Are these examples of unification problems? I have been studying unification, especially nominal unification (paper) gets my attention.
I read the theory and examples. But I am wondering that what kind of problems occur in unifications.
For examples, The following examples are from nominal unification paper. (I write distinct bound variables, so easier to see the solutions )

(1) $\lambda a. \lambda b. (X  \, b) = \lambda c. \lambda d. (d \,X) $

(2) $\lambda a. \lambda b. (X \, b) = \lambda c. \lambda d. (d \, Y) $

(3) $\lambda a. \lambda b. (b  \, X) = \lambda c. \lambda d. (d \, Y) $

I observed that each variable ($X$ or $Y$) occurs only once on one side of equations.
Should it be always that way?
Can I write the following

(4) $\lambda a. \lambda b. (X  \, X) = \lambda c. \lambda d. (d \,X) $

(5) $\lambda a. \lambda b. (Y  \, X) = \lambda c. \lambda d. (d \,X) $

(6) $\lambda a. \lambda b. (X  \, X) = \lambda c. \lambda d. (X \,X) $

and are these possible unification problems?

I read many sources, but and all presented unification problems with variables only have once occurrences on one side of equations.
I tried to find more examples, but could not find anything different.

I know the unification problems arise from logic programming. And so far, I did not see any logic programs which puts $X$ twice in a term.

Anyway, hoping someone to clarify these points.

Thanks in advance!

Yes, the variables can occur more than once in a term.  Either way you end up with a system of equations.  For plain unification, you can always have the unification variables be distinct and then add equations to unify them separately.  That is, you can turn $\mathtt{p}(X,X) = \mathtt{q}(\mathtt{a},\mathtt{b})$ into $\mathtt{p}(X,Y) = \mathtt{q}(\mathtt{a},\mathtt{b})$ and $X = Y$.

Comparing predicates with duplicate variables comes up all the time in Prolog.  For example, one of the most iconic Prolog programs is list append, usually written as:

append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

If you want to be very pedantic and say these programs don't illustrate terms with duplicate variables, then you can consider another iconic Prolog technique: difference lists. The most general difference list representation of a list $[1,2,3]$ is $[1,2,3|X]\setminus X$.


What is the expansion of the regular expression $(a^*b^*)^*$ Consider the regular expression $(a^*b^*)^*$

Does this mean that there are zero or more occurences of the term $(a^*b^*)$ before the term is expanded or that there are zero of more occurences of the term $(a^*b^*)$ after the term itself has been expanded?

Here is an example of what I'm try to say

zero or more occurences of $(a^*b^*)$ BEFORE expanding $(a^*b^*)$
$(a^*b^*)^* = a^*b^*a^*b^*a^*b^* = aababbab$

or

Zero or more occurences of $(a^*b^*)$ AFTER expanding $(a^*b^*)$
$(a^*b^*)^* = (aab)^* = aabaabaab$

Expand the outer starred expression first and then expand the terms. If $r$ is a regular expression, then $r^*$ denotes the language consisting of zero or more copies of $r$, concatenated together, so $r^*$ could take the form $\epsilon$ (the empty string, resulting from no copies of $r$) or $r$ or $rr$ or $rrr$, and so on.

In your example, with $r=a^*b^*$, then $r$ denotes all the strings consisting of zero or more $a$'s, followed by zero or more $b$'s, and so $(a^*b^*)^*$ will denote all possible concatenations of terms $(a^*b^*)$. For example, one possible concatenation would be $(a^*b^*)(a^*b^*)(a^*b^*)$ and then after expanding each term, we might have $(abb)(aab)(bbb)=aabaabbbb$.

By choosing to expand the inner term and then concatenating the results you will likely miss the general form. If, for example, we chose a particular string in $r$ and then concatenated them, we might replace $r=a^*b^*$ with $abb$. Then, if we concatenated just those terms three times, we'd have $(abb)(abb)(abb)$. While this is in the language $(a^*b^*)^*$, it is of a special form that doesn't capture the full generality of strings in the language.

While it's not directly related to the question you asked, it's worth noting that $(a^*b^*)^*=(a\mid b)^*$ (some authors would write $(a\mid b)$ as $(a\cup b)$ or $(a+ b)$). In other words, $(a^*b^*)^*$ denotes the language consisting of all possible strings over $a$ and $b$. Can you see why?


Forming red-black tree from binary tree conserving in-order traversal What is the optimal algorithm (in terms of time complexity) that can transform any binary tree to a red-black tree, with the requirement that in-order traversal must yield the same values for the new tree?

Is iterative insertion of the original nodes sufficient, or can it be done with better complexity?

Iterative insertion gives a time complexity of $O(n \log n)$ for $n$ keys, but it's possible to do it in linear time.

The input tree gives you the in-order traversal, so you can begin by traversing the input tree and storing the keys in an array. Now, notice that if $n = 2^m - 1$ for some $m$, it's actually trivial to create a new binary tree which is perfectly balanced: split the array in half, choose the middle element as the root, and recursively build the left and right children from the two halves of the array. To make it a red-black tree, you have to assign colors. For a perfectly balanced tree, this is simple: you can actually make every node black.

But how do you handle the general case, when $n$ is not one less than a power of 2? You won't be able to make a perfectly balanced tree, but you can get pretty darn close!

This smells like a homework assignment, so I'll leave the specifics of assigning colors to you, but here's something to get started. Notice that, when you split the array of keys in half, the two halves have either exactly the same number of keys, or they differ by one. When they have exactly the same number of keys, assigning colors is easy. When they don't, you might need to use some red nodes...


Why is pure literal elimination absent in DPLL-based algorithms like Chaff? I'm looking into various SAT-solvers and trying to understand how they work and why they are designed in certain ways. (But I'm not in a university at the moment and I do not know anyone who is a professor. So I'm posting here hoping that someone can help me out. I'd really appreciate.)

In Chaff, BCP (Boolean Constraint Propagation) is implemented differently from the original DPLL: it does it by watching two literals at a time (a technique slightly different from one initially suggested in SATO: An Efficient Propositional Prover) according to the 2001 paper, Chaff: Engineering an Efficient SAT Solver. There is, however, no mention of pure literal elimination in this paper.

In The Complexity of Pure Literal Elimination, Jan Johannsen wrote

  The current best implementations of DLL-type SAT solvers, like Chaff
  or BerkMin sacrifice this heuristic in order to gain efficiency in unit
  propagation.

where "this heuristic" is referring to pure literal elimination. My understanding of what pure literal elimination does is that it

searches for all single-polar (or pure) literals
assigns a boolean value to them such that each yields True
in which case we can now delete all the clauses containing them

Here is my question:

How is the sacrifice necessary? Is there a good reason why pure literal elimination is absent in DPLL-based algorithms like Chaff? Can't we just do pure literal elimination in each decision level (or at least do it at the start before branching)?

Solvers that use the two-watched-literals algorithm to implement unit propagation don't keep track of which clauses have been deleted (by implication) to produce the subformula implied by the current partial assignment.  By not tracking this information, solvers can avoid touching most of the clauses during assignments and avoid touching any of the clauses during backtracking.  Figuring out which variables are currently pure in the formula means losing these substantial efficiency gains.  Meanwhile there's nothing to suggest that pure literal removal will produce conflicts or satisfying assignments early enough to make up for the heavy tracking cost.

Solvers that do formula simplification before starting the search procedure will generally include pure literal removal since it is quite cheap to do as a preprocessing step and could potentially remove many clauses.


Time complexity of transforming one string to another Here is the problem:

Given a dictionary $D$ and two strings $s$ and $t$, write a program to determine if $s$ produces $t$. If it does produce $t$, output the length of of the shortest production sequence, otherwise, output $-1$.

Example: $D$ = [bat, cot, dog, dag, dot, cat], $s$ = cat, $t$ = dog, the shortest production sequence would be [cat, cot, dot, dog], giving us an output of four.

Here is the algorithm (Breadth First Search):

private static class StringWithDistance {
    public String candidateString;
    public Integer distance;

    public StringWithDistance(String candidateString, Integer distance) {
    this.candateString = candidateString;
    this.distance = distance;
    }
}

public static int transformString(Set<String> D, String s, String t) {
    Set<String> visited = new HashSet<String>(D);
    Queue<StringWithDistance> q = new ArrayDequeu<>();
    visited.remove(s) // mark as visited by erasing it
    q.add(new StringWithDistance(s, 0);

    stringWithDistance f;
    while ((f = q.poll()) != null) {
        if (f.candidateString.equals(t)) {
            return f.distance;
        }

        for (int i = 0; i < str.length(); ++i) {
            String strStart = i == 0 ? "" : str.substring(0, i);
            String strEnd = i + 1 < str.length() ? str.substring(i + 1) : "";
            for (int c = 0; c < 26; ++c) {
               String modStr = strStart + (char)('a' + c) + strEnd;
               if (visited.contains(modStr)) {
                   visited.remove(modStr);
                   q.add(new StringWithDistance(f, f.distance + 1);
               }
            }
        }
    }

I'm having a hard time understanding why this algorithm is $O(n^2)$. I know that the time complexity of processing the vertices/words is $O(n)$, but based on the text I'm reading, processing the edges in the worst case would be $O(n^2)$, so we would have $O(n + n^2)$, giving us $O(n^2)$.

I just can't see how that is taking place. The second loop is a constant (right?), it doesn't change with the size of $n$, so I don't think that is a part of the calculation for the run time.

Any help would be greatly appreciated.

As told by OP, the problem and its the solution come from Elements of Programming Interviews in Java by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.

Here is the excerpt of the book that analyzes the time-complexity of the solution.

  The number of vertices is the number d of words in the dictionary. The number of edges is, in the worst-case, $O(d^2)$. The time complexity is that of BFS, namely $O(d + d^2) = O(d^2)$. If the string length $n$ is less than $d$ then the maximum number of edges out of a vertex is $O(n)$, implying an $O(nd)$ bound.

The above analysis in the book is correct. Please note "word" and "string" are used interchangeably here.

Here is OP's analysis, with the only modification that I use $d$ to denote the number of words so as to be consistent with the book.

  The second loop is a constant (right?), it doesn't change with the size of $d$, so I don't think that is a part of the calculation for the run time.

OP's analysis is not wrong, either, if we assume that the length of the strings in the dictionary is bounded by a constant. This assumption is not unreasonable since it conforms to our ordinary experience about words in a normal dictionary. In fact, OP's analysis has been included in the book as well! It is the very last statement of the excerpt above.

Is there a logical inconsistency between the bounds $O(d^2)$ and $O(nd)$? No, since they apply to different situations with different assumptions. For example, in the worst case where every string differ in exactly one character with every other string, if we let $d$ go to infinity, then the maximal string length $n$ will goes to infinity as well. That is, "The second loop" does "change with the size of $d$"! Those strings are very unlikely to be words in our ordinary dictionary because of their huge lengths, of course.

In fact, in all cases, $d \leq 26n$. So $O(d^2)$ implies $O(nd)$.


Elementary proof that Bool is a Set The type Bool, as in the datatype with just two point constructors true false : Bool and no higher-dimensional constructors, has decidable equality which is easy to prove directly, e.g. via a type family that maps true to Unit and false to Void. Then we can apply Hedberg's theorem to show that Bool is a Set.

What is a direct, elementary proof of IsSet Bool that doesn't go via Hedberg's theorem?

Here is the encode-decode method that L. Garde suggests (in cubical Agda):

{-# OPTIONS --cubical --safe --postfix-projections #-}

module Hmm where

open import Cubical.Core.Everything

open import Cubical.Foundations.Prelude
open import Cubical.Foundations.Isomorphism

open import Cubical.Data.Empty
open import Cubical.Data.Unit

data ℕ₂ : Type₀ where
  0₂ 1₂ : ℕ₂

Code : ℕ₂ → ℕ₂ → Type₀
Code 0₂ 0₂ = Unit
Code 1₂ 1₂ = Unit
Code m  n  = ⊥

Crefl : ∀{m} → Code m m
Crefl {0₂} = tt
Crefl {1₂} = tt

decode : ∀ m n → Code m n → m ≡ n
decode 0₂ 0₂ c = refl
decode 1₂ 1₂ c = refl

encode : ∀ m n → m ≡ n → Code m n
encode m n p = transport (λ i → Code m (p i)) Crefl

decode-encode : ∀ m n p → decode m n (encode m n p) ≡ p
decode-encode m n p
  = J (λ z q → decode m z (encode m z q) ≡ q) (lemma m) p
  where
  lemma : ∀ m → decode m m (encode m m refl) ≡ refl
  lemma 0₂ = refl
  lemma 1₂ = refl

encode-decode : ∀ m n c → encode m n (decode m n c) ≡ c
encode-decode 0₂ 0₂ c = refl
encode-decode 1₂ 1₂ c = refl

Cprop : ∀ m n → isProp (Code m n)
Cprop 0₂ 0₂ = isPropUnit
Cprop 1₂ 1₂ = isPropUnit

ℕ₂set : isSet ℕ₂
ℕ₂set m n = transport (λ i → isProp (p i)) (Cprop m n)
  where
  p : Code m n ≡ (m ≡ n)
  p = isoToPath (iso (decode m n) (encode m n)
                   (decode-encode m n) (encode-decode m n))


Halting problem with Proof of The Immerman-Szelepcenyi Theorem (knowledge of the theorem might not be necessary to clear my doubt) So, I was reading this pdf on complexity theory. On page 18 pf pdf (Page 12 of book) The Immerman-Szelepcsenyi Theorem is mentioned with proof. The following lines are from the book :

  The idea is to cycle through all possible configurations $\sigma$ of $M$, for each one checking whether it is a final configuration that is reachable from the initial configuration by a computation of $M$. In case no such accepting configuration is found we know $x\notin A$ so we let $\overline M$ accept $x$.

My question here that the machine $M$ may not halt for a string $x\notin A$. Then the logic of "cycle through all possible configurations" won't make any sense. What am I missing here?

On a side note is this book too high level for me? (I am graduate in Computer Science) Getting stuck at page 12 is not a good sign right?

As the proof (sketch) itself notes:

  Note that on a given input $x$ of length $n$ there are $2^{f(n)}$ possible configurations.

This means there is only a finite space of configurations for a machine that operates in less than $f(n)$ amount of space!

Intuitively, if you have an array [0,1,0,...,] of length $n$, then all possible combinations of configurations of that array is $2^n$, and so a machine which could only modify an array of bits of size at most $n$ will either halt in that time, or end up in a loop with exactly the same state as previously, and this is easy to decide.

If you allow arbitrary amounts of space then as you note, it is undecidable whether or not a state is reachable or not.

It's hard to say whether a given piece of work is "too high level" for someone or not. To paraphrase Euclid, there is no "royal road" to theoretical computer science, so you should expect to have at least some difficulty working through technical material.

As Paul Halmos suggests: "Don't just read it, fight it!". This suggests that difficulty in mathematical reading is rather widespread (I certainly experience it sharply as well).


Amortised analysis of binary heap insert and delete-min I'm trying to figure out how to do amortised analysis of heap insert and heap delete-min using potential function.

We can assume, that insert is O(logn) and delete-min is O(logn) too.

The goal is to prove, that amortised price of insert is O(logn) and amortised price of delete-min is O(1).

Can't figure out how to create a potential function.

POT.F = ?
INSERT c = logn + (something from 0 to xlogn)
DELETE-MIN c = logn + (something like -logn)

Could you guys help me? I've figure out so far that difference between potentials should be from 0 to xlogn so INSERT price would be logn and for DELETE-MIN, difference should be somewhere abour -logn to get constant price.

First, for a bit of clarifying terminology:  rather than proving an amortized insertion cost of $O(\lg n)$ and an amortized deletion cost of $O(1)$, you are using those amortized costs to prove something about the total cost of a sequence of insertions and deletions, starting with an empty heap.  This might be a subtle distinction, but it is fairly important (at least to me).  If you allow yourself to start from a non-empty heap, you would also need to allow yourself to start with a $\Theta(n \lg n)$ potential, or else the deletion amortized cost won't work.  Or, if you were to add in an operation for the worst-case linear time build-heap operation, you would also need for that linear time operation to add $\Theta(n \lg n)$ to the potential function.

To use your desired amortized runtimes, each insertion has to prepay for a deletion to come later.  So, for instance, when inserting into a heap of size $n$, you can pay for the actual insertion $O(\lg n)$, but your amortized cost will pay that plus an additional $O(\lg n)$ for the worst-case runtime of deleting from a heap of size $n+1$.  Now, every time you delete from a non-empty heap?  That deletion's actual cost has already been prepayed by a previous insertion's amortized cost.  It costs 0 (amortized) to delete.  The only deletions that you still need to pay for are the ones from an empty heap, for when your deletions outnumber prior insertions, and those cost $O(1)$.

While these bounds are fine to use for a proof of efficiency for a sequence of insertions and deletions, they are slightly odd, in that in real life, the deletions generally take expected $\Theta(\lg n)$ time, and insertions take expected $\Theta(1)$ time, for some reasonable definitions of operating on a random heap of size $n$.

While I have presented this in terms of "prepaying" (or the accounting method), in this case, just writing it down as a more formal equation directly transforms it into the potential function method.  You will be able to prove that the potential of a heap with $n$ elements is at least $\sum_{i=1}^n f(i)$ where $f(i)$ is the worst-case price to delete the min item from a heap if $i$ elements.  You already start your question with a given $O(\lg i)$ bound on $f(i)$.


Is there a name for this kind of graph? Is there a name for the DAG obtained from a directed graph by collapsing together the strongly connected components?

The graph you describe is called the condensation of the original graph.


Given a non-deterministic Mealy machine $M$, if $L$ is regular, is $M(L)$ regular? Consider a nondeterministic Mealy machine, $M$, defined as follows:
$M = (Q, \Sigma, \Delta, \delta, \tau, q_0)$ where

$Q$ is a finite set of states
$\Sigma$ is an input alphabet
$\Delta$ is an output alphabet
$\delta : Q \times \Sigma_{\varepsilon} \to \mathcal{P}(Q)$ is the transition function
$\tau : Q \times \Sigma_{\varepsilon} \to \mathcal{P}(\Delta)$ is the output function
$q_0 \in Q$ is the start state

Let $M(x)$ for $x \in \Sigma^*$ denote the set of all strings that $M$ could output on input $x$.  Note that $M$ could fail to process the entirety of its input, and thus a string is output only if $M$ processes all of its input.  Also, we define, for $L \subset \Sigma^*$, $M(L) = \bigcup\limits_{w \in L} M(w)$.  Given this, if $L$ is regular, does it follow that $M(L)$ is regular?

I've attempted to solve this by first showing that for every non-deterministic Mealy machine, there exists an equivalent deterministic Mealy machine.  By "equivalent" I mean that the input-output behavior of the two is identical.  The problem, however, is that the output function for a deterministic Mealy machine can only output a single character at a time.  How, then, could I get the simulating deterministic Mealy machine to output a set of strings?

There is no reason to convert the Mealy machine to a deterministic one – indeed, this is not always possible. Suppose that the input alphabet is unary but the output is binary. A deterministic machine has one output of each length, but a non-deterministic machine can have many.

Instead, the idea is to construct an NFA which keeps track of both the Mealy machine $M$ and a machine $T$ accepting $L$. Denote by $w$ the (unknown) word in $L$ on which we run $M$. At each point in time we guess the next symbol in $w$ and transition in $T$, guess a corresponding transition in $M$, and "accept" the symbol output by the $M$-transition (if any). The accepting states of the NFA are those in which $T$ is at an accepting state.

I'll let you go over the details.


Reduce set partition search to decision? I'm a little lost and don't know how to approach this problem.

  Show the partition search problem can be poly-time reduced to the
  partition decision problem, the partition decision problem takes an
  input set of numbers and returns true if there is a subset of the
  initial set that sums up to half the total sum of the initial set.

With problems like ham-path search, clique search and SAT search, the key was to build the solution one piece at a time using the results from the decision "oracle". But I need to know how to approach this problem.

Initially, I thought about removing elements from the set while verifying if there is a partition in the remaining set, which led me nowhere. Now I'm wondering if adding elements to the initial set would have any results.
I noticed if the initial set has a partition, adding elements to the set would then only have a partition if the added element is even, but I don't see how this can generate a subset of the original set that satisfies partition search.
Am I going off the wrong track? Any pointers would be appreciated.

The standard approach works fine to reduce the problem size.  Given a "true" instance, $n$ elements which can be partitioned, you want to be able to reduce it to a smaller sized problem.  Grab any 2 elements, and combine them into one (having their sum as its size), and now you have an instance with $n-1$ elements.  If the answer to that instance is yes, great.  If it is no?  They must go into different partitions, which (effectively) adds their difference to whichever partition got the larger one.  Get rid of both, but add the difference as a new element.  In either case, you have $n-1$ elements in your new instance.


Suggest structure for query $sumRange(low,high)$ which returns sum of elements whose key $k$ satisfies $low \le k \le high$ in $\Theta(\log n)$ time Suggest a data structure to perform a query $sumRange(low,high)$ which will return the sum of the elements whose key $k$ satisfies $low \le k \le high$ in $\Theta(\log n)$ time.

I found the original problem here (although it's for counting) but it runs in $\Theta(n)$ time. However, I think with additional data structures and/or improvements this can be done in $\Theta(\log n)$.

I think we need a balanced binary search tree, for example, red-black tree.

Then I thought of the following algorithm:

sumRange(low, high)
sum <- 0
temp
closestToLow <- findClosest(low)

if(low=closestToLow)
    sum += closestToLow.key

temp <- successor(closestToLow)
sum += temp.key

It will only find the low point and its successor. I guess we need a similar piece of code to find the high point. Not sure how to traverse in between though.

Prefix sums or a 1-D summed area table suffice to answer those queries in $O(1)$ time.  (Alternatively, you can augment a balanced binary search tree -- I will let you discover how.)


Distributed systems according to Lamport? I need some clarification over the following quotation of Leslie Lamport:

  A distributed system can be described as a particular sequential state machine that is implemented with a network of processors. The ability to totally order the input requests leads immediately to an algorithm to implement an arbitrary state machine by a network of processors, and hence to implement any distributed system.

I see how a distributed system can be modeled as the product of several particular sequential state machines.

I understand that by totally ordering input requests, one can duplicate a given sequential state machine over several computers, and make sure that all input requests are processed in the same order at every computer, and thus ensuring that the individual local states are coherent.

What I don't understand is how this mechanism is sufficient to implement ANY distributed system. At least it's sufficient to duplicate a sequential state machine, but isn't that a very particular case of a distributed system?

My interpretation of this quote is that if we consider the whole distributed system as a black box containing multiple local processors, then when we send input requests to this box, the whole box moves to another state even though we don't know what that next state is (particularly in non-deterministic state machines), but we are sure that there's no inconsistent interpretation within the box.

Actually input requests could be thought of as an external node that does atomic broadcast to all internal nodes (within the box). This type of broadcast ensures us that all internal nodes receive messages in the same order, so all local state machines move to their next states. If we define state of the whole system as a set of all internal local states, so whenever we receive an atomic broadcast (i.e. input request), our system's state moves to a next state depending on the order of messages that all internal nodes agree on. Hence, each different order leads us to a non-deterministic destination (the next state) in the state machine of the whole system.

Therefore, total ordering is sufficient to model a distributed state machine. However in some applications some more properties might be needed, for instance, FIFO ordering, causal ordering, etc.


Show complement of language in same complexity class? If $L$ is a binary language ($\Sigma = (0, 1)^*$) and $\overline{L}$ is the complement of $L$, the set of binary strings not in $L$.

How can I show that, if $L$ is in the complexity class $P$, then so is $\overline{L}$?

Hint: Given a polynomial time algorithm for $L$, come up with a polynomial time algorithm for $\overline{L}$.


Outputting numbers within a range that are not in a list How could you design an efficient algorithm that uses the least amount of memory space and outputs, in ascending order, the list of integers in the range 0..255 that are not in a randomly generated list of 100 integers?

The aim is to output the number of such integers, and determine if the randomly generated list of 100 integers included any repeats.

The naive approach would be to compare each number from 0 to 255 against the list of 100 integers. This would not be very efficient.

What would be a more efficient approach to solve this?

Facetious answer: all the sizes involved are constant, so a straightforward algorithm for this will run in $O(1)$.

Serious answer: with such small numbers involved, getting too elaborate may just slow you down. Simplicity is your friend.

let found be an array [0..255]
found ← [false, false, false...]

for i ← [1..100]:
    value ← A[i]
    if found[value] is true:
        there was a repeat
    found[value] ← true

for j ← [0..255]:
    if found[value] is false:
        j was not in the list

This runs in $O(n+k)$ time and $O(k)$ space (where $n$ is the number of elements in the array and $k$ is the maximum size of those elements). I don't believe it's possible to do better.


Rice's Theorem for Total Computable Functions Fix a Gödel numbering, and write $\phi_n$ for the function coded by $n$. Rice's theorem states that if $P$ is the set of partial computable functions, and $A \subseteq P$, then the decision problem

  Given $n$, does $\phi_n \in A$?

is decidable if and only if $A = \emptyset$ or $A = F$; that is, if the decision problem always has the same answer.

Now consider the set $T$ of total computable functions instead. Clearly, the problem

  Given $n$ with $\phi_n \in T$, does $\phi_n \in A$?

is no longer decidable if and only if $A \in \{\emptyset,T\}$. In fact, for recursive set $M\subseteq \mathbb N^k$, the problem is also decidable for
$$
A_M = \{\phi_n \in T \mid (\phi_n(0),\ldots,\phi_n(k-1)) \in M\}.
$$
So is it true that the problem is decidable if and only if $A$ is of the form $A_M$ as above? If not, can we give a different restriction on the form of $A$ that does give us a theorem?

Almost

The correct answer is that a property of recursive languages is r.e. if and only if it can be verified by a finite number of values (though unlike in your example the exact number of values can be unbounded, so $k$ can depend on $n$). In fact, the wikipedia page for Rice's theorem has a section on this:

  ...the analogue says that if one can effectively determine for every recursive set whether it has a certain property, then only finitely many integers determine whether a recursive set has the property.

More precisely, a property is r.e. iff there is a r.e. set $T_1$ with the prefix property (i.e.- no string in $T_1$ is a prefix of another) such that $\phi_n$ has the property iff there is some $k$ such that the sequence $\phi_n(0), ..., \phi_n(k-1)$ is in $T_1$ (we can make sense of a sequence being in a set of natural numbers by encoding this as $p_1^{\phi_n(0)}\cdot p_2^{\phi_n(0)}\cdot ...\cdot p_{k}^{\phi_n(k-1)}$ where $p_i$ is the $i$th prime). A property would be recursive iff it is r.e. and co-r.e.

This pretty much says that we can get no more information out of the index $n$ than the function $\phi_n$ itself, because any computable property must be computable only using calls to the function $\phi_n$. This may sound trivial, but it is no means obvious since a priori the input $n$ might have some extra non-syntactic information computably nestled into it.

Rice's theorem essentially states that no extra non-syntactic information about partial recursive functions can be computably nestled into their Godel encodings. As it turns out this is also equivalent to the above characterization, so the same thing holds for total functions as well. I suppose one could make this statement even stronger by generalizing to even more general classes of functions, but I do not know if this is true.


Find the maximum (longest) delay to last user in a multicast T. NP complete proof Given a un-directed weighted graph G=(V,E) where V is the set of vertices and E is the set of edges between vertices, and weights are the time delays on each link between two user. The goal is to construct a multicast tree T (that connects source node to a set of nodes say K) such that to minimize the maximum (longest) delay of the last user in the multicast tree T. The maximum (longest) delay of the multicast tree T should be less than or equal to say d. Thus it seems a an NP-Complete problem but I don't know how to prove it or reduce it. I will appreciate your kind feedback. Thank you

Refer to Shorted Path Tree (SPT)- https://en.wikipedia.org/wiki/Shortest-path_tree
It ensures that the delay from source node is always minimum for all the nodes including the maximal ones.

Based on your problem description I think it is SPT. If that's the case, it is not a $\text{NP}$-hard problem.


Uncertainty of coroutines writing to single socket A program runs in a low-spec hardware utilizes coroutines writes to a single socket but how does the socket know when the data should be sent as there could more coroutines writing given N time.
I find this problem similar to The halting problem even tho contexts are different.
Does anyone know how could be a one find a optimal solution to solve this problem?

I ended up using a buffer limit and a queue.
I knew that this may not answer this question fully but it's the only optimal solution I could find.


Algorithm for finding connected components checking as few edges as possible Is there a good algorithm to find connected components in undirected graphs with at the lowest possible costs given as the total weight of the edges being checked?

You are looking for the minimum spanning tree for each connected component.


Is there any recursive function f whose code is unique? I am doing some reviewing for the term final on computability and found out this simple exercise. I am very fresh on theoretical computer science so if you do have an answer please make it simple.

The question is fairly simple: Is there any recursive function f whose code is unique? That is $comp(p_1, ) \doteq comp(p_2,) \doteq f $ implies $p_1=p_2$.

$comp$ is the universal recursive function.
That is, the function that for every recursive function $ f: \mathbb{N}^m \rightarrow \mathbb{N}  $, exists a code $p_f$ such that $f  \doteq  comp(p_f, <x_0,x_1,...,x_{m-1} > )$. And $\doteq$ designates equality in Kleene sense.

I found in my notes Rice's theorem in the following form.

Let $k$ be an arbitrary natural number and $ g: \mathbb{N} \rightarrow \mathbb{N}  $. If g satisfies the following conditions, the $g$ is not recursive.

1.Totality: For any $p\in\mathbb{N}$, the value $g(p)$ is defined and $g(p)\in {0,1}$

2.No constant: $g$ is not constant. There exists two natural numbers
 $p_0,p_1\in\mathbb{N}$ such that $g(p_0)=0 $ and $ g(p_1)=1$

3."Reflects equivalence of codes" If p,q are codes for the same recursive function $\mathbb{N}^k \rightarrow \mathbb{N}$ then $g(p)=g(q)$

I know the answer must be No there is not by property 3 but how can I formally write it.

No. The Padding Lemma states that there is a primitive recursive function $\sf pad$ such that, if $n$ is a code for $f$, then ${\sf pad}(n)$ is another code for $f$ which is larger than $n$.

Therefore, if $f$ has a code, it has infinitely many.

The intuition is: if you have a TM $M$ computing $f$, you can modify the TM so that it starts with some useless steps (e.g. move right, then left), and then behaves as $M$. The modified TM has a few more states, and under the "usual encoding" it will have a larger code than $M$.


Trouble Understanding a Remark about Beta-Reduction in the Lambda Calculus From page 15 of Lambda Calculus and Combinators an Introduction:

  Note 1.34 If $M \equiv aM_1 \ldots M_n$ where $a$ is an atom, and $M \triangleright_\beta N$, then $N$ must have form

  $$ N \equiv a N_1 \ldots N_n $$

  where $M_i \triangleright_\beta N_i$ for $i = 1, \ldots, n$. To see
  this, note that $M$ is really

  $$ (( \ldots ((aM_1)M_2) \ldots)M_n) $$

  when its parentheses are fully shown; hence each $\beta$-redex in $M$
  must be in $M_i$. Also the same holds for each subterm $\lambda x. P$
  whose bound variable might be changed in the reduction of$M$.

Question: Why is the following not a counter-example?

First let $M_1 = m_1 m_2 m_3$ for atomic constants $m_1$, $m_2$, $m_3$. Then let $N_1 = m_1$ and $N_2 = m_2 m_3$. Then:

$$
aM_1 \equiv a (m_1 m_2 m_3) \equiv (((am_1)m_2)m_3) \equiv ((a m_1)m_2 m_3) \triangleright_\beta a N_1 N_2
$$

Here, if I am correct, then we have a case where

$$
a M_1 \triangleright_\beta a N_1 N_2
$$

which seems to contradict the note.

Application in the lambda calculus is not associative. $m_1 m_2 m_3$ means $(m_1 m_2) m_3$ and is not equal to $m_1 (m_2 m_3)$.  So the second equality you state doesn't hold. $$a(m_1 m_2 m_3) \neq ((a m_1) m_2) m_3$$  Further $$a N_1 N_2 = (a m_1)(m_2 m_3) \neq (a m_1) m_2 m_3 = ((a m_1) m_2) m_3$$


Mano base computer and the FGO flag I have a question about the Mano base computer. The state diagram, shown below, implies that the output device will set the FGO flag to "1" after the job is done to continue the output activity from the PC (and to zero when device is busy).

But in most cases we don't have anything to do with the output and the flag stays at "1" and the cycle enters the interrupt routine every time.  It seems like this leads to the computer running the interrupt routine most of the time.

Is this a bug in this system or am I missing something?

You may have a misunderstanding of OUTR. OUTR is not the R in the flowchart you posted. Here is what is exactly done in the Mano system:

OUTR is not flag! It's a register for sending AC's value to the output device.
FGO is a flag in system that shows whether the CPU is ready to send data to output device or not. So it is "1" by default. The CPU checks the flag:

If FGO="1" :  The device is ready to send output in an interrupt cycle! so R<--1 and the interrupt process will start:  AC's content will be moved to OUTR in parallel and FGO="0" (means OUTR is full and you cannot send anything to output device!).
If FGO="0": means that the device is busy reading data from OUTR so no more data can be send out.

At the end of the I/O process the R<--0 means get out of Interrupt cycle!


Is there a concept called "white waveforms" in computer science? It sounds like the lecturer is speaking

  If you for example want to play a
  music file, mp3 file, well you know, given
  that you've taken a programming course
  before, all right? How would you do this?

  Well, you would look up on Wikipedia, what
  are the specifications of an mp3 file,
  and then you would sit down over a long
  weekend and you could probably write
  something in Python or in C, takes the file decodes it generates
  the white waveforms and so on.

  and it's
  not a big deal right after a couple days
  you will have a program that takes that
  date and generates the output, that's fine.

The lecturer used a term "white waveforms".

I know the visual of a waveform may look like this figure.

I also know .wave is one type of audio filename extension.

I am trying to figure out what "white waveforms" is.

I understand the approximate meaning that the lecturer is trying to say is playing mp3 file.

So, what is "white waveforms"?

I suspect you might have misheard.  I suspect the lecturer said "takes the file decodes it generates the right waveforms and so on"  (right, not white).


Computing number of block reads given relational algebra statement So I'm just starting to learn about query processing and such in databases and I'm having some trouble.  I don't really understand how to compute the minimum number of block reads given a relation and a query I guess you could say.  If anyone could help me out, it'd be much appreciated.  Here is an example that I'm working on:

R1(A,B,C) A is a primary key and C is a foreign key to R2.C
R2(C,D,E) C is a primary key
R1 has 20,000 records, with 200 records per block. There is a primary B+-tree index on
A with height h = 3
R2 has 45,000 records, with 4,500 records per block. There is a primary B+-tree index
on C with height hC = 3 and a secondary B+-tree index on D with height hD = 2.

Find the minimum number of block reads for each statement.  I can only hold one block of memory for each relation at a time.

Where B=1(R1)
Where C=1(R2)

I'm not looking for answers.  I'm looking for explanation of how to actually do it and guide me along the way.  Aka equations, etc. It's kind of difficult to find anything beneficial online at all.

select * from R1 Where B=1

You don't have any index on a search field (B), hence you have to do a full table scan. It means that you fetch all relation's blocks one by one and take the records which satisfy the condition B=1. (Cost - 200000/200 = 200 blocks)

select * from R2 Where C=1

There is not enough information - you have to know(at least approximately) how many records in R2 satisfy the condition C=1.
For example in case that all the records in R2 have C=1 you'll do the full table scan like above (cost - 45000/4500 = 10 blocks)
On the other hand if you have only one record with C=1 you'll read 3 blocks of index and another one from disk(cost 3 + 1 = 4 blocks)


Comparing complexities with 2 variables Suppose I have 2 possible algorithms: one runs in O(m+n) and the other runs in O(mn). Suppose also that the task is performed on a connected graph with m edges and n vertices. No other information is given about the graph. How do I know which algorithm is faster?

EDIT:
I don't think my question is a duplicate of the question quicksort refers to since that question asks for a definition and I'm asking for a calculation. I did search for a solution before I posted but couldn't find any sufficient solution to my question.

Since big O is only an upper bound, you cannot really tell which algorithm is faster. Let us therefore assume that the running times of the two algorithms are actually $\Theta(n+m)$ and $\Theta(nm)$. Since your graphs are all connected, you have $n-1 \leq m \leq \binom{n}{2}$, and so the first algorithm runs in time $\Theta(m)$ and the second in time $\Omega(m^{1.5})$. This shows that as $m\to\infty$ (equivalently, as $n\to\infty$), the first algorithm is asymptotically faster.


Are all languages generate by Turing machines countable? Are all languages generate by Turing machines countable? I know that the set of all TMs are countable, but what about the languages that they generate?

Yes. All languages, not only those generated by Turing machines, are countable. This is because they are all subsets of $\Sigma^*$, and $\Sigma^*$ itself is countable. However, there are uncountably many languages.


Whether TM accepts epsilon? $L = \{ \langle M \rangle \mid \epsilon \in L(M) \}$, where $M$ is any Turing machine.

Why is the above problem undecidable? Can't we just check whether the initial state is a final state and say the TM accepts $\epsilon$ if the initial state is the final state else it doesn't? We can also just check if the TM goes to an accepting state on the blank symbol.

First, a note on notation: $L(M)$ is a language which is a set. Languages don't accept or reject, Turing machines do. You can either say "$\epsilon \in L(M)$" or "$M$ accepts $\epsilon$".

There are many Turing machines in this language that don't meet your description. For example, imagine a machine that upon reading a blank goes and writes, say, 111 and then accepts. The initial state does not need to have a transition to an accept state on a blank symbol in order to belong in this language.

Here's another perspective on why this language is undecidable using Kleene’s Recursion Theorem. Imagine that there is some decider $D$ that, given the description of a TM $\langle M \rangle$, $D$ accepts if $M$ accepts $\epsilon$ and rejects otherwise. Now create a Turing machine with the following behavior:

Get my own description <M> and then run D on <M>.
If D accepts <M>:
   If input is empty, reject. Otherwise accept.
Else:
   If input is empty, accept. Otherwise reject.

The existence of this decider allows us to create the above Turing machine which is a contradiction. Essentially, if the decider says the Turing machine is supposed to accept the empty string, it then goes and rejects and if it's supposed to reject, it then goes and accepts. This idea of being able to use self-reference and ask "What am I about to do?" and then doing the opposite shows that no single machine can predict behavior of all others.


What do these Big-O notations mean in context of comparison What do the following mean, in the context of greater than, or smaller than?
$$
O(n \log n) > O(n)
$$
$$
O(nlogn) < O(n^2)
$$

In this context, this comparison means the subset of. Hence, $O(n\log n) > O(n)$ means All members of $O(n)$ exist in $O(n \log n)$ as well or $O(n) \subset O(n \log n)$. For example, $f(n) = \sqrt{n} \in O(n)$ and $f(n) \in  O(n\log n) $ and $g(n) = n \log n \not \in O(n)$ and $g(n) \ \in O(n \log n)$.


With a halting oracle, can tell whether something will have finite output? A program can have finite output, yet still not halt. Example:

1: output "Yolo"
2: output ""
3: go to step 2

This only ever outputs "Yolo", despite never halting.

Is there some way, with a halting oracle, to determine whether a program will have infinite output or not?

Bonus: If not, what would be the Turing Degree of a machine capable of such a feat?

It's not clear what specific computational model you use.
If you're using Turing Machines, then having a finite output is equivalent to having a finite number of distinct configurations (assuming that you're not allowed to "erase" the tape).

So we're considering the language of all TMs $M$ such that $M$ has a finite number of configurations when run on the empty input.
Clearly this is Turing recognizable - simulate the machine and accept if it halts or repeats a configuration. Thus, the problem is in RE.

It's also very simple to show that it's not in coRE by a reduction from $A_{TM}$. So we conclude that the problem is in RE\coRE.

Now, given a halting-problem oracle, the problem is decidable: Given a TM $M$, modify it to a machine $M'$ such that $M'$ simulates $M$ and records the configurations, and if a configuration is repeated,or if $M$ halts, then $M'$ halts. Now simply run the oracle on $M'$.


Problems conjectured but not proven to be easy We have many problems, like factorization, that are strongly conjectured, but not proven, to be outside P. Are there any questions with the opposite property, namely, that they are strongly conjectured but not proven to be inside P?

Two decades ago, one of the plausible answers would be primality testing: there were algorithms that ran in randomized polynomial time, and algorithms that ran in deterministic polynomial time under a plausible number-theoretic conjecture, but no known deterministic polynomial-time algorithms.  In 2002, that changed with a breakthrough result by Agrawal, Kayal, and Saxena that primality testing is in P.  So, we can no longer use that example.

I would put polynomial identity testing as an example of a problem that has a good chance of being in P, but where no one has been able to prove it.  We know of randomized polynomial-time algorithms for polynomial identity testing, but no deterministic algorithms.  However, there are plausible reasons to believe that the randomized algorithms can be derandomized.

For instance, in cryptography it is strongly believed that highly secure pseudorandom generators exist (e.g., AES-CTR is one reasonable candidate).  And if that is true, then polynomial identity testing should be in P.  (For instance, use a fixed seed, apply the pseudorandom generator, and use its output in lieu of random bits; it would take a tremendous conspiracy for this to fail.)  This can be made formal using the random oracle model; if we have hash functions that can be suitably modelled by the random oracle model, then it follows that there is a deterministic polynomial-time algorithm for polynomial identity testing.

For more elaboration of this argument, see also my answer on a related subject and my comments on a related question.


Find the length of the longest subarray having sum greater than k I tried to solve this problem but could not do it better than $O(n^2)$.
My Algorithm:
1. Calculate prefix sum

2. for i in 1..n:
     for j in 1..i:
       if presum[i] - presum[j-1] > k:
          ans = max(ans, i - j)

Edit: I have found a solution which works in $O(n\log n)$. This solution does a binary search on the length of the subarray and chooses the maximum length of the subarray satisfying the property.
The code is as follows:
#include<stdio.h>
long long int a[1000005]={0},sum[1000005]={0},n,k;
long long int check(long long int len)
{
long long int i,c=0;
for(i=len;i<=n;i++)
{
 if((sum[i]-sum[i-len])>=k)
   c++;
}
 return c;
 }

int main()
{
 long long int i;
 scanf("%lld",&n);
 scanf("%lld",&k);
 for(i=1;i<=n;i++)
  {
  scanf("%lld",&a[i]);

  sum[i]=a[i]+sum[i-1];
  }
 long long int low=0,high=n,ans=0,count=0;
 while(low<=high)
 {
  long long int mid=(low+high)/2;
  long long int p=check(mid);
  if(p>0)
  {
   ans=mid;
   low=mid+1;
  }
  else
  {
  high=mid-1;
  }
}
if(ans==0)
    printf("-1\n");
else
    printf("%lld\n",ans);
return 0;
 }

My doubts: How does this algorithm discards the search space?
More specifically, what I want to know that suppose there does not exist any subarray of length $len$, then how can we show that there won't exist any subarray of length $>len$. The above code does the same way, whenever there does not exist any subarray of length $mid$ it removes the other half and continues to search for an answer in the lower half by decreasing the $high$ to $mid-1$.

We can improve your code and speed it up from $O(n^2)$ to $O(n \cdot \log n)$ with one change.
First precompute all prefix sum. Let $P_t$ = the sum of the first $t$ elements. Notice that $P_t$ is defined from $0 \leq t \leq n$ and in particular $P_0=0$. This step is $O(n)$ so it is ok.
Now you need to find two index $0 \leq j < i \leq n$ such that $P_i - P_j > k$ and $i - j$ is maximum.
The next step in your solution is fixing the right most index ($i$), so we need to figure out a way to find fast the leftmost $j$ such that $P_i - P_j > k$. For a fixed $i$ the condition can be converted to:
What is the smallest $j$ such that $P_i - k > P_j$?
We might be tempted to do binary search here, but it is not correct since $P_j$ is not sorted... but wait, we can just get rid of "not sorted elements" easily. Let's say that if there exist two index $a < b$ such that $P_a \leq P_b$, then we are not interested at all in the element at position $b$, since it will never be the leftmost index of an optimal interval, given that we can extend that interval up to position $a$.
With this in mind we can define an index $j$ important, if there is no index $k < j$ such that $P_k \leq P_j$, i.e. $j$ is the smallest element in the prefix ending at $j$. One nice property of important elements, is that they form a strictly decreasing subsequence of array $P$, and for any fixed $i$, the optimal election of $j$ is an important index.
Since the important index array forms a strictly decreasing subsequence we can perform binary search without any issue. To build such array, we inserts elements one by one, if the new element is less than the minimum element in the array then it is important and should be inserted, otherwise, we don't add this element. The minimum element of the important index array will always be the last one.
Pseudocode:
def largest_subarray(array, k):
    n := length of array
    P := prefix sum of array
    # Remember that P[0] = 0, P[1] = array[1], ...

    # List of important index in increasing order.
    # Notice the values such indexes are pointing too are decreasing.
    # That is P[J[0]], P[J[1]], ... is strictly decreasing
    # Initially there is only index 0
    J := [0]

    # Answer of this function.
    longest_length := -1

    for i in 1..n:
        # Check if there is at least one solution ending
        # at index i. i.e. If P[i] - min(P[j < i]) > k

        # Index of the smallest element
        last_j := J[-1]
        if P[i] - P[J[-1]] > k:
            # There is at least one solution, so we can run binary search
            # to find the optimal solution. i.e the smallest index j
            # such that P[i] - P[j] > k
            # Since j belongs to J, we are finding the smallest index
            # p such that P[i] - P[J[p]] > k
            p := bin_search()
            longest_length := max(longest_length, i - J[p])

        # Check if i is important
        if P[i] < P[last_j]:
            J.push(i)

    return longest_length


Median of medians confusion -- the "approximate" median part I'm struggling with the median of medians algorithm, and I think it's perhaps more of a semantics thing rather than a technical thing. I've always thought the median of medians algorithm as finding an approximate median $p$ such that $p$ is within $20\%$ of the true median $M$ in the sorted array.
However, when I look at actual implementations, e.g., in https://brilliant.org/wiki/median-finding-algorithm/, the algorithm they posted returns an exact median, but at each level of the recursion, you may have some approximate median generated from a sublist of medians. And eventually you'll reach a level where the array is $\leq 5$ elements, ending the recursion. At this level, you obtain an exact median of the array you passed in. So I had thought all this time that this exact median computed at the last level is actually your estimate of the median in the original array passed in at the first level of the recursion.
So I had the same confusion as this poster https://stackoverflow.com/questions/52461306/something-i-dont-understand-about-median-of-medians-algorithm and some others.
Now that I understand this algorithm, I am now confused on how the median of medians actually finds an "approximate" median to the original array. In all the implementations I've seen, the median you find using median of medians is exact. So where does the approximate part come in other than approximating the median at each recursion level? Even Wikipedia describes as an algorithm that approximates a median. Yes, it approximates medians at various levels, but the final output is exact.
Or am I operating under a false premise in thinking that Median of Medians finds an approximate median to the ORIGINAL array?

Median-of-medians is a recursive algorithm which solves the more general selection problem: given an array $A$ of length $n$ (which we assume, for simplicity, has distinct elements) and an integer $k$, find the $k$'th smallest element (where $1 \leq k \leq n$). It works as follows:

If $n \leq K$ (where $K$ is some constant), solve the problem by brute force.
Otherwise, find an approximate median $x$ of $A$ in $O(n)$. By approximate median, we mean that $x$ is the $m$'th smallest element in $A$, where $\alpha n \leq m \leq (1-\alpha) n$ for some constant $\alpha < 1$.
Use $x$ to split $A$ into elements smaller than $x$, comprising an array $A_{<x}$ of length $m-1$, and elements larger than $x$, comprising an array $A_{>x}$ of length $n-m$.
If $m = k$, then output $x$. If $m > k$ then output the $k$'th smallest element of $A_{<x}$. If $m < k$ then output the $(k-m)$'th smallest element of $A_{>x}$.

The running time of the algorithm satisfies the recurrence $T(n) \leq T(\alpha n) + O(n)$, whose solution is $T(n) = O(n)$.
The algorithm finds the exact median, but it does so by repeatedly finding approximate medians.


Recursively edit 2-D array using backtracking I have a 2-D array which contain 3 types of elements:

C (Contaminant)
R (Rock)
W (Water)

The rule is that:

  contaminant can seep through water but not through rocks.

Let's say I have the following input array:

WWWRW
CRRRR
RWWRW
WWWRR
WRRWC

So the cells which have 'C' as their value in the above array can contaminate in the same row and same column if water is present.

So the output would like something like this:

CCCRW
CRRRR
RWWRW
WWWRR
WRRCC

I know I have to solve this using via backtracking and recursion, but I am not able to come up with an apt algorithm to do so.

Any help will be hugely appreciated.

The following algorithm would be my first attempt.

Initialize a 2D array $A$ with given characters, 'C', 'W' or 'R'.
Loop $m+n-2$ times.

In each loop, iterate over all cells of $A$. For each cell, check whether it is 'C'. If yes, change all of it neighbors that are 'W' to 'C'. Otherwise, do nothing.

Here is an illustration of the step 2 on the example given in the question, where after 3 loops the situation will not change any more although we have specified 5+5-2=8 loops. Looping $m+n-2$ times guarantees that all contaminated elements will be found although the situation should become stable earlier in general. (In fact, the number of times needed is the longest Manhattan distance from a water cell that will be contaminated to the nearest cell that is contaminated initially.) $m+n-2$ is chosen here just for its simplicity.

WWWRW     CWWRW     CCWRW     CCCRW              CCCRW
CRRRR     CRRRR     CRRRR     CRRRR              CRRRR
RWWRW ->  RWWRW  -> RWWRW  -> RWWRW  -> (stable) RWWRW
WWWRR     WWWRR     WWWRR     WWWRR              WWWRR
WRRWC     WRRCC     WRRCC     WRRCC              WRRCC

Once the above simple and sound algorithm has been working well, we can consider a couple of improvements.

Once we have checked a cell with value 'C', we will mark it as 'V' after we have changed its neighbors. In each loop, we will ignore cells with value 'V'.
We can use a queue to list the cells to be checked. Cells that are changed to 'C' will be appended to the queue. Once the queue is empty, the algorithm stops.

  I know I have to solve this using via backtracking and recursion.

Not necessarily.

The technique used in the above algorithm is looping simply. Or nested loops to advance the frontier of contaminants. You can imagine the contaminants are spreading to their immediate neighbors uniformly by one tick of time. Ticks of time correspond to the outer loop while all contaminant correspond to the inner loop.


I can't understand this example of PDA Automata looking for old tests of Language Theory, I see this exercise:

Give a PDA automata that recognize the language $L = \{w \in \{a,b\}^*,\ 2|w|_a=3|w|_b\}$

They propose this solution:

Can anyone help me to understand what strategy they used?

Sorry for my english, is not my native language.

Thanks.

The idea of this PDA is very simple. Start with a PDA for $L' = \{ w \in \{a,b\}^* : |w|_a = |w|_b \}$, and now modify it as follows:

Whenever you read $a$, simulate the original PDA reading $aa$.
Whenever you read $b$, simulate the original PDA reading $bbb$.

Hopefully you can see why the new PDA accepts $L$ given that the original one accepted $L'$.

The PDA for $L'$ maintains a stack which can be of three different types, depending on the word $x$ seen so far:

If $|x|_a = |x|_b$ then the stack contents is $Z_0$. In particular, this is also the initial stack.
If $|x|_a > |x|_b$ then the stack contents is $B^{|x|_a - |x|_b} Z_0$.
If $|x|_a < |x|_b$ then the stack contents is $A^{|x|_b - |x|_a} Z_0$.

When the top-of-stack is $Z_0$ we know that $|x|_a = |x|_b$, and so we optionally move to the final state; the PDA will accept only if $x = w$, since otherwise it will get stuck.

When converting this PDA to the one for $L$, we use epsilon transitions to simulate reading the second $a$ and the second and third $b$s.


Duplicating ACKs and Window Sizes After reading an answer at this link:
https://serverfault.com/questions/503345/three-duplicate-acknowledgementss
I am confused. Do ACK values repeat when a packet is lost or when an out of sequence packet is received? For example in the diagram, the ACK values are same at the 12th and 13th segment. However, there's a drastic change in the window size. What exactly is the link?
I also read that selective acknowledgments could be used in segement 8. I know what they do by definition but I don't understand why we could use them here in segment 8 particularly. Any ideas? If it's because of the same SEQ & ACK numbers in the corresponding segments, it would be the same for segment 10, right?

In simple words: ack is the way of the receiver to tell you "i got data until some num now send me from this num",now if a packet is lost it means the reciver will not get its data.

If i understood your question right then we can see the acks in the 12th and 13th packets are identical,the reason is because not data was sent between them to the reciver

Now why the window size is bigger?its simply because the receiver reads the data in a certain speed and the buffer now has more space in it

So th reason they have same acks its because no data was sent to the receiver
And the reason why the window size is bigger is because the receiver reads from the buffer