Here is a proof that the problem remains hard when $k=1$. For simplicity it uses an item of size equal to the bin capacity. If you require each item to be smaller than the bin capacity you can subtract a small enough constant from this item's size.
Consider an instance of $3$-partition in which $3n$ positive integers  $x_1, x_2, \dots, x_{3n}$ of total sum $S$ need to be partitioned into $n$ triples $t_1, \dots, t_n$, each with total sum at most $T=\frac{S}{n}$, where $T$ is also an integer.
Assume that $x_i \ge \frac{2T}{7}$ (it is known that the problem remains strongly NP-complete in this case).
Furthermore assume that $n > \max\{8,T+1\}$ (if this is not the case, multiply each integer in the instance by $10$, add many copies of the integers in $\{10T-2, 1, 1\}$ to the input, and then convert the resulting instance into an instance that satisfies $x_i \ge \frac{2T}{7}$. This conversion multiplies the new value of $T$ by $7$).
Consider the instance of your version of bin-packing in which $k=1$ and you need to pack the set of elements $Y = \{y_1, \dots, y_m\}$ into the fewest number of bins of capacity $n T$ (you can set the capacity of each bin to $1$ by a suitable scaling of all the involved quantities).
Let $m=3n+1$, $y_m = nT$ and $y_i = (n-1) x_i$ for $i=1,\dots,3n$.
If the $3$-partition instance is a yes-instance then $Y$ can be packed into $n$ bins.
Create a bin $b = (y_i, y_j, y_h)$ for each triple $t = (x_i, x_j, x_h)$ of a solution of $3$-partition. Notice that $y_i + y_j + y_h = (n-1) (x_i + x_j +x_h) = (n-1)T$, leaving $b$ with unused capacity of $T$.
The only element not assigned to a bin is $y_m$. Split $y_m = nT$ into $n$ pieces of size $T$ each, and add a piece to each of the $n$ bins.
If $Y$ can be packed into $n$ bins then the $3$-partition instance is a yes-instance.
Notice that $\sum_{i=1}^m y_i = (n-1) \sum_{i=1}^{3n}x_i + nT = (n-1)nT + nt = n \cdot nT$, showing that each each of the $n$ bins must be completely full.
We can assume w.l.o.g., that if some element is split into pieces, this element is $y_m$.
Indeed, if an element $y' \neq y_m$ is split, there must be one bin $b'$ that is used entirely for $y_m$. We can then swap each piece of $y'$ with a piece of $y_m$, so that $y'$ is now entirely contained in $b'$.
Notice now that each bin $b$ must contain exactly $3$ elements from $\{ y_1, \dots, y_{3n}\}$.
Indeed, if this was not true there would exist a bin that contains at least $4$ elements from $\{ y_1, \dots, y_{3n}\}$ and its used capacity would be at least
$$
4(n-1)\left(\frac{2T}{7}\right) = \left( \frac{8}{7}n - \frac{8}{7} \right)T > nT.
$$
We construct a solution for the $3$-partition instance by creating a triple $t = (x_i, x_j, x_h)$ for each bin $b$ containing $y_i, y_j, y_h$ with $i,j,h \le 3n$.
The total weight of $t$ is at most:
$$
x_i + x_j + x_h = \frac{y_i + y_j + y_h}{n-1} \le \frac{nT}{n-1}
= \frac{(n-1)T+T}{n-1} = T + \frac{T}{n-1} < T+1,
$$
i.e., $x_i + x_j + x_h \le T$.


Dynamic Programming - Print all paths from (0,0) to (n,n) in Grid/Lattice

You can solve this problem using a recursive formulation of print all paths from a point $(i,j)$ to the target $(n,n)$ in the grid. I call this function $f(i,j)$. So the all paths will be in $f(0,0)$ call.

$f(i,j) = \begin{cases}
\emptyset & if\ \ {i>j}\\
\emptyset & if\ \ \neg( {0\leq i\leq n\ \wedge 0\leq j\leq n) }\\
\{(n,n)\} & if \ \ i = n \wedge j = n\\
\bigcup_{p\,\in\, f(i+1,j)\,\cup\,f(i,j+1) } \ \ \{(i,j)\}\cup p & \text{otherwise}
\end{cases}$

By example, two of all paths from $f(0,0)$ when $n=4$ are:

blue path = {{0, 0}, {0, 1}, {1, 1}, {1, 2}, {2, 2}, {2, 3}, {3, 3}, {3, 4}, {4,
  4}}

red path = {{0, 0}, {0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}, {4,
  4}}

So, although programming is not in the scope of this site, I think is good to see a implementation for a memoization version of the above algorithm.
asdf

from functools import wraps

def memo(func):
    cache = {}

    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap

@memo
def f(i, j):
    global n
    if i > j:
        return []
    if not (0 <= i <= n and 0 <= j <= n):
        return []
    if i == n and j == n:
        return [[(n,n)]]
    alls = []
    for path in f(i, j+1)+f(i+1, j):
        if len(path) > 0:
            alls += [[(i,j)] + path]
    return alls

n = 4
for path in f(0,0):
    print path


reduce reduce and shift reduce error in LALR grammar

I don't see any problem with your first grammar and bison doesn't complain on the rendering I've done of it.

I (and bison) see one conflict in your second grammar (which doesn't describe the same language as the first BTW). After having seen id id id with a pending ^, you don't know if your last id and the ^ should be an F, or if you should keep together the three id forming an A which will be gathered with the '^'.

Edit after your comment:

A direct rendering of your rules:

EXP ::= id | EXP ^ | ^ EXP | EXP . id | EXP [ EXP ]

will be ambigous — and thus have conflict(s) — because you don't state if the prefix version of ^ has priority over the other (postfix) operators. I don't remember how it was in Pascal, but you can get both effects with

EXP ::= POST | ^ EXP
POST ::= id | POST ^ | POST . id | POST [ EXP ]

and

EXP ::= PRE | EXP ^ | EXP . id | EXP [ EXP ]
PRE ::= id | ^ PRE

Edit again: a mixed version corresponding to my understanding of what you ask in the comment (I continue to find this confusing and I consider the complexity of the grammar — with post operators given twice — as a hint it is so :-) )

EXP ::= PRE | POST2
POST2 ::= PRE '^' | POST2 '^' | POST2 '.' id | POST2 '[' EXP ']'
PRE ::= POST | '^' PRE
POST ::= id | POST '.' id | POST '[' EXP ']'


Rice's theorem for non-semantic properties

A general theorem that partially covers the example given is that any $\Sigma^0_1$-hard property of the machine will be undecidable. The halting problem is $m$-reducible to the state-reachability problem, so that shows the state reducibility problem is $\Sigma^0_1$-hard.

However, this is not an "if and only if" theorem like Rice's theorem. If every $\Sigma^0_1$ property of the index of the Turing machine counts as a property of the machine, then there is not going to be a nice characterization, because there is not any nice characterization of which r.e. sets are decidable in terms of the index of the r.e. set.


Why is learning DNF harder than learning CNF?

It's important to distinguish between $k$-CNF and CNF.  A $k$-CNF formula is a CNF formula where every clauses has at most $k$ literals; a CNF formula has no limit on the number of literals in each clause.

Both $k$-CNF and $k$-DNF are efficiently, properly PAC learnable, when $k$ is constant.  In contrast, as far as I am aware, it is not known whether CNF or DNF are efficiently, properly PAC learnable (no PAC-learning procedure is known for either).  So there is no asymmetry.

By "efficiently, properly PAC learnable", I mean that there is a polynomial-time algorithm for PAC learning, where the hypothesis space is the same as the concept space (e.g., given labelled instances from a $k$-CNF formula $\phi$, we want to find a $k$-CNF formula $\phi'$ that has low generalization error).

Since you haven't provided any references nor told us where you got the impression that $k$-DNF isn't PAC-learnable, it's hard to know what the exact source of your misconception might be.


Simple question about signed integer multiplication

Your answer is nearly right.
So x is an unsigned negative value of k bits. The smalles possible value of x is representet by the 2's Complement number 1000....0. If you multiply this number by 2 (or logical shifting it by 1, which is equivalent) you end up with the number 0000...0 which is 0. And therefore (x*2)<0 is false.


Searching a hierarchy for progressive node criteria

These things are generally done through backtracking. Which in your case would look somewhat like this:

Go down 3 levels and look for 'a'
If you find some -> perform your magic
If you find none (or if you do, depending on the implementation) -> go up 1 level repeat steps 1-3

Really this is no better than simply searching all directories in the worst case, but there is no way you can guarantee having found all a's without searching every directory anyway (assuming no prior knowledge). However this solution will have a much better average case performance if the a's are always at the maximum level than simply starting to search at level 1, then level 2 etc.

edit: also, regexes are fast because the average CPU performs billions of operations per second. If you're copying files then the copying will be the part slowing it own drastically anyway so you probably should not be too concerned with the performance of your searching algorithm


MinHeap represented by an array - two simple statements

You're not missing anything, this problem really is that easy. Your solution works, but I feel like I should point out that you can disprove both statements with a much smaller heap. In particular

\begin{array}{}
[2, 7, 6]
\end{array}

with $i = 1$ and $j = 2$ for the first statement and swapping them for the second.

Furthermore, I'm pretty sure those two statements only hold if the array is sorted (assuming distinct elements).


Compiler backend generated from declarative description of the architecture

João Dias; Norman Ramsey: "Automatically Generating Back Ends Using Declarative Machine Descriptions", Proc. ACM Symp. Principles of Prog. Lang., (POPL-37):403-416, 2010.

I think this goes a bit farther than you asked for, because they're actually looking for good code sequences.  For something a little more basic you could go back to some of Norm Ramsey's earlier work, like: Norman Ramsey; Mary F. Fernández: "Specifying Representations of Machine Instructions", ACM T. Prog. Lang. and Sys., 19(3):492–524, May 1997.

There's a long line of research on trying to automatically generate back ends from simpler descriptions.  Look for papers by Christopher W Fraser, David R Hanson and Todd A Proebsting.


Given a set $A$ of sets find a minimal set $B$ of pair-wise disjoint sets such that each set in $A$ can be expressed as a union of sets in $B$

Essentially you are finding all non-empty components of the Venn diagram of the sets in $A$. So here is an algorithm:

B = empty set
for each set S in A:
    for each set T in B:
        remove T from B
        compute (S \cap T), (T \ S) and (S \ T)
        if (S \cap T) is not empty, add (S \cap T) into B
        if (T \ S) is not empty, add (T \ S) into B
        S = S \ T
    if S is not empty, add S into B
return B

This algorithm runs in $O(nm)$ time where $n$ is the number of all elements involved, and $m$ is the number of sets in $A$.

For your example, initially $B$ is empty.

After dealing with $\{1,2\}$, $B=\{\{1,2\}\}$.

After dealing with $\{1,2,3\}$, $B=\{\{1,2\},\{3\}\}$.

After dealing with $\{3,4\}$, $B=\{\{1,2\},\{3\},\{4\}\}$.

After dealing with $\{4\}$, $B=\{\{1,2\},\{3\},\{4\}\}$.


For Computer Science, I would recommend you

  Computer Science: An Overview 11th J. G. Brookshear.

If you are more interested, you can attend one of the online courses, you can register for free and finish these courses online with exercises. I recommend you one of these:

An Introduction to Computer Science from Harvard, more informations you can find here EDX
Computer Science from Stanford, more info here

Algorithms, you can find relevant online courses following these books on EDX and Coursera as well. Depends on how much time you have and want to spend on these subjecs, and how deep you want to go.

  Algorithms (4th Edition) by Robert Sedgewick and Kevin Wayne

or

  Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein


How can the intersection of CFLs and REGs be CFL if REG is a proper subset of CFL?

You are confusing two different statements.

$\mathrm{CFL} \cap \mathrm{REG} = \mathrm{REG}$ or, equivalently,
 for all $L_1 \in \mathrm{REG}$ : $L_1 \in \mathrm{CFL}$.
For all $L_1 \in \mathrm{REG}$, $L_2 \in \mathrm{CFL}$ : $L_1 \cap L_2 \in \mathrm{CFL}$.

The first makes a statement on two sets of languages (aka language classes), the second makes one over (many) pairs of sets of strings (aka languages). So in mixing the two, you are creating a type error.

Also, you seem to suggest that if a language is context-free, it's not regular. That is false; we have $\mathrm{REG} \subsetneq \mathrm{CFL}$ (cf. 1.), so showing a language is CFL (using 2.) does not preclude it from being regular. Specifically, it's easy to find examples of a non-regular context-free and a regular language whose intersection is regular.


Optimal Loading of a Hopping Airplane Minimum Cost Flow Problem

One approach to understand some complicated situation is to figure out some simplest but still meaningful situations.

In the current situation, let us check a situation when there are only two hops, hop 0 and hop 1. The simpler situation when there is only one hop is too trivial to be instructive, sine there will be no passenger to pick up.

Picking up your pen (or pencil or stylus or your finger), draw the following reduced version of Figure 9.4 in the reference provided.

The above direct network means

there are up to $b_{12}$ passengers at node 1-2 who can be picked up at node 1 (hop 1) and who should be dropped at node 2 (hop 2)
The cost of the arc from node 1-2 to node 1 is $-f_{12}$, where $f_{12}$ is the fare per passenger from node 1 to node 2. That means every passenger picked up will pay $f_{12}$.
The capacity of arc from node 1 to node 2 is $p$. There is no associated cost.
The arc from node 1-2 to node 2 is the imaginary flight with no cost associated nor any capacity limit.
There should be $b_{12}$ passengers reaching node 2. They either take the flight from node 1 to node 2 physically or take the arc from node 1-2 to node 2 virtually without paying any fare.

The minimum cost flow problem for this simple directed network is the following, where $x_{a,b}$ means the number of passengers (the flow) on the arc from $a$ to $b$.

  $$\text{Minimize }\ \ z(x)= (-f_{1-2, 1})x_{1-2,1} + 0x_{1,2} + 0x_{1-2, 2}$$
  subject to
  $$x_{1-2,1} + x_{1-2,2} = b_{12}$$
  $$x_{1,2} - x_{1-2,1} = 0$$
  $$-x_{1-2,2} - x_{1,2} = -b_{12}$$
  $$ 0\le x_{1-2, 1}$$
  $$ 0\le x_{1, 2}\le p$$
  $$ 0\le x_{1-2,2}$$

Why do we want to minimize $z(x)$? Because the total fare collected is $-z(x)$.

All the conditions in the end just means, $x_{1-2,1}\le b_{12}$ and $x_{1-2,1}\le p$. We can solve this problem minimum cost flow easily by letting $x_{1-2,1}=\min(b_{12},p)$, the most passengers available not exceeding the airplane capacity.

Hopefully the above explanation is detailed enough to enable you to further understand the full minimum cost flow formulation for the problem of optimally loading a hopping airplane. You can establish a one-to-one correspondence between feasible passenger routings and feasible flows in the minimum cost flow formulation of the problem.


NP-complete problem whose corresponding optimization problem is not NP-hard

Take a look at Bellare and Goldwasser, "The complexity of decision vs. search" SIAM J. of Computing 23:1 (Feb 1994), pp. 97-119. It discusses the issue at length. Perhaps a bit more readable is the class note by Bellare, "Decision versus search".


Given Directed Graph G(V,E) with red/black vertices, v is good if there's a path from v to a black vertex

Lets consider the case where you need to be $O(V+E)$. As someone in the comments mentioned, the way I thought about it was reversing the edges, as described below:

Reverse all edges
For every unvisited black vertex, perform a BFS/DFS on all unvisited nodes, marking them visited as you search.
All visited nodes are good.

It is trivial to see that if and only if a node is marked visited, it can reach a black vertex in the original graph. The forward direction is simple, if a node is visited, then there is a direct path to a black vertex. The other direction is also true, if there is a path from a node to a black vertex in the original graph, that that node would clearly have been visited by one of the searches.

Now, let's say you want to stick with the SCC strategy. We first find all SCC's in $O(V+E)$ time. Then, for each SCC we condense it to a single node and color it black if it contained a black node and red otherwise. All edges into and out of the each SCC will now lead into and out of the new corresponding condensed node. Now we can just perform the same algorithm as above on the new graph with no SCCs! For every node, mark it as good iff its corresponding SCC was visited.


Minimal size of contracting a DAG into a new DAG

One approach to solving this problem would be to use integer linear programming (ILP).  Let's tackle the decision version of the problem: given $k$, is there a way to contract same-color vertices to get a DAG of size $\le k$?

This can be expressed as an ILP instance using standard techniques.  We're given the color of each vertex in the original graph.  I suggest that we label each vertex with a label in $\{1,2,\dots,k\}$; all vertices with the same label and same color will be contracted.  So, the decision problem becomes: does there exist a labelling, such that contracting all same-color same-label vertices yields a DAG?

To express this as an integer linear program, introduce an integer variable $\ell_v$ for each vertex $v$, to represent the label on vertex $v$.  Add the inequality $1 \le \ell_v \le k$.

The next step is to express the requirement that the contracted graph must be a DAG.  Notice that if there is a labelling of the form listed above, without loss of generality there exists such a labelling where the labels induce a topological sort on the contracted graph (i.e., if $v$ precedes $w$ in the contracted graph, then $v$'s label is smaller than $w$'s label).  So, for each edge $v\to w$ in the original graph, we'll add the constraint that either $v$ and $w$ have the same label and same color, or else $v$'s label is smaller than $w$'s label.   Specifically, for each edge $v\to w$ in the initial graph where $v,w$ have the same color, add the inequality $\ell_v \le \ell_w$.  For each edge $v \to w$ where $v,w$ have different colors, add the inequality $\ell_v < \ell_w$.

Now see if there is any feasible solution to this integer linear program.  There will be a feasible solution if and only if the labelling is of the desired form (i.e., contracting all same-color same-label vertices yields a DAG).  In other words, there will be a feasible solution if and only if there is a way to contract the original graph to a DAG of size $\le k$.
We can use any integer linear programming solver; if the ILP solver gives us an answer, we have an answer to the original decision problem.

Of course, this isn't guaranteed to complete in polynomial time.  There are no guarantees.  However, ILP solvers have gotten pretty good.  I would expect that, for a reasonable-sized graph, you've got a decent chance that an ILP solver might be able to solve this problem in a reasonable amount of time.

It's also possible to encode this as a SAT instance and use a SAT solver.  I don't know whether that would be more effective.  The ILP version is probably easier to think about, though.

(I hope this is right.  I haven't checked every detail carefully, so please double-check my reasoning!  I hope I haven't gone awry somewhere.)

Update (10/21): It looks like ILPs of this form can be solved in linear time, by processing the DAG in topologically sorted order and keeping track of the lower bound on the label for each vertex.  This has me suspicious of my solution: have I made a mistake somewhere?


Consider the range of j in the inner loop:

What is its maximum?
What is its average?
What is its average average?


By definition,
$$
L \diagdown L(A) = \bigcup_{x \in L} \{ w : \delta(q_0,xw) \in F \}.
$$
The idea now is to use the identity
$$
\delta(q_0,xw) = \delta(\delta(q_0,x),w).
$$
You take it from here.


Graphs that cause DFS and BFS to process nodes in the exact same order

Assume our BFS and DFS have the rule to start from a specific node and both of them then visit the node with the lowest degree:

Start from left most black node, then both (BFS and DFS) traversals will visit left most red node, then they will visit next black node, and so on. To make it more general, you could add some paths in between triangles, or add star after finishing triangles.


Your description of NP is still missing the accept criterion. For example you might decide to accept the input exactly in case all computation paths accept. This would give you the class coNP instead of NP. Or you might decide to accept the input exactly in case half of the computation paths accept. But for NP, the accept criterion is that there exists at least one computation path which accepts. Other than that, your parallelism model of NP is perfectly fine. And yes, the deterministic machine can simulate the computation of the non-deterministic machine in $O(2^n)$ time!


You're on a good path!  Keep at it.  Remember that a pushdown can have a finite-state control, and you can remember up to a finite amount of information in the finite-state control.  Also, it can have $\epsilon$-transitions (so the read head doesn't consume any of the input).  Those might be helpful.


Indentation has absolutely no syntactic or semantic meaning in Java, and indeed in most popular languages (the main exception is Python).
Which if does your else belong to? This is an instance of the famous dangling else problem.
The syntax of Java associates each else to the innermost if, so the Java compiler understands your code in a way which is different than what your indentation suggests. If you want to associate the else with the outer if, you can use curly brackets.


What are the tradeoffs between implenting dataframes as a series of columns vs a series of tuples

At the level of an actual implementation, Array of structures versus structure of arrays makes an enormous performance difference; particularly when SIMD parallelism is involved.  If you want to add together all of the values of one field, then all of those values are sitting next to each other.

SIMD instructions add/mul entire arrays all at once, rather than looping over each struct member.  If you need to jump around memory to add all of these, you will invalidate memory caches.  Also, suppose that only one column has non-default values, and the other dozen columns have zero values.  The implementation can simply not bring over columns that are all zero.  Run-length coding can be used on columns, or differential encoding.

In the BigData world, there are different serialization standards in use.  Parquet is one option, picked because it has these characteristics due to being a columnar format.  These kinds of formats are oriented towards doing stream processing.  For example: you can get the next 1024 rows as a batch out of a cursor, but as an implementation detail they are packed in a columnar format.


L(M)=L where M is a TM that can move right or stay, so L is decidable

This inherently depends on your exact model of a TM, I'm assuming the following:
A left-bounded tape, the head starts at position 0 and the word to decide is written at the tape. Furthermore, the TM has finitely many states.

Now the TM can only look at the first symbol at a time, can do finite computation (i.e. can have finitely many transitions to different states (*)) and move its head to the right once. Then it can repeat itself (**). In that, this TM is quit limited in what it can do, it can do as much as an DFA (like pointed out in the comments), that is: Look at a symbol, do some state-transitions and look at the next symbol.

(*) What happens, if the TM loops in the inner states without moving its head? Well, since there are only finitely many states, the Universal Turing Machine UTM can simulate the TM and just count how many transitions the TM has made since the last head movement to the right. If this number exceeds the number of states of the TM, the TM will not terminate, so the UTM can answer 'no'.

(**) What happens if the TM just goes to the right indefinitely? Well, at some point it will exceed the word to decide and move its head to a blank cell. An easy argument is to just count from there on the number of transitions (moving right or staying with the head at the current cell). If this number is greater than the number of states of the TM, it is caught in a loop and the UTM can answer 'no'.

To sum it up: The TM in question cannot decide its language, but the UTM can, so it is decidable in the usual sense.


Is {|M prints more than 300 non-blanks on input w} decidable?

It is decidable. The decider $D$ is described as the following pseudocode by Church–Turing thesis. The syntax of the pseudocode is borrowed from Python.

configurations = [the initial confituration]
print_non_blank = []
min = 0
max = len(w) - 1
while M does not halt on w:
    simulate one step of M on w
    configuration = the current configuration
    if M prints a non-blank:
        print_non_blank.append(1)
        if sum(print_non_blank) > 300: # Check 1
            return ACCEPT

        # update the non-blank area
        p = the position where M prints the non-blank
        if p > max:
            max = p
        if p < min:
            min = p

    else:
        print_non_blank.append(0)

        # Check 2
        for i in reserved(range(len(configurations))):
            if print_non_blank[i]:
                break
            if configurations[i].head_position < min:
                if configurations[i].state == configuration.state and configuration.head_position < configurations[i].head_position:
                    return REJECT
            elif configurations[i].head_position > max:
                if configurations[i].state == configuration.state and configuration.head_position > configurations[i].head_position:
                    return REJECT
            else:
                break

    # Check 3
    for i in range(len(configurations)):
        if configurations[i] == configuration:
            if sum(print_non_blank[i:]) > 0:
                return ACCEPT
            else:
                return REJECT

return REJECT

The decider $D$ maintains an area of the tape (represented by the closed interval $[$min$, $max$]$) such that there are only blank symbols beyond the interval. We call this area non-blank area, and call the area represented by  $(-\infty,$min$)\,\cup\,($max$, +\infty)$ blank area.

In addition to count how many non-blank symbols $M$ prints (Check 1), the decider $D$ performs two additional check. Check 2 checks for the pattern where the head of $M$ wanders in the blank area without printing any non-blank symbol, then reach a position with the same state that is no closer to the non-blank area. Check 3 checks for the case where the configuration is the same as some previous one. We can assert that $M$ will loop forever in both cases and infer whether it will print more than $300$ non-blank symbols accordingly.

Now all the rest work is to show that $D$ is indeed a decider, i.e. will always halt. We prove this by contradiction. Assume $D$ does not halt for some $M$ and $w$, then $M$ does not halt on $w$ too. Also, $M$ must print finite ($\le 300$) many non-blank symbols otherwise $D$ will detect it and halt no later than the time $M$ prints the $301$th non-blank symbol. As a result, the non-blank area is always a subset of a fixed area represented by, say $[a, b]$, during the running of $D$. We call the area represented by $[a, b]$ universal non-blank area, and call the area represented by $(-\infty,a)\cup(b,+\infty)$ universal blank area. There are two cases.

There are only finite many configurations where the head of $M$ is in the universal non-blank area. This means after some step, the head of $M$ will wander in the universal blank area forever (without printing any non-blank symbol, due to the definition of universal blank area), then there must be two configurations with the same state during the wandering. Also, the head of $M$ in the later configuration must be no closer to the non-blank area, otherwise the head will finally move into the non-blank area, which contradicts to the assumption that $M$ will wander in the universal blank area forever. As a result, this case is detected by Check 2 of $D$.
There are infinite many configurations where the head of $M$ is in the universal non-blank area. In this case, there must be two same configurations, so this case is detected by Check 3 of $D$.

Hence $D$ will halt anyway.


Peaking finding when equals is taken out of the equation

I can further improve your approach - let's consider an array that has peak, but all but two elements in the array are equal. O(log n) comparisons can check only O(log n) elements, so it's not enough even to decide whether peak is in first or second half of the array.


Is data received after transmission immediately stored and can that be recovered?

Briefly, communication between two hosts/peers on a network occurs by means of network sockets. Roughly a socket is pair (IP,PORT) of numbers which uniquely identifies a host on a network. So, when a host A sends data to another host B on the network, B listens to a corresponding port for incoming data. Data (payload) comes byte-by-byte and when one byte of data riches destination B gets notification. At this point it is up to the application what to do with data: to store it on the hard drive or in memory. Nothing is stored in HDD or on some other device by default.

As for "sending an essay to a server" your are talking about file transfer protocols, in particular file uploads. Whether your file was stored on the server depends on the underlying protocol. For example recently people have started talking about resumable file upload protocol.

Your questions say that you should start learning from basic TCP/IP and HTTP protocols, and move towards more advanced and specific protocols depending on your tasks.


How are codes like 5421 and 2421 unique?

Codes like 5421 and 2421 are not unique, and this is one of their advantages. For example, 2421 is self-complementing: computing the 9-complement of a digit is the same as negating its bits. In textbooks you can find tables in which the authors choose one possible code for each digit, but this choice is arbitrary, and you might find different choices in different textbooks.

Let me also mention that BCD has been gradually losing favor, and I expect only old hardware to use anything other than 8421 (if at all). Most of the interest in BCD is historical, since modern architectures don't use BCD. I suspect that material about BCD is there mostly because of inertia, though BCD might still be used in conservative industries such as banking.


What does this performance formula mean?

Just break it down into parts:

  $  \{ f(l) \mid l = 1,...,K \} $

This is a simple set construction. The above would simply create a set with all the elements from 1 to K. In your case the f(l) is the function:

  $ ||X_i-C_l||^2 $

Given the || means the norm, these are vectors you are subtracting (rows of the X and C matrices). So subtract the vectors, take the norm, and square it. That produces a new set, of which you want to take the minimum.

  $ \sum\limits_{i=1}^n $

This part is then just the sum of above min calculation for every index $i$ from $1$ to $n$.


Why is writing down mathematical proofs more fault-proof than writing computer code?

Let me offer one reason and one misconception as an answer to your question.

The main reason that it is easier to write (seemingly) correct mathematical proofs is that they are written at a very high level. Suppose that you could write a program like this:

function MaximumWindow(A, n, w):
    using a sliding window, calculate (in O(n)) the sums of all length-w windows
    return the maximum sum (be smart and use only O(1) memory)

It would be much harder to go wrong when programming this way, since the specification of the program is much more succinct than its implementation. Indeed, every programmer who tries to convert pseudocode to code, especially to efficient code, encounters this large chasm between the idea of an algorithm and its implementation details. Mathematical proofs concentrate more on the ideas and less on the detail.

The real counterpart of code for mathematical proofs is computer-aided proofs. These are much harder to develop than the usual textual proofs, and one often discovers various hidden corners which are "obvious" to the reader (who usually doesn't even notice them), but not so obvious to the computer. Also, since the computer can only fill in relatively small gaps at present, the proofs must be elaborated to such a level that a human reading them will miss the forest for the trees.

An important misconception is that mathematical proofs are often correct. In fact, this is probably rather optimistic. It is very hard to write complicated proofs without mistakes, and papers often contain errors. Perhaps the most celebrated recent cases are Wiles' first attempt at (a special case of) the modularity theorem (which implies Fermat's last theorem), and various gaps in the classification of finite simple groups, including some 1000+ pages on quasithin groups which were written 20 years after the classification was supposedly finished.

A mistake in a paper of Voevodsky made him doubt written proofs so much that he started developing homotopy type theory, a logical framework useful for developing homotopy theory formally, and henceforth used a computer to verify all his subsequent work (at least according to his own admission). While this is an extreme (and at present, impractical) position, it is still the case that when using a result, one ought to go over the proof and check whether it is correct. In my area there are a few papers which are known to be wrong but have never been retracted, whose status is relayed from mouth to ear among experts.


Turing machine and coming up with an idea

Just to expand the comments above, you should try to find a high level algorithm, and then refine its steps in smaller pieces.

For example, if you want to recognize palindrome words, a high level agorithm can be:

1. check if the leftmost symbol is equal to the rightmost symbol
2. if they are not equal reject, otherwise delete them
3. if there are other symbols then goto 1, otherwise accept

That can be refined in the following way:

1.1 move the head on the leftmost symbol
1.2 "store" its value
1.3 if it is the only symbol left then accept (w has an odd length)
1.4 otherwise move the head to the rightmost symbol
2.1 compare it to the "stored" one
2.2 if they are not equal halt and reject, otherwise
2.3 delete the rightmost symbol
2.4 move the head to the leftmost symbol
3.1 delete it
3.2 if the tape is empty halt and accept, otherwise
3.3 goto 1.1

The steps are "implemented" using the internal states of the Turing machine.
While designing the Turing machine you can name the states with labels instead of "q0, q1, q2" to make the design process easier.

If you have a single tape Turing machine, the step [1.2 "store" its value] means that you must use the internal states to "remember" the symbol read while the head moves to the rightmost one.

Suppose you have two input symbols $a,b$ and $-$ is the blank symbol, then you can use a set of states La,L'a,CMPa and Lb,L'b,CMPb to represent (store) the leftmost symbol read; so steps 1.1, 1.2, 1.3, 1.4, 2.1, can be implemented in this way:

     |  a      |   b     |   -
START| a,R,La  | b,R,Lb  | -,R,START << move right until you find a symbol
La   | a,R,L'a | b,R,L'a | ACCEPT    << step 1.3
Lb   | a,R,L'b | b,R,L'b | ACCEPT    << step 1.3
L'a  | a,R,L'a | b,R,L'a | -,L,CMPa  << step 1.4
L'b  | a,R,L'b | b,R,L'b | -,L,CMPb  << step 1.4
CMPa | -,L,MVL | REJECT  |           << compare to a
CMPb | REJECT  | -,L,MVL |           << compare to b
MVL  | .......                       << move left

As you can see after reading the leftmost symbol the states are doubled:

Lx we are on the first symbol after the leftmost one (which is symbol x)
L'x we are moving rightward from the leftmost symbol x
CMPx we are comparing the rightmost symbol with the leftmost symbol x


Prove $\{a^ib^i\mid i\ge0\}$ is not regular using the pumping lemma

By the pumping lemma $a^n b^n$ can be written as $xyz$ with $|xy| \le n$ and $|y| \ge 1$ in a way that ensures that $xy^kz \in L$ for any $k \ge 0$.
Picking $k=0$, this implies that $xz \in L$.
Since this is not the case for your language $L$, you know that $L$ cannot be regular.


Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S) = \epsilon (\epsilon (S))$

Your definition of $\epsilon$-closure is quite problematic. Here is a better formulation:

  $\epsilon(S)$ is the intersection of all sets $T \subseteq Q$ such that (i) $T \supseteq S$ and (ii) if $q \in T$ then $\delta(q,\epsilon) \subseteq T$.

Here is a series of claims which imply $\epsilon(S) = \epsilon(\epsilon(S))$.

Claim 1. $\epsilon(S) \supseteq S$.

Proof. $\epsilon(S)$ is the intersection of sets containing $S$, and so contains $S$.

Claim 2. If $q \in \epsilon(S)$ then $\delta(q,\epsilon) \subseteq \epsilon(S)$.

Proof. If $q \in \epsilon(S)$ then $q$ belongs to all sets $T$ in the definition. Property (ii) implies that all of these sets contain $\delta(q,\epsilon)$, and so $\epsilon(S)$ contains $\delta(q,\epsilon)$.

Claim 3. $\epsilon(\epsilon(S)) \supseteq \epsilon(S)$.

Proof. Follows directly from Claim 1.

Claim 4. $\epsilon(\epsilon(S)) \subseteq \epsilon(S)$.

Proof. $\epsilon(S)$ satisfies the $T$-conditions for $\epsilon(S)$: (i) is trivial, and (ii) follows from Claim 2.

Claim 5. $\epsilon(\epsilon(S)) = \epsilon(S)$.

Proof. Follows from Claim 3 and Claim 4.


They are two different definitions.
The interview definition calls a safe edge one that is not part of any cycle and therefore cannot be removed from $G$ without disconnecting it, thus changing the resulting MST.
Notice that this definition depends solely on the chosen edge and on $G$. Notice also that it does not depend on the edge weights in any way.
The definition in the notes defines a safe edge $e$ as one that can safely be added to a subgraph $A$ of $G$ so that $A + e$ is a partial MST of $G$.
In this case $A$ is probably thought to already be a partial MST of $G$, since otherwise no edge would be safe, although this is not formally required.
Notice that this definition depends on the particular choice of $A$ and on the edge weights of $G$.
As an example, let $G$ be a cycle on $n$ nodes, where the $n$ edges have weights $1, \dots, n$. None of these edges is safe according to the interview definition.
If $A$ is the empty graph then all edges except for the one of weight $n$ are safe w.r.t. the definition in the notes.
If $A$ is the subgraph containing the edge of weight $n$ then no edge is safe w.r.t. the definition in the notes.


What is the formal way to prove this is still a minimum spanning tree?

For part (1), denote by $w$ the weight of a tree in the original tree, and by $w'$ its weight in the new tree. Since $T$ is an MST, we have $w(T) \leq w(T')$ for every tree $T'$. Also, $w'(T) = w(T)$ and $w'(T') \geq w(T')$ for all $T'$. Therefore $w'(T) = w(T) \leq w(T') \leq w'(T')$ for all trees $T'$, that is, $T$ is an MST with respect to $w'$ as well.

Part (2) is similar to part (1), though slightly more challenging. Suppose that we decreased the weight on an edge in $T$ by an amount $\delta$. Then $w'(T) = w(T) - \delta$, and $w'(T') \geq w(T') - \delta$ for every tree $T'$. Therefore $w'(T) = w(T) - \delta \leq w(T') - \delta \leq w'(T')$ for every tree $T'$, and so $T$ is an MST with respect to $w'$ as well.

I couldn't quite understand part (3), but I think you've seen enough examples of how these proofs go.


SMT solves with functions for free varibles

SMT solvers do support uninterpreted-functions as part of many logics. If there's a counter-example, then they will also print a "counter-example" function, which will be the predicate you're looking for. If you have a concrete example, we can surely see if one can be coded up using Z3.


Is there a way to incrementally degrade the quality of a PRNG?

There are many possible ways to degrade its output, but here is one simple choice:

Think of your PRNG as outputting a sequence of bits.  For a good PRNG, each bit would be uniformly distributed (equally likely to be 0 or 1), independent of the previous bits.  We can build a degraded PRNG where each bit of the output is 1 with probability $p$ or 0 with probability $1-p$, independent of all of the previous bits.  This gives us a parameter $p$ that can be varied from $1/2$ down to $0$: with $p=1/2$, there's no degradation, and smaller values of $p$ correspond to increasing amounts of degradation.  Effectively, $p$ is a tuning knob that allows us to control the amount of degradation.

From this, you can derive a way to get other quantities.  If you want a 32-bit integer, you generate each of its bits using this degraded PRNG.  etc.

This model has some nice properties.  For instance, if you generate a random $k$-bit value using your degraded PRNG, the resulting value will have $k h_2(p)$ bits of entropy.  This varies from $k$ bits smoothly down to $0$ bits as $p$ varies from $p=1/2$ down to $p=0$.  As a very crude approximation, the $k$-bit value will be approximately uniformly distributed on a set of size $2^{k h_2(p)}$; as $p$ gets smaller (as you introduce more degradation), the size of this set gets smaller smoothly.

Of course, we can't tell you whether this is the "right" degradation model for your particular application, as that will depend on your particular application.  There are many other possible ways of degrading a PRNG's output, and since we haven't been given any specific criteria for selecting among them, I have semi-arbitrarily chosen one that is especially simple to implement and simple to think about.


Regular expression (ab U a)* to NFA with two states (Sipser)?

Mouse-over the yellow box to see an NFA that accepts the language.


A comparison with a result "different" doesn't add information regarding any other sock in the pile (If sock B didn't match A, and Sock C didn't match A, the chance of B and C  to be a match is still the same as with any other sock). therefor no sorting or organization can be made, rather then knowing for each sock which socks don't match it based on this comparison. this leads back to the naive algorithm, which is $O(n^2)$.

Pretty disappointing...


An example of a context-sensitive grammar for a given language

Your request is easily served!

$$\begin{array}{lcl}
   &S  &\to &abab\\
   &ba &\to &bbBa\\
   &Ba &\to &aB\\
   &Bb &\to &bb\\
   &ba &\to &bAaa\\
   &bA &\to &Ab\\
   &aA &\to &aa\\
\end{array}$$

There is some theory to help you make sense of this solution.

Let us first consider a simpler language that manifests the same difficulty: $L = \{a^nb^ma^n ∣
n,m \ge 1\}$. Imagine it as a sea of $b$ between the shores of $a$, if you please.

We would like to grow the shores so that they are always the same size. One immediate way is to
have a collection of rules like $a + b^m + a \to aa + b^m + aa $. But we see it will not serve our
needs, as, our collection being finite (grammars are required to have a finite set of rules),
there is always some choice of $m$ that is not accomodated. So evidently there is a trick.

The trick is to introduce a non-terminal "ship" that will sail across the sea and deliver the
information from one shore to the other. When the left shore grows, it will send a ship to the
right shore, and when the right shore receives a ship, it will also grow, thus maintaining the
required equilibrium. How can we sail a ship? $Ba \to aB$ is one way to move it one unit of sea
rightwards. What remains to be put in place is a shipyard $ba \to bbBa$ and a port $Bb \to bb$.

Here is what we get:

$$\begin{array}{lcl}
   &S  &\to &bab\\
   &ba &\to &bbBa\\
   &Ba &\to &aB\\
   &Bb &\to &bb\\
\end{array}$$

I am sure you can see how to extend this to your original language: you will need the sea
people to also send some sort of messenger golems $A$ across the land to the sea on the other side of
$b$.

Happy adventures in fantasy grammar land!


Showing $1$-reducibility of $\overline{\text{HALT}'}$ to index set

Let $e$ be and index for the constant 0 function. Then consider $s$ such that

$$ \varphi_{s(x)}(y) = \begin{cases} 0 & \mbox{ if }\varphi_x(x) \mbox{ does not halt within $y$ steps} \\ 1 & \mbox{otherwise} \end{cases} $$

Then $\varphi_{s(x)} = \varphi_e$ if and only if $x \not\in HALT$ (assuming HALT was the diagonal halting problem).

The function $s$ can be choosed to be monotonic (use pumping), hence it is one-to-one.


What can be said about the given language?

The words in the first part start with $ab$, those in the second part start with $aa$.

That should help.


Those are my lecture slides, so I figured I'd chime in. :-)

The idea is to split apart the recursive calls being made into two different classes: recursive calls where the range being searched is the entire range of a node and recursive calls where the range being searched corresponds to just a part of the range. One of the observations you can make is that if you do a range search on a segment tree, after the initial split made in the recursive call, every recursive call made either spans the entire range given by a node or corresponds to a subrange that's flush up against one of the sides of the range given by a node.

As an optimization in a segment tree, any recursive call that's made for a range that completely spans a node doesn't do any further recursion; it just returns the cached value and stops. Therefore, the only recursive calls that fire off more recursive calls are ones where the range searched is flush against the side of the range spanned by a node. If you look at what happens in that case, you'll see that every recursive call made from that point either is over a full range (in which case it doesn't really count as a recursive call; we can charge that work back to the initial recursive call) or is to a flush against the side range. This means that while the recursion does indeed branch, one of those branches always immediately ends. Therefore, the work done obeys the recurrence

  T(n) = T(n / 2) + O(1)

where that O(1) term counts both the work for the recursive call and the (up to) one recursive call made on a full range, which terminates immediately. That solves to O(log n), as required.

Hope this helps!


Given any enumeration $E$ of the language, here is a way to describe a language: "the 5th language in the enumeration".

If you use that as the description, then yes, your condition is trivially true.  Given the description of a language ("the 5th language in $E$"), you can quickly find its position in $E$ (5).


Maximizing sum of ranges of vertices edges

I'll start by giving a negative example to @seteropere algorithm:

Let $G=(V,E)$, where $$V=\{x_1,x_2,x_3,y_1,y_2,y_3\}\ \ \ ,\ \ \ E=\{(x_i,y_i)\mid i\in [3]\}\cup\{(x_1,x_2),(x_1,x_3)\}$$
Let the weight collection be $\{3,3,2,1,1\}$.

The proposed algorithm starts by assigning weights $1,2$ and $3$ for $x_1$, and assume that $(x_1,y_1)$ was assigned 1.

This already means that the optimal solution profit (5, see figure) is not obtainable.

  That said, this problem is poly time solvable after all , greedily,
  but differently.

Hint: given a graph $G$ such that $\Delta(G)\geq 2$, prove that in the optimal solution there exists a vertex $v$ such that the maximal number and the minimal number are both in $w(v)$.

P.S.

The opposite problem, in which we aim to minimize $$\sum_{v \in V}{max(w(v)) - min(w(v))}$$

Is quite interesting by itself.


Can Yacc be used to generate three address code for Java 1?

A grammar's parser serves to recognize the language generated. Tools like YACC augment the parser to (essentially) trace a parse tree (some automatically build an AST, abstract syntax tree) for the parsed string according to the grammar. You can then walk this structure to generate code. But that is a separate task, that commonly uses different tools.


Given an algorithm, is it possible to find all other equivalent algorithms for the same computable function in the same model

Interpreting your problem as finding a computable $f$ such that $f\big(\langle M\rangle\big)=\langle M'\rangle$ with the property that $M'$ enumerates all programs equivalent to $M$, i.e. all $M''$ with $L(M'')=L(M)$, the answer is no (such $f$ does not exist).
One way to show this is to observe that such $f$ would place the language $\left\{\big(\langle M_1\rangle, \langle M_2\rangle\big) \big| \; L(M_1)=L(M_2)\right\}$ in $RE$, while it is known that this language is $\Pi_2$ complete and thus not in $RE$. You could formulate this relative to any admissible numbering, and not necessarily in the language of Turing machines.


Given regular grammars (each is either left or right linear), does exist word/string so it can be derived from all regular grammars?

Your problem is PSPACE-complete. Indeed, the easier problem of DFA intersection is already PSPACE-complete, see for example Descriptional and computational complexity of finite automata—A survey by Holzer and Kutrib. For comparable results from the point of view of exponential time algorithms, see Problems on Finite automata and the exponential time hypothesis by Fernau and Krebs.

It is well-known that regular grammars are essentially equivalent in power to NFAs (even considering description complexity), and for this reason your problem is essentially equivalent to the NFA intersection problem, in which you are given a collection of NFAs and have to decide whether the intersection of languages accepted by them is empty — this is the problem considered in the papers above.

The same problem for regular expressions is also PSPACE-complete, see for example Complexity of decision problems for simple
regular expressions by Martens, Neven and Schwentick, which considers restricted cases of the problem.


Existence of functions that only tests memberships without revealing any information about the members

Yes.  This is known as the problem of obfuscating a point function.  There are standard schemes.  See, e.g., the following papers:

On Obfuscating Point Functions.  Hoeteck Wee.  STOC 2005.

Technically, a point function is a function $f_s(x)$ given by $f_s(x)=1$ if $x=s$ and $f_s(x)=0$ for all $x \ne s$.  There are standard schemes for obfuscating point functions.  This corresponds to the special case of your problem where $n=1$ (hiding a single value $s$).  However, the techniques all generalize to arbitrary $n$, as long as the number $n$ of values is exponentially small compared to the size of the domain of the function.


minimum number of edges that should be added to an undirected graph to make it a tree

Your first guess is correct. Sometimes there is more than one way to write the same solution.
Clearly, if there are $k$ connected components you'll need exactly $k-1$ edges to connect them (without forming any cycle).
On the other hand, a tree with $n$ nodes must have exactly $n-1$ edges, so if the graph is acyclic and already has $m$ edges, then it is missing $n-1-m$ edges.
Regarding the example: the given graph has $n=10$ vertices, $m=6$ edges, and $k=4$ connected components (not 3), so the answer is $3=k-1=n-m-1$. The sets of vertices in each connected component are $\{1,2,8\}, \{3\}, \{4, 6, 10\}$, and $\{5, 7, 9\}$.


Shortest Path in a Graph with Interacting Edge Weights

It's NP-hard.

We reduce 3SAT to your problem (where $f$ is constant). Let $c_1,\dots ,c_m$ be an instance of 3SAT. Let $v_1,\dots,v_n$ be the variable in the clauses. For each clause $c_i$, call $l_{i,j}$ the $j^\text{th}$ literal of $c_i$. Now, build this graph:

(Note that we allow several edges between the two same nodes, but if you don't want to, you can just add dummy nodes)

Now, if we look at paths from $0$ to $n+m$ in this graph, clearly, they will pick a value per variable (true if it picks $v_i$ and false if it picks $\lnot v_i$), and a literal per clause. Set $f:=e\mapsto 1$ to be constant. Now set $g((l,c),l)=1$ and $g(e,e')=0$ in all other cases, i.e. reward taking a literal in a clause that's been made true by the valuation defined by the first $n$ edges. Note that the cost of a path from $0$ to $n+m$ is $\le n$ (or equivalently $=n$) if and only if the initial formula is satisfiable (because the cost due to $f$ is $n+m$ and the reward due to $g$ is the number of satisfied clauses). So the problem "Is there a path of cost $\le n$" is NP-hard.


If $\{ww^R \mid w \in L\}$ is regular, is $L$ itself regular?

Let $A = \{ww^R \mid w \in L\}$, and suppose that $A$ is regular. What can we say about $L$?
For a word $w \in \Sigma^*$, let $E(w) = \{x : wx \in A\}$. Since $A$ is regular, there are only finitely many different $E(w)$.
Say that $w \in L$ is self-terminating if it has no extension in $L$. If $w \in L$ is self-terminating then $E(w)$ is finite, and the unique longest word it contains is $w^R$. Therefore if $w_1 \neq w_2$ are both self-terminating words in $L$, then $E(w_1) \neq E(w_2)$. Consequently, there are only finitely many self-terminating words in $L$. Let $L'$ result from removing them and all their prefixes. Thus every word in $L'$ has infinitely many extensions in $L'$.
Say that $w \in L'$ is creative if there are two different letters $\sigma,\tau$ such that both $w\sigma$ and $w\tau$ have extensions in $L'$. If $w \in L'$ is creative then we can recover $w$ from $E(w)$ by taking the longest common suffix which appears infinitely often. This implies that there are only finitely many creative words in $L'$. Let $L''$ result from removing all creative words in $L'$ and their prefixes. Thus every word in $L''$ has infinitely many extensions in $L''$, and all of them are prefixes of a single $\omega$-word.
Let $x$ be an $\omega$-word that $L''$ has infinitely many prefixes of, and choose the shortest such prefix $w_x$. We can recover $x$ from $E(w_x)$ in the following way: the first $\ell$ letters of $x$ are the reverse of the suffix of length $\ell$ of all long enough words in $E(w_x)$. It follows that $L''$ consists of prefixes of finitely many $\omega$-words.
Let $x$ be one such $\omega$-word. By the pigeonhole principle, there exist $n_1 < n_2$ such that $x_1 \ldots x_{n_1},x_1 \ldots x_{n_2} \in L$ and $E(x_1 \ldots x_{n_1}) = E(x_1 \ldots x_{n_2})$. Since all long enough words in the former start with $x_{n_1+1} \ldots x_{n_2}$, it follows that $x_{n_2+1} \ldots x_{n_2+(n_2-n_1)} = x_{n_1+1} \ldots x_{n_2}$, and continuing in this way, we see that $x$ is eventually periodic, say $x=yz^\omega$.
The number of words of given length in a regular language is eventually periodic. It follows that we can modify $L''$ to another language $L'''$, differing in finitely many words, such that $L'''$ also consists of prefixes of finitely many $\omega$-words, and furthermore there exists a modulus $m$ such that for each $a \in \{0,\ldots,m-1\}$ and each $\omega$-word, either all prefixes of length $nm+a$ are in $L'''$, or none of them. Up to finitely many words, for each $\omega$-word $x = yz^\omega$, these prefixes are of the form $y' (z')^*$.
Every two $\omega$-words in $L'''$ differ in some symbol. It follows that for each such word $x$, and for each $a$, we can use regular closure operations to isolate the corresponding subset of $A$, which is of the form
$$ \{ ww^R \mid w \in y z^* \} = \{ y z^n (z^R)^n y^R \mid n \geq 0 \}. $$
We can further use regular closure operations to isolate
$$ \{ z^n (z^R)^n \geq 0 \}. $$
Applying the pigeonhole principle to the sets $E'(z^n)$ (where $E'$ is the analog of $E$ to the new language), we see that $E'(z^{n_1}) = E'(z^{n_2})$ for some $n_1 < n_2$. Since $(z^R)^{n_1} \in E'(z^{n_1}) = E'(z^{n_2})$, it follows that $z^{n_2}(z^R)^{n_1} = z^{n_1} (z^R)^{n_2}$, and so $z = z^R$.
We conclude that there exist $a,b \in \mathbb{N}$, words $w_1,\ldots,w_a,y_1,\ldots,y_b$, and palindromes $z_1,\ldots,z_b$, such that
$$
L = \sum_{i=1}^a w_i + \sum_{j=1}^b y_j z_j^*.
$$
The corresponding language $A$ is
$$
A = \sum_{i=1}^a w_i w_i^R + \sum_{j=1}^b y_j (z_j z_j)^* y_j^R.
$$


determining timeouts / retry attempts in distributed systems

The simplest solution I have found to this problem is using rolling percentile latency. The optimal timeout will shift based on hardware, network configuration and the state of the operating system. Therefore it cannot be fixed/established beforehand, but approximated at runtime. The typical practice in industry is to maintain P95 and P99 response times. These are durations in which 95% and 99% of requests complete respectively over some time duration. So you could perhaps store the last hour of request times, and if the current request is longer than 95% of the others in the last rolling 60 minutes, then you deem that a timeout.
This will adapt and gradually become more strict if response times are fast, and more lenient if they become slow.
You can read more about percentile latency here.


Doubt on declaring an array in pseudocode

Pseudocode is not a formally defined programming language. Rather, it refers to textual description of code that is not in "paragraph" form but rather in "code" form. (Paraphrasing Molière, it is a third form of expression, after prose and poetry.)

The only rule in pseudocode is that it should be self-explanatory. If there is anything that the reader might misunderstand, you have to explain it. Otherwise, it's up to you how you write pseudocode, though it's good measure to be consistent in your paper.

Your pseudocode is self-explanatory. You have declared a variable "number" of type integer, printer "Enter a number", read a number from the input into "number", and then declared an integer array "randomarray" of length "number". Moreover, your array is "1-based" (i.e., the first index is 1). If this is what you intended to convey, then you were successful and there is nothing wrong with your pseudocode.

It's good practice to try to emulate the way other people in your field write pseudocode. This will cause your code to look more "standard", and so more "professional" and easier to read. But it's definitely not necessary, and you are encouraged to write the pseudocode in whatever way seems best or nicest to you.


Complexity of CFG grammar for a regular language

A regular grammar is context-free. So regular languages are
context-free.

Every regular language has a right regular grammar, which is simply derived from a finaite state automaton for that language.

Every regular language can be recognized by a deterministic finite state au tomaton. From that deterministic FSA you can construct a right regular grammar
which is LL(1) since you can decide what to do for
parsing by simply looking at the terminal on the rules applicable at any time. There always is only one such rule. Actually you do
not even need the pushdown, and use the non-terminal for the states.
(this is a bit informal, but it is so simple being formal seems
silly).

The key part is producing the deterministic FSA.

So, yes, every regular language can be generated by a LL(1) grammar.

A LL(1) grammar is always unambiguous, as it allows constructing a
deterministic push-down automaton. So it is unnecessary to specify
that it is unambiguous.

As for your language, it seems strangely defined, and I wonder whether
you copied that correctly. What is the "$+$" supposed to mean ?


What is the name for polynomially solvable optimisation problems?

An optimization problem is an example of a function problem: i.e., one where the task is to map some input to some output.  The class of function problems solvable in polynomial time is FP. See, for example, the Complexity Zoo.

(Note that there is a class OptP but that's not the polynomial-time optimization problems. Perhaps confusingly, it's the optimization analogue of NP: it's the class of functions that can be defined by taking the maximum out the outputs given by accepting paths of a nondeterministic polynomial-time Turing machine.)


Let's go over your questions one by one:

(1) Your definition of Unique cover is wrong. Given a set system $\mathcal{S}$, the goal is to find a subset $\mathcal{S}' \subseteq \mathcal{S}$ which uniquely covers the most elements. The subset $\mathcal{S}'$ uniquely covers an element $x$ if $x$ belongs to exactly one set in $\mathcal{S}'$.

(2) Exact cover is a decision problem, whereas Unique cover is an optimization problem. The decision version of Unique cover goes as follows:

  Given a set system and an integer $k$, is there a subset of the set system which uniquely covers at least $k$ elements?

Exact cover is a special case of the decision version of Unique cover.

(3) The sets $S_3$ and $S_4$ together cover $6$ elements once ($1,2,4,5,7,8$). Since $6 > 4$, it is better to take both $S_3$ and $S_4$ rather than any of them individually.

(4) The probability is that of choosing any given set. I suggest you look for more material on probability theory and on randomized algorithms, and after that come back and see if it makes sense.

(5) This is explained very clearly in various lecture notes. There is no point repeating the explanation here. I suggest you learn probability theory and randomized algorithms from scratch, and then attempt to read the $O(\log n)$ analysis again. It might take a few weeks, but without catching up on the basics you have no chance of understanding anything which is even slightly advanced.


Is the halting problem undecidable or unrecognizable?

Encode a Turing machine $M$ and an input string $I$ into a single string $(M,I)$. Create a Turing machine $U$ that behaves as follows:

$U$ rejects any input that is not a valid encoding
When given valid input $(M,I)$, $U$ emulates the behavior of $M$ with input $I$
If $M$ eventually halts when given input $I$ then $U$ halts and accepts input $(M,I)$

If $M$ eventually halts when given input $I$ then $U$ will (eventually) accept input $(M,I)$. So $U$ recognizes the language

$L=\{(M,I) : M \text{ eventually halts when given input } I \}$

Note, however, that $U$ does not decide $L$ because it does not explicitly reject $(M,I)$ if $M$ never halts given input $I$ - in this case $U$ will also never halt when given input $(M,I)$.

The Halting Theorem tells us that $L$ is undecideable (over Turing machines) but we have just shown that $L$ is recognizeable.


Is it a problem to be a programmer with no knowledge about computational complexity?

Yes, I would say knowing something about computational complexity is a must for any serious programmer. So long as you are not dealing with huge data sets you will be fine not knowing complexity, but if you want to write a program that tackles serious problems you need it.

In your specific case, your example of finding connected components might have worked for graphs of up to say $100$ nodes. However, if you tried a graph with $100.000$ nodes then your lecturer's algorithm would probably have managed that in 1 second, while your algorithm would have (depending on how bad the complexity was) taken 1 hour, 1 day, or maybe even 1 eternity.

A somewhat common mistake students make in our algorithms course is to iterate over an array like this:

while array not empty
    examine first element of array
    remove first element from array

This might not be the most beautiful code but in a complicated program something like this might show up without the programmer being aware of it. Now, what is the problem with this program?

Suppose we run it on a data set of $100.000$ elements. Compared to the following program, the former program will run $50.000$ slower.

while array not empty
    examine last element of array
    remove last element from array

I hope you agree that having the knowledge to make your program run $50.000$ times faster is probably an important thing for a programmer. Understanding the difference between the two programs requires some basic knowledge about complexity theory and some knowledge about the particulars of the language you are programming in.

In my pseudocode language, "removing an element from an array" shifts all the elements to the right of the element being removed one position from the left. This makes removing the last element an $O(1)$ operation since in order to do that we only need to interact with 1 element. Removing the first element is $O(n)$ since in order to remove the first element we need to shift all the other $n-1$ elements one position to the left as well.

A very basic exercise in complexity is to prove that the first program will do $\frac{1}{2}n^2$ operations while the second program uses only $n$ operations. If you plug in $n=100.000$ you will see one program is drastically more efficient than the other.

This is just a toy example but it already requires a basic understanding of complexity to tell the difference between the two programs, and if you are actually trying to debug/optimize a more complicated program that has this mistake it takes an even greater understanding to find out where the bug is. Because a mistake like removing an element from an array in this fashion can be hidden very well by abstractions in the code.

Having a good understanding of complexity also helps when comparing two approaches to solve a problem. Suppose you had come up with two different approaches to solving the connected components problem on your own: in order to decide between them it would be very useful if you could (quickly) estimate their complexity and pick the better one.


"Characterizes" means you must prove "if and only if".


FFT implementation using Danielson-Lanczos Lemma

The meaning of the first line is "Let $X$ be an array of length $m$ (with indices running from $0$ to $m-1$) such that $X_j = x_{2j}$ for $j \in \{0,\ldots,m-1\}$." The second line has a similar meaning, with $Y_j = x_{2j+1}$ instead.


Complexity of $O(\log(n^n))$ vs $O(\log(n!))$

$O(\log n^n)$ and $O(\log n!)$ both describe the same set of functions.

Notice that $( \frac{n}{e} )^n \le n! \le n^n$ and hence:

$O(n \log n)  = O(n \log \frac{n}{e}) = O( \log ( \frac{n}{e} )^n) \subseteq O(\log n!) \subseteq O(\log n^n) = O(n \log n)$.

This shows that all the above sets coincide.


Balance factor changes after local rotations in AVL tree

I found the answer myself.
We know that
$$b(x)=b(x')+b(y)[b(y)>0]+1$$
$$b(y′)=b(x)+b(y)[b(y)\le0]−b(x′)[b(x′)>0]−2$$
thus
$$b(y′)=b(x')+b(y)[b(y)>0]+1+b(y)[b(y)\le0]−b(x′)[b(x′)>0]−2$$
where
$$b(x')−b(x′)[b(x′)>0]=b(x')[b(x')\le0].$$
So, the new balance factors will look like this:
$$b(y′)=b(y)+b(x')[b(x')\le0]−1$$
$$b(x′)=b(x)−b(y)[b(y)>0]−1$$


Proving algorithm for removing nodes from a complete graph with two kinds of edges

A complete graph with red and black edges is just an unnecessarily complicated way of describing an arbitrary graph (where black edges correspond to neighbors and red edges to non-neighbors).

Effectively, given a graph $G$ you are looking for a subset of the vertices that is both a clique and a vertex cover.

Restating the problem like this, it is easier to see that your arguments are correct: in a graph with no isolated vertices, if there is more than one connected component (in an undirected graph every connected component is also strongly connected so stating "strongly connected" is redundant) then clearly there is no clique that covers both components.

Let $\Delta$ be the maximum degree of the graph $G=(V,E)$ and let $v$ be a degree-$\Delta$ vertex. Suppose there is a valid solution $S\subseteq V$ that does not contain $v$, then this solution must contain all of $v$'s neighbors. Suppose $S$ can not be extended to a valid solution by adding $v$, then $S$ contains some vertex not adjacent to $v$, thus the graph restricted to $S$ is a clique of size least $\Delta+1$ in which all vertices have degree at least $\Delta$. However, then the graph restricted to $S\cup{v}$ has a vertex of degree at least $\Delta+1$, contradicting that $\Delta$ is the maximum degree. Thus if a valid solution exists then this solution remains valid when adding a maximum-degree vertex.

So the algorithm can be restated in much simpler terms: take all maximum-degree vertices, and check that they are a valid solution.


An example where Knuth-Morris-Pratt Algorithm is faster than Boyer-Moore?

There is a paper that did a good experiment over these string matching algorithms for different patterns:
"Comparison of string matching algorithms: an aid to information content security"

Also there is a study of these string matching algorithms for Japanese language:
Comparison and Improvement of String Matching Algorithms For Japanese Texts

I hope these are useful to get a sense about algorithms efficiency!


The only thing you are missing is the importance of the interconnect between cores/processors/racks and the design of the memory system for each processor.

I assume you are referring to the most recent top-500 supercomputer list.  That list is sorted by Rmax, not Rpeak.

Rpeak is a measure of the theoretical maximum number of floating point operations that the system can perform.  For Rpeak you are correct: just add more cores (or more vector units per core) and the Rpeak number will go up.

Rmax is (arguably) a little bit more meaningful.  It is the maximal rate at which the system can run the Linpack benchmark.  The Linpack benchmark requires the system to solve a huge, dense, system of linear equations using LU factorization with partial pivoting in double precision.

For solving a dense system of linear equations you need to carefully partition the problem among the cores, and there needs to be an efficient way for the cores to communicate results back and forth.  So a big part of designing a computer that will get onto the Top500 list is careful design of the interconnect and the software used to send messages between processors.

On the top500 list they tell you what interconnect each system is using. Note that you don't find a system with Ethernet until you get to number 49.  The first 48 all have infiniband, cray gemini or custom interconnects.

There is also a green500 list that measures the MFLOPS/Watt of systems while solving the Linpack benchmark.  The difference between the top system and the 500th system on that list (from last November) is a factor of 75x.

Most people agree that there is a lot more that you want from a supercomputer in addition to being able to efficiently solve massive dense systems of linear equations.  Jack Dongara (who originated the Linpack benchmark) has recently released a paper proposing a new benchmark that measures the speed at which a system can solve a sparse linear system.  http://www.netlib.org/utk/people/JackDongarra/PAPERS/HPCG-Benchmark-utk.pdf.


Compute square root using (bit) additions and shifts as primitives

An iterative algorithm seems like it should work.

Let $M=\lfloor N/4 \rfloor$.  Suppose we know that $x$ is the integer approximation to $\sqrt{M}$, i.e., $x=\lceil \sqrt{M} \rceil$, and suppose we know the value of $x^2$ (obtained previously).

Now we want to find $y=\lceil \sqrt{N} \rceil$.  What are the possible values of $y$?  I'm pretty sure the only possible values are $y=2x$ or $y=2x+1$.   And, it's easy to try both of them and see which is correct.  In particular, for $y=2x$, we have $y^2=4x^2$, which can be obtained from $x^2$ by two left-shifts ($O(1)$ time); for $y=2x+1$, we have $y^2=4x^2+4x+1$, which can be obtained from $x^2$ and $x$ with four left-shifts and two additions ($O(1)$ time).  Now just compare those two values to $N$ to see which one is correct.

In this way, we get an iterative algorithm where we do $n/2$ iterations, and where each iteration takes $O(1)$ time.  The total running time is $O(n)$, as required.

I realize this didn't use binary search.  Oh well.


There are two typos in their algorithm.  Fixing them yields an algorithm that does work.  Here's the fixed algorithm:

Algorithm $A$, with input $x$:
 1. $c := \max(||x||_1 - \lambda,0)$
 2. $d := ||x||_0$
 3. $\tau := c/d$
 4. for each non-zero element $i$ of $x$, do:
 5.     $\qquad s := \text{sign}(x_i)$
 6.     $\qquad x_i := s \times \max(x_i - \tau,0)$
 7. return $x$

The first typo was in line 1: $\lambda - ||x||_1$ should have been $||x||_1 - \lambda$.

The second typo was in line 6: $|x_i - \tau|$ should have been $x_i - \tau$ (no absolute value).

With these changes, everything makes sense and the algorithm now seems to work correctly.  For instance:

If $||x||_1 \le \lambda$, then $A(x)=x$ (since $c=0$ in this case).
If $||x||_1 > \lambda$, then $\lambda \le ||A(x)||_1 < ||x||_1$ (since each $x_i$ gets mapped to something whose absolute value is smaller).
The sequence $x,A(x),A(A(x)),\dots$ converges to the desired $y$.
Convergence should typically be pretty fast.  In particular, if $\max_i |x_i|$ is not too much larger than $\lambda / ||x||_0$, then this procedure should converge exponentially fast.

(There are definitely some bad cases where this procedure converges very slowly: e.g., if $x$ has many elements whose absolute value is tiny but non-zero, and a single element whose absolute value is enormous.  In this case, the algorithm still converges, but it requires $\Theta(||x||_0)$ iterations, which might be as bad as $\Theta(d)$.  However, these bad cases are pretty rare.)


Your proof is unfortunately wrong. Consider what happens when $I_1 = I_2$, for example.

The essential reason behind the statement is the following more general fact:

  Any subset of an independent set is an independent set.

You can try proving this rigorously.


It seems that a bunch of different things are being conflated here:

Bits in an addressable memory location - 16 in this example.
Addressable memory locations - 1M = 2^20 in this example.
CPU word size

These can all be the same, or they can be entirely different. I will try to explain the differences:

1 - Bits in an addressable word. This can be ANYTHING. Typically this will be the same as the CPU word size - e.g., 32-bits for a 32-bit processor. However, it can be larger (e.g., direct access to a "double word") or smaller (e.g., individual byte access for a CPU that has a 16-bit or larger word size). On some CPUs there will be different instructions that use different size operands and addressing schemes - e.g., floating point instructions might work only on 32-bit ("single word") or 64-bit ("double word") memory locations but other instructions might work with individual bytes. In some designs, every byte can be addressed and accessed directly but 16-bit words only on even addresses (or 32-bit only on addresses divisible by 4).

2 - Addressable memory locations. Historically this was often double the addressable memory location size. For example, a typical 8-bit CPU such as the Z80 or 6502 could directly address 64k = 2^16 memory locations. However, there are quite a few variations. One significant one is a segmented memory addressing scheme such as that used by the 8086 family. This is one method of expanding the total addressable memory while keeping the addresses directly used by most instructions to a smaller size (16-bit in the case of the 8086). While there is some logic to keeping the address size (=# of addressable memory locations) the same as the CPU word size, in many (most?) CPU architectures that was simply not practical in many cases until we arrived at the era of affordable 64-bit CPUs.

3 - CPU word size. The CPU word size normally refers to the standard chunks of memory operated on and produced as results by individual CPU instructions. Another way of looking at it is the register size. However, there have been exceptions here as well. For example, the 8-bit 8080 has 7 8-bit registers and 2 16-bit registers (SP and PC - both needed to be 16-bit to match the memory address size) and some of the 8-bit registers could be used in pairs for operations that really operated on 16 bit values. Similarly, many 16-bit CPUs have some instructions that operate on 32-bit quantities either for floating point arithmetic or again for memory addressing.

Now that I've rambled on a bit (pun intended), back to the original question: 1M = 2^20, while the max number of memory locations for 16 bits is 2^16. How could there be a memory size of 1M x 16?
A few possibilities come to mind:

16-bit CPU with memory locations 16-bits wide and a 20-bit segmented architecture like the 8086. (But not actually the 8086 as the 8086 address space was 1M x 8)
16-bit CPU with a 20-bit or larger (typically 31-bit or 32-bit) total word-addressable memory with the 1M being just a small portion of the potential addressable memory for that particular CPU.
16-bit CPU with 21-bit or larger (typically 31-bit or 32-bit) total byte-addressable memory with the 1M just being a small portion of the potential addressable memory for that particular CPU.
32-bit CPU with memory addressable in 16-bit words (i.e., 1/2 the native CPU word size) for better performance with instructions that don't need 32-bit words.

In case it isn't already clear, the CPU word size historically directly translated to the number of pins available for reading/writing memory. So an 8-bit CPU could interface with memory 8-bits at a time and a 16-bit CPU 16-bits at a time. That all changed famously with the 8088 which internally was a 16-bit CPU but externally only 8-bits. So while the 8086 could directly use 16-bit wide memory like the example 1M x 16, the 8088 could not. That difference gives the 8088 performance that is in some ways closer to an 8-bit CPU than a 16-bit CPU.


VAR autoincrement with constant space consumption for super large tables

If you want an ID (i.e. unique label, whether number or not) which is stored as a binary (or $k$-ary) string you will have at least logarithmic growth, because with $o(\log n)$ bits you can't identify more than $k^{o(\log n)}=o(n)$ objects. So you can't do much better.

You could however map the old IDs to new IDs every time the size of the table doubles. If the entry #$2^m$ is inserted, the old IDs become $\mathrm{id}'=2^{m+1}+\mathrm{id}$ and the younger elements get shorter IDs. This only works if you don't use the IDs elsewhere (major drawback for a PRIMARY) and you have a reason to believe that newer entries get requested more often than older ones.

Finally one may ask whether you really need big integers for some kind of ID. According to this there are $\approx 10^{80}\leq 2^{267}$ atoms in the observable universe, so a kilobit sized ID will do for most purposes.


It depends on what you call "without communicating". How does B know that A really exists ? Either B speaks to A, or C tells to B that A exists, and B trusts C.

So, if a trusted C exists, C may provide to B a key to authenticate A. If a trusted C doesn't exist, B can't know if A exist, and authenticate its messages makes no sense.


Rice's Theorem just says it's undecidable. Some undecidable languages are semi-decidable; some (almost all, in fact) of them aren't.


complexity of determining whether a language given by context free grammar is empty

First, omit all terminal symbols. Then the language is empty iff the grammar does not generate the empty string.

An algorithm to check acceptance of the empty string is straightforward. A non-terminal $A$ is nullable, i.e., $A\Rightarrow^* \lambda$ iff $A \to w$ where each symbol in $w$ is nullable.

Determine the symbols nullable with a derivation tree of depth $k$, $k=0,1,\dots$. First find all $A$ such that $A\to \lambda$. Remove these $A$ from the right-hand side of productions and repeat. Axiom $S$ is nullable iff the language is non-empty.
This can be implemented in linear time, making lists of all productions that contain a certain letter at their right-hand side.

Seems to be equivalent to HORN-SAT.


How to prove that BFS directed-graph traversal algorithm terminates?

The only potentially non-terminating construct used here is the while loop. So you need to prove that Q eventually becomes empty.

Q contains vertices from the graph. The only operations that add elements to Q are the enqueue operations. Each adds a single vertex. So proving the termination of the algorithm is equivalent to proving that only a finite number of enqueue operations are performed.

The first call to enqueue at the beginning of the program adds one vertex and marks it. The second call to enqueue adds a vertex that was not marked yet, and the vertex is marked at the same time.

Since a vertex is never unmarked, the set of marked vertices can only grow.

The set of marked vertices is included in the set of all vertices. Note that the graph is be assumed to be finite (in an infinite graph, the search might not terminate). Hence there are at most $|G|$ mark operations where $|G|$ is the number of vertices in the graph. Since each enqueue operation has a corresponding mark, there are at most $|G|$ enqueue operations. Therefore there are at most $|G|$ dequeue operations. Since there is one dequeue operation at each loop iteration, there are at most $|G|$ iterations of the while loop, a finite number.


Pumping lemma for an involved non context free language

Suppose that $C$ were context-free. Then the following language would also be context-free:
$$
C' = C \cap 0(100+110)^+0.
$$
What does $C'$ look like? Suppose that $x = wzzw^R$ belongs to $0(100+110)^+0$, where $z,w \neq \epsilon$. Note that the first two symbols of $x$ are $01$, and last two are $00$. This shows that $w = 0$, and so $zz$ belongs to $(100+110)^+$. Thus $|zz| = 3m$ for some $m \geq 1$. Since $|zz|$ is even, $m = 2k$, and so $|z| = 3m/2 = 3k$. Therefore $z$ belongs to $(100+110)^+$, and we conclude that
$$
C' = \{ 0 zz 0 : z \in (100+110)^+ \}.
$$
If $C'$ were context-free, then so would be the language
$$
0^{-1} C' 0^{-1} = \{ zz : z \in (100+110)^+ \},
$$
obtained by taking left and right quotients with $\{0\}$. Finally, if we define a homomorphism $h\colon \{a,b\} \to \{0,1\}^*$ by $h(a) = 100$ and $h(b) = 110$ then the following language would also be context-free:
$$
h^{-1}(0^{-1} C' 0^{-1}) = \{ zz : z \in (a+b)^* \}.
$$
Since this language is well-known not to be context-free, we conclude that so is $C$.


Yes you can do it directly on the K-map. In order to get a minimal product of maxterms (aka product-of-sum [POS], aka conjunctive-normal-form [CNF]), you simply circle/unify the zeros that appear in the K-map instead of the ones. (It doesn't matter how you got the K-map, it can be from any representaiton of the function, it's just a table of the function's output after all). You can also build the K-map from a (not necessarily minimal) POS by adding a zero the K-map for every maxterm (with the remaining squares being ones.) This should be said to varying extents in most textbooks, e.g.

Digital Fundamentals by Thomas L. Floyd, 9th edition, pp. 221-224 has a very detailed example. (I'm guessing the latest, 11th edition has it too, but I haven't checked.)
The Electronics Handbook, Second Edition edited by Jerry C. Whitake, pp. 55-57 has an example too, but this isn't as detailed.
Introduction to Digital Electronics by Reid and Dueck, p. 114 also has an example.
Digital Logic Techniques, 3rd Edition by John Stonham, p. 43.

That this approach is correct comes from De Morgan's laws and double negation. It's the same as if you flipped all zeros and ones in the K-map and SOP-minimized the negated function and then finally applied De Morgan to the result double-negating the function. This is explained on an example in

Principles of Modern Digital Design by P.K. Lala, p. 70.

and probably other textbooks as well.


Polynomials - using Newton's method, or not?

The sum goes to infinity at x = -1 / $b_i$. Between $b_i$ and $b_{I+1}$ it is continuous. So each of these intervals contains a point wher the sum of fractions equals k. Go from there.


Complexity of the decision version of determining a min-cut

The described problem is problem A.4.4 of the book  "Limits to Parallel Computation: P-Completeness Theory" and is P-complete. It is proven via a reduction from Alternating Monotone Fanin 2, Fanout 2 CVP (problem A.1.4 of the same book).

The reduction described in this book originates from the 1990 Theoretical Computer Science paper "The Binary Network Flow Problem is Logspace Complete for P" (T. Lengauer, K. Wagner).

The reduction gets an Alternating Monotone Fanin 2, Fanout 2 CVP instance (a circuit $C$) and creates a flow network $N$ that allows a max flow of value $D 4^{k-1}$ where D is the number of input gates in $C$, iff $C$ evaluates to 1.

The idea is to construct the network by creating two nodes $(i,x,0)$ and $(i,x,1)$ for each gate $(i,x)$ (gate $x$ on the $i$th layer in $C$, one for each possible value 0 and 1). The input layer is layer 0. The source of $N$ is connected to $(0,x,0)$ ($(0,x,1)$) with capacity $4^k$ iff $(0,x)$ is a constant 0 (1) in $C$. Each edge $((i,x),(i+1,y))$ of $C$ is then replaced by a small subnetwork which sends 3/4 of the flow directly to the sink. The remaining quarter is sent to $(i+1,y,0) ((i+1,y,1))$, if $x$ in $C$ values to 0 (1). (At least the max flow needs to take these routes. Hence these small subnetworks simulate the gates.)

Now, the output gate $(k,x)$ is copied as well, but only the $(k,x,1)$ copy is connected to the edge. That is: Iff $C$ evaluates to 0, then exactly 1 flow unit cannot be sent to the sink. Hence, the flow in $N$ is $D 4^{k-1}-1$. If $C$ evaluates to 1, then the full $D 4^{k-1}$ flow units can reach the sink. This completes the reduction.


2-clause satisfiability associated graph

You already have a description of how the graph is built from the formula. Think about a possible algorithm for doing the job. For example, you first scan over all variables in the formula, and you add two vertices into your graph for each. Now you only need to add in the edges into the graph. You can scan over the clauses, and if you see either form you describe, you add in an edge into your graph. This all can be implemented to run in polynomial time; just observe you are performing two scans over the formula, and you do a bit of work for every step of the scan. Similar reasoning will make you see the graph only needs polynomial space.

For your first question, an answer is given in the Wikipedia article on 2-SAT, but has also been touched upon in other question (see e.g., here).


A term in logic and rewriting theory is anything defined by a tree structure that's supposed to represent the syntax of something. It can be a term of a programming language, a type, a kind, a module, etc.

The size of a term is the size of the tree: it's 1 for a leaf, and $\mathit{size}(t) = \mathit{size}(t_1) + \dots + \mathit{size}(t_n)$ for a tree $t = C(t_1,\dots,t_n)$. The exact definition is often not terribly important: what matters is that the size of a term is strictly larger than the size of any term that appears as a part of it.

In programming language literature, some authors use term in this sense, and some authors use term for a term of the programming language itself as opposed to types, kinds, modules, etc. The former authors use expression for the narrow sense of a term of the programming language itself. Pierce uses term in the narrow sense.

The definition of the size follows the same principle no matter what syntactic category the term (in the broader sense) represents. Thus the size of a type is defined as $\mathit{size}(\mathsf{Nat}) = \mathit{size}(\mathsf{Bool}) = 1$,  $\mathit{size}(\mathsf{T}_1 \mathord\rightarrow \mathsf{T}_2) = 1 + \mathit{size}(\mathsf{T}_1) + \mathit{size}(\mathsf{T}_2)$, etc.

When there are multiple syntactic categories, whether terms of another category count depends on the definition chosen by the author. For example, the size of $\lambda x:T. M$ could be defined as $1 + \mathit{size}(M)$, or as $1 + \mathit{size}(T) + \mathit{size}(M)$, or even as $1 + \mathit{size}(x) + \mathit{size}(T) + \mathit{size}(M)$ depending on what is convenient for the matters at hand.


Problems while trying to prove that $(r|s)^* = (r^*.s^*)^*$

In one direction,
$$
L((r^*s^*)^*) \subseteq L(((r|s)^*(r|s)^*)^*) = L(((r|s)^*)^*) = L((r|s)^*).
$$
In the other direction, $L(r) \subseteq L(r^*s^*)$ and $L(s) \subseteq L(r^*s^*)$ imply that $L(r|s) \subseteq L(r^*s^*)$, and so
$$
L((r|s)^*) \subseteq L((r^*s^*)^*).
$$


Non-deterministic logarithmic time complexity class

$\mathsf{DLOGTIME\subsetneq NLOGTIME}$. Search in unsorted array is a problem from $\mathsf{NLOGTIME}$, but it can't be solved deterministically in logarithmic time. This is proven. I also think that $\mathsf{NLOGTIME\not\subset DTIME}(o(n))$.

Padding argument here do not have an implication for $\mathsf P$ vs. $\mathsf{NP}$.


Is there a single valid definition for a Turing Machine, or is it mutable?

The ordering of the items in the 7-tuple M is completely immaterial to the behavior of the Turing machine. There is no "correct" or "incorrect" ordering; but I would say that both orderings are essentially the same definition. And I don't see that the blank character is treated any differently in the two definitions. In both, it's part of the tape alphabet but not the input alphabet.

For the two definitions to be effectively different, you would need to find a difference that does not correspond to a re-ordering of the 7-tuple, or is just in the wording of how the blank symbol is treated.

The only actual difference between the two definitions seems to be that your book has $q_{\mathrm{accept}}$ and $q_{\mathrm{reject}}$ as the halting states, while Wikipedia permits a general set $F$ of halting states. This is because your book only deals with Turing machines that compute languages (so for every string $x$, either $x \in L$ or $x \not\in L$) while Wikipedia also wants to handle Turing machines that compute functions. For a Turing machine that computes a function, you can assume that there is only one final state, $q_{\mathrm{halt}}$; the value of the function will be written on the tape when the Turing machine halts.


How can I study the nature of the structure of evaluation of function in lambda calculus?

I'll try addressing only some of the questions.

Church numerals are defined to be functions (abstractions in $\lambda$-calculus speech) that take two arguments: a base argument $z$ (stands for zero), and a "successor" function $s$ which will be repeatedly applied to the base $z$. The number of times $n$ we apply $s$ corresponds to some natural number $n$.

The successor function $\mathsf{succ}$ takes a Church numeral corresponding to some $n \in \mathbb{N}$ (the numeral's canonical form is $\lambda sz. s^nz$), and returns a Church numeral corresponding to $n+1$, i.e. some term that behaves like $\lambda sz. s^{n+1}z$.

Notes:

$s^n z$ means $s (s (s (... s z))...)$, where $s$ applied $n$ times to $z$;
two abstractions are behaviorally equivalent if applied to the same arguments they yield the same result.

Let's obtain a $\lambda$-term representing $\mathsf{succ}$. In what follows I'm using Church numerals and corresponding natural numbers interchangeably, I hope that it won't cause confusion, since the current domain can be derived from the context.

$\mathsf{succ}$ is an abstraction that takes a Church numeral $n$, so $\mathsf{succ} = \lambda n. \textsf{<...>}$
$\mathsf{succ}$ returns a Church numeral, which must take 2 arguments, that's why $\mathsf{succ} = \lambda n. (\lambda sz. \textsf{<...>})$
After supplying some $s$ and $z$ to $(\mathsf{succ}\ n)$ we must have $s$ applied $n+1$ times to $z$. Notice that the Church numeral $n$ allows us to easily get $s$ applied $n$ times: we just apply $n$ to $s$ and $z$: $(n\ s\ z) = s^n z$. Then, using the fact $s^{n+1} z = s (s^n z)$, we get $s^{n+1} z = s (n\ s\ z)$. Finally, $\mathsf{succ} = \lambda n. (\lambda sz. s (n\ s\ z))$ or, sweetening with some more syntactic sugar, $\mathsf{succ} = \lambda nsz. s (n\ s\ z)$.

The term we've got for the successor function is not unique, one can use any form of $\mathsf{succ}$ as long as it fulfills its role: make "the next" Church numeral out of the current one. For instance, the following is a valid term for $\mathsf{succ}$ too: $\lambda nsz. n s (s z)$, and it can be obtained using the fact $s^{n+1} z = s^n (s z)$.

In fact, there are infinitely many syntactically different $\lambda$-terms for the successor function. We can invent many different (and silly) ways of "implementing" $\mathsf{succ}$: make a Church pair $(\lambda nsz. s (n\ s\ z), \text{<any-term>})$ and take its first component, i.e.
$$
\mathsf{succ} =
\mathsf{fst}\ (\mathsf{pair}\ (\lambda nsz. s (n\ s\ z))\ \text{<any-term>}),
$$
or add $x+1$ to a number and subtract $x$, i.e.
$$
\mathsf{succ} = \lambda n. \mathsf{minus}\ ((\mathsf{plus}\ n\ \mathsf{(x+1)})\ \mathsf{x})
$$

Now, let's address the $\mathsf{succ}\ (\mathsf{succ}\ 1)$ issue (I'm using the unrestricted evaluation strategy here):
$$
\begin{array}
    \mathsf{succ}\ (\mathsf{succ}\ \mathsf{one}) &= \quad \text{(by definitions of succ and one)} \\
    \mathsf{succ}\ ((\lambda nsz. s (n s z))\ (\lambda sz.s z)) &\to_{\beta} \\
    \mathsf{succ}\ (\lambda sz. s ((\lambda sz.s z) s z)) &\to_{\beta}^{*} \\
    \mathsf{succ}\ (\lambda sz. s (s z)) &= \quad \text{(by definition of succ)} \\
    (\lambda nsz. s (n s z))\ (\lambda sz. s (s z)) &\to_{\beta} \\
    (\lambda sz. s ((\lambda sz. s (s z))\ s z)) &\to_{\beta}^{*} \\
    (\lambda sz. s (s (s z)))
\end{array}
$$
We've got a $\lambda$-term which clearly represents the number $3$ as was expected. If you try using $\lambda nsz. n s (s z)$ as the successor function you'll get the same result.

Under more restricted reduction strategy, viz. the call-by-value strategy, we sometimes get a term which doesn't look like a Church numeral at all, but behaves like one. A classical example is
$$
\begin{array}
\mathsf{succ}\ 1 &= \\
(\lambda nsz. s (n s z)) (\lambda sz. s z) &\to_{\beta} \\
\lambda sz. s ((\lambda sz. s z) s z)
\end{array}
$$

The result is behaviorally equivalent to $\lambda sz. s (s z)$.

Now I'm going to show that $(\mathsf{succ}\ \mathsf{succ})\ N$ is equivalent to Church numeral corresponding to $N(N+1)$. Then somewhat unintuitive term $(\mathsf{succ}\ \mathsf{succ})\ 1$ indeed evaluates to $2$.

$$\begin{array}
\mathsf{succ}\ \mathsf{succ}\ N &= &\text{unfold the 1st succ}\\
(\lambda nsz. s (n s z))\ \mathsf{succ}\ N &\to_{\beta} \\
(\lambda sz. s (\mathsf{succ}\ s\ z))\ N &\to_{\beta} \\
\lambda z. N\ (\mathsf{succ}\ N\ z) &\to_{\beta}^{*} &\text{(apply succ to N)}\\
\lambda z. N\ (\{N+1\}\ z) &=_{\alpha} &\text{(rename z → s)} \\
\lambda s. N\ (\{N+1\}\ s) &= &\text{unfold {N+1}} \\
\lambda s. N\ ((\lambda tz'. t^{N+1}\ z')\ s) &\to_{\beta} \\
\lambda s. N\ (\lambda z'. s^{N+1}\ z') &= &\text{(unfold N)} \\
\lambda s. (\lambda tz. t^{N}\ z)\ (\lambda z'. s^{N+1}\ z') &\to_{\beta} \\
\lambda s. (\lambda z. (\lambda z'. s^{N+1}\ z')^{N}\ z) &= &\text{(syntactic sugar)} \\
\lambda sz. (\lambda z'. s^{N+1}\ z')^{N}\ z &\to_{\eta} &\text{(η-reduction)} \\
\lambda sz. (s^{N+1})^{N}\ z &= \\
\lambda sz. s^{N(N+1)}\ z &= \\
N(N+1)
\end{array}$$


Definition of the state of an object in OOP

You can take a look to (and cite) the book "Object-Oriented Analysis and Design" by G. Booch:

  ... An object is an entity that has state, behavior, and identity. The structure and
  behavior of similar objects are defined in their common class. The terms instance
  and object are interchangeable.

  We will consider the concepts of state, behavior, and identity in more detail in the
  sections that follow.
  ...

And there is a whole subsection that describes the concept of state:

  ... From this example, we may form the following low-level definition.

  The state of an object encompasses all of the (usually static) properties of the
  object plus the current (usually dynamic) values of each of these properties
  ...


Why can't I run a mac program natively on windows?

Think of the .dmg file as a book of short stories.

Windows and Mac OS X have different formats of books, so the gesture to open one is a bit different (think of pages turned from left to right or right to left). Less metaphorically, a .dmg file packs a bunch of files, and the format in which these files are packed isn't one that Windows supports natively. However it would be easy to write a program to unpack .dmg files on Windows, and I'm sure someone has done so.

Ok, now you have the book open and can see the pages. That doesn't necessarily mean you can read it, though. Let's say you speak English and only English… but the book is in Turkish. You aren't going to be able to understand a word of it.

A computer program contains a bunch of elementary instructions. The instruction set is like the script that the book is written in. The instruction set is determined by the type of processor that powers the computer. Modern Macs and Windows PCs have the same type of processor (one of the two x86 families, either the 32-bit one or the 64-bit one). So that step is fine — you can make out the individual letters. However, that's not enough!

Some instructions rely only on the processor: instructions like “read the value at this memory location” or “add these two numbers” or “jump to this location in the program”. However, every time the program wants to interact with something else (access a disk file, read user input, display something, communicate over the network, etc.), the program makes a call to the operating system. And two completely different operating systems, such as Windows and Mac OS X, have completely different APIs — they offer completely different system calls. (Note that the metaphor breaks down somewhat here: the problem isn't that the arrangement of instructions has to be different, but that a few very important instructions have radically different effects.)

There's even another layer of differences: Windows and OSX even have different executable file formats (PE vs Mach-O). The executable format determines how code and data are arranged in the file and how things like dependencies on libraries are represented. Making Windows understand OSX's file format would require some work, but making Windows understand OSX's system calls would be a Herculean task.

You can't read the book because it's in Turkish. You could learn Turkish, but it would take years of effort. Similarly, making Windows able to run OSX programs would take a huge amount of programming effort.

In fact, it's simpler to simulate a processor with its peripherals, by implementing all of its instructions, than it is to simulate an operating system by implementing all of its system calls. This is called a virtual machine. You can run an operating system on an emulated machine that is in fact provided by a program running under another operating system. For example, you can run OSX on an x86 CPU emulated by Vmware which is running as a Windows application. (In the specific case of OSX, this is difficult, but not for technical reasons, rather because Apple makes it difficult for commercial reasons.)