Difference between word logical addressing and byte logical addressing in this exercise?

Page size => 1024 words = 2^10 words

Since it is word addressable format 10 bits will be required to identify offset within page.

There are 10 pages as 10 can't be expressed in 2's power format we need to consider 16 for identifying 10 pages i.e. 2^4=16.

So 4 bits are  required for page number.


Is the complexity class NP computably enumerable?

I can't make heads nor tails from what you attempt to do, but I know that the answer to your question is: no, NP is not enumerable.

First, let's fix what that means. I assume you are asking if

$\qquad\displaystyle \mathrm{TM}_{\mathsf{NP}} = \{ \langle M \rangle \mid L(M) \in \mathsf{NP} \}$

is recursively enumerable. It's not by the extended Rice theorem since the Turing machine $M$ that never halts is an NP-acceptor for the empty language, so $M \in \mathrm{TM}_{\mathsf{NP}}$, but there certainly are $M'$ with $M \subsetneq M'$ and $M' \notin \mathrm{TM}_{\mathsf{NP}}$.

Intuitively, no algorithm can separate $M$ (which has infinitely many equivalent brethren, by the way) from any other Turing machine in finite time, and thus can never enumerate them.


How to create this pushdown transducer? (formal languages and automata)

It is no surprise you could not create that PDA: the language $\{a^m b^{2m}c^m\mid m\geq 0\}$ is not CF. The same is true of $\{a^m b^{2m}c^{m+n}\mid n\geq m\geq 0\}$. You may try to prove it.

Hence, I suspect that the pushdown transducer is not supposed to recognize the input string but assumes it is well formed, and simply has to translate correctly when it is.

So I would simply use the pushdown stack of the transducer to collect the information to be found in the input (supposed to be well formed) to produce the correct output, without worrying about acceptance. You do not care what happens when the input string is not well formed.  It is actually quite simple to produce $b^{n-m}$


Regular expression or automata for language with odd number of 0's and odd number of 1's

Hint: You are trying to solve two problems (i.e., odd number of zeros and odd number of ones) at once. Try to solve each separately instead and then combine the solutions appropriately.


Time complexity of algorithm inversely proportional to size of sub problem?

I am afraid that you fell prey to ambiguous notations.

To clarify, the subscript $\frac{n-1}2$ in the recurrence relation, $T_n = T_\frac{n-1}2 + 1$ must mean the integer division of $n-1$ by 2 as used in most programming languages, i.e., $\frac 22=1$ and $\frac32=1$. The following equality does NOT hold,

$$\log_2(\frac{n+1}{2}) = \log_2(n+1) - 1,$$
where the division on the left hand side is the integer division. For example, you can check the case when $n=2$.  In the light of that clarification, $T_n = C\log_2(n+1)$ with any constant $C$ cannot be a solution to that recurrence relation.

Now, you might insist that $\frac{n-1}2$ means the usual math division of $n-1$ by 2, i.e., $\frac{3-1}2=1$ and $\frac{4-1}2=1.5$, so that $T_n = C\log_2(n+1)$ could be a solution to that recurrence relation. Well, in that case, that recurrence relation, together with the initial conditions $T_0 = 0$ and $T_1 = 1$ does not define the value of $T_2$, since $T_2=T_{0.5}+1$, where $T_{0.5}$ is not defined. That means, it does not make any sense to involve $T_2$, $T_4$, etc in any equality, since they are not defined!

By the way, it is wrong that "from Master's theorem, $T_n = T_{n/2} + 1 \Rightarrow T_n = \log_2(n)$". What Master's theorem tells us is, $T_n = T_{n/2} + 1 \Rightarrow T_n = \Theta(\log_2(n)).$


This is one of the reasons why most modern general-purpose CPUs have split L1 caches, one for instructions and one for data. (It's not the only reason, of course.)
You see, modern CPU pipelines don't interact with a von Neumann-type bus at all, but directly with cache. As far as the pipeline is concerned, instruction memory and data memory are separate because the caches are separate.


Understanding access and insertion time of arrays

Because they are using the pointer to access to an index of the array, hence the access time is constant. Moreover, as indices of the array are stored beside each other (to access in constant time), insertion to the array needs to extend the allocated storage of the array to insert a value, and it needs to copy all values of the array to the newly allocated storage with size $n + 1$. Hence, insertion of the array is $O(n)$ in most of the implementations.

To know more about this, you can seek around "dynamic array" for constant access time and amortized $O(n)$  for $n$ insertion.


Smallest real root of a polynomial in a range

I would like to propose mix of Sturm algorithm (to split range into ranges to know how many roots are there) and then run Newton method, which converges very fast with good initial guess.

Of course for Sturm - only up to first root range found.

Housholder is very tempting, but please check the runtime first to tweak the degree (and there is chance that it will in fact be Newton after all, when degree is equal one).

The main idea behind that is local root finding methods are faster than global ones, but they might diverge to some other place, but you are interested in the first one, so providing good initial guess will put Newton method in the radius of convergence.

The things to add: there might be many roots in small distance, so the main idea was to "pick one" range and start finding it, your idea of finding the slope is very neat, and if you merge the slope finding with initial range picking it seems like boosted Newton for very small cost.
The idea is to also show Newton method which root you are after (otherwise it might go after surrounding one).

About binary search, if you want to apply it until there is one root - yes, indeed, but if the idea is to check more ranges - I would cut it for resources savings.


Your language could be rewritten more clearly as:

$\{ a^m \mid m \text{ is a perfect cube} \}$

Now you'd have to find a word from this language, longer than the pumping length $p$, that can not be pumped. We choose as a candidate: $a^{p^3}$.
We name our three substrings $x, y, z$, which must be of the form:
$x = a^i$
$y = a^j$
$z = a^{(p^3 - i - j)}$

The pumping lemma restricts $j$ to be greater than $0$ and $i + j \le p$. It's sufficient to show that there exists at least one integer $k \ge 0$, such that $xy^kz$ is not a valid word in the language. Because of our separation, we need to find a $k$ such that $p^3 + (k - 1)j$ is not a perfect cube.
Let's say $k = 2$, which gives us $p^3 + j$, strictly increasing with respect to $j$, having a maximum value of $p^3 + p$.
We also know that the smallest perfect cube larger than $p^3$ is $(p + 1)^3 = p^3 + 3p^2 + 3p + 1$.

Because $p^3 \lt (p^3 + p) \lt (p+1)^3, \forall p \gt 0$, our pumped string's length can't be a perfect cube (because it's strictly between two consecutive perfect cubes).

So the language contains at least one word longer than the pumping length that can't be pumped, which means the language isn't regular.


My professor claims that inserting the same key into a hash table again will lead to a collision … – Is he really right?

I suppose one could define the word however you like, but I've always understood it to mean the same thing you are talking about. Here I'm assuming if you try to insert a key the second time, no change is made, as it is already present.  If inserting the key caused a second copy to be inserted somewhere, then I think it's more ambiguous and in any formal analysis it would be best to define precisely what you mean by a collision and state whether you consider that a collision, to avoid confusion.


Acyclic Tournament Digraphs and Hamiltonian Paths

I am completing Nicholas's answer because I think there are problems with his answers to 3 and 4 and explaining why is a bit too long for comments.

For 3. you need to show there is a simple path in the tournament that visits every vertex (this is called a hamiltonian path). You can do this simply by induction. Clearly this is true for a tournament on 2 vertices. Now assume you have a tournament $T = (V, A)$ on $n$ vertices.  Remove some arbitrary $v$ from $V$ and find a hamiltonian path $v_1, \ldots, v_{n-1}$ in the induced tournament on $V \setminus \{v\}$. If for all $i \leq n-1$, $(v_i, v) \in A$, then $(v_{n-1}, v) \in A$ and you can append $v$ to the existing path. Otherwise, there exists some edge from $v$ to the $\{v_1, \ldots, v_{n-1}\}$; let $i$ be the smallest integer such that $(v, v_i) \in A$. Either $i = 1$ and you can pre-pend $v$ to the existing path, or, since $i$ was the smallest $i$ such that $(v, v_i) \in A$, you know that $(v_{i-1}, v) \in A$, and, therefore, you can take the path $v_1, \ldots, v_{i-1}, v, v_i, v_{i+1}, \ldots, v_{n-1}$.

For 4., I also don't think it's enough to say that the rationals have no infimum or supremum. That's true of the integers too, but there exists a path through the integers which is infinite in both directions. I think the crucial property of the rationals that causes problems is that they are dense: there is a rational between every two rationals. In particular, assume for contradiction there exists a path that visits all rationals in the graph defined in the question. Take any edge $(x, y)$ in the path: $x < \frac{x+y}{2} <y$, so $\frac{x+y}{2}$ cannot precede $x$ in the path and it cannot succeed $y$, so it cannot be in the path - a contradiction.


Problem with proving the undecidability of REGULAR$_{TM}$

Note $M_2$ is constructed based on $\langle M,w\rangle$. That is to say, different $\langle M,w\rangle$ may result in different $M_2$.

If $M$ accepts $w$, then $M_2$ will accept any string (if the input has the form $0^n1^n$, $M_2$ accepts it at the first step, otherwise $M_2$ accepts it at the second step), thus $M_2$ accepts a regular language.

If $M$ does not accept $w$, then $M_2$ will only accept string of the form $0^n1^n$ (if the input has the form $0^n1^n$, $M_2$ accepts it at the first step, otherwise $M_2$ skips the first step, and will not accept it at the second step), thus $M_2$ accepts a non-regular language.

So we can conclude $M$ accepts $w$ iff $M_2$ accepts a regular language.


Determine whether a point lies in a convex hull of points in O(logn)

This is a classic problem in computational geometry, called Polygon Inclusion Problem. Further, you are considering its special case --- Convex Inclusion.

In chapter 4 of this thesis by Michael lail Shamos 1978, you will find that:

Generally,

  Theorem 4.2 (Page 92): Whether a point is interior to a simple $n$-gon can be determined in $O(n)$ time, without preprocessing.

and for convex polygon,

  Theorem 4.3 (Page 95): The Inclusion question for a convex $n$-gon can be answered in
  $O(\log n)$ time and $O(n)$ space, given $O(n)$ preprocessing time.

The proofs of these two theorems contain the algorithms you are looking for.


Natural occurrences of monads that make use of the category-theoretical framework

Asking whether an occurrence of monad is natural is similar to asking whether a group (in the sense of group theory) is natural. Once you formalise something, in this case as an endofunctor, either it satisfies the axioms of being a monad or not. If it does satisfy the  axioms, then one gets a lot of technical machinery for free.

Moggi's paper Notions of computation and monads pretty much seals the deal: monads are incredibly natural and useful for describing computational effects in a unified way. Wadler and others translated these notions to deal with computational effects in functional programming languages, by using the connection that a functor is a data type constructor. This  adds the icing on the cake. FP monads allow a treatment of computational effects such as IO which would be extremely unnatural without them. Monads have inspired related useful notion such as arrows and idioms which are also very useful for structuring functional programs. See the Wadler link for references. FP monads are the same thing as category theory monads in the sense that for an FP monad to work the same equations need to hold --- the compiler relies on these. Generally, the presentation of the monad differs (different but equivalent operations and equations), but this is a superficial difference.

A vast amount of the work of Bart Jacobs, to take but one example, uses monads. A lot of work stems from coalgebra, which is a general theory of systems. One of Jacobs' (many) contributions to the area is the development of a generic notion of trace semantics for systems (described as coalgebras) based on monads. One could argue that the notion of trace semantics is natural: What is the semantics of a system? The list of actions that can be observed!

One way to understand monads is to first program in Haskell using monads. Then find one of the many good tutorials available (via google). Start from the programming angle, then move to the theoretical side, starting with some basic category theory.


Why there is no FPTAS for multiple knapsack problem for two knapsacks unless P=NP?

There is no guarantee that the packing algorithm you suggested will lead to an optimal packing. Say you have two knapsacks of capacity 5, and objects of size 1, 2, 3 and 4. An optimal packing would be putting 1 and 4 into knapsack 1, and 2 and 3 into the other knapsack (switching the indexes on the knapsacks would also be another alternative solution and this is a further complication). The greedy algorithm you have given would not result in this packing.


Stateful computation basically means that the model of computation has got a memory storage to store information, and it uses this information to compute. For example, let us say you have a function $f()$ computing something using state information. Then, if you do,

$x_1 = f()$
$x_2 = f()$
$x_3 = f()$
...

$x_1, x_2, x_3,.. $ may be all different. In functions, defined  as mapping in  set theory, we cannot have functions returning different values from different calls. We will need to define something like $\langle y, store_{i+1}\rangle = f(\langle x, store_i\rangle)$ in that case.
 A sample code for $f()$ that is stateful is given below.

function f()
output: integer x;

global integer store initialized to 0;

x = store
increment store by 1
return x

This function will return 1, 2, 3, 4, ..., in sequence when it is called multiple times. Here store is the memory storage it uses to compute differently.

The function can also use other inputs to compute its output, such as events from an event queue, input data, interactive data, etc. but stateful computation must assume an underlying saving of state in the model of computation.

By the way, the model of computation for computers is Turing Machine, which can be thought as stateful computation if you use functions as subroutines, i.e., you do not start Turing machine from beginning at every function call.


Prim's algorithm greedily chooses the smallest edge leaving the set of already connected nodes (until all nodes are connected).

It is not clear what "non-trivial run" means here; I propose this: a run of Prim is trivial if in every step, it can choose the smallest available edge. This would happen on linear chains, for instance.

With this "definition", a non-trivial run is one during which the algorithm can not choose a cheap edge because it would create a cycle, but has to take a more expensive one. Here is an example graph:

[source]

If you start the algorithm with $A$, edge $\{B,C\}$ would be the cheapest after having chosen $\{A,B\}$ and $\{A,C\}$, but it can not be chosen.


Integer Linear Programs: An instance or not?

Your problem has a solution if and only if $m$ is a multiple of the greatest common divisor of $x_1,\ldots,x_n$. You can compute the GCD in polynomial time using the Euclidean algorithm (the version where you divide in each step rather than subtract) applied $n-1$ times.


If such a mapping $f$ exists at all, there always exists such a mapping with $k = 1$: you can always collapse a larger function in such a way that doesn't make the mapping constant. In other words, a mapping $f$ exists if there is some non-trivial event $E$ depending only on $Y$ which is independent of $X$. The converse is also true.


What happens if the holder of a lock tries to acquire a lock?

Resources that can only be used by a single process at a time are usually protected by a lock. If the process that currently holds the lock attempts to acquire it a second time, what happens depends on the type of lock.

If the lock is reentrant, then it can be acquired multiple times by the same process. The process will need to call the release function as many times as it called the acquire function.
If the lock is not reentrant (for example if it's a simple semaphore or an atomically-modified boolean), then a second attempt will block. You can call this a single-process deadlock.
In some mutex implementations (probably not in what is studied in Concurrency 101 though), a process can acquire the same lock more than once, and the second time is a no-op, so the process must only call the release function once. Another thing that sometimes happens is that calling the acquire function from the same process twice puts the implementation in a bad state after which anything can happen — the semantics doesn't define what happens in that case.

Thus, it depends on what semantics your locks have. You can build non-reentrant locks on top of reentrant locks or vice versa if all you have is the wrong kind for what you want to do.


Shortest path in weighted(positive or negative) undirected graph

A generic scheme to make an undirected graph directed is to replace each of its edges by two directed edges with same weight as the original weight of the edge. For an undirected edge $(u,v)$. Replace it by two directed edges $(u,v)$(direction u to v) and $(v,u)$(direction v to u). The weight of both of these edges are same as weight of undirected edge $(u,v)$.

Thus the algorithm which you have in mind for solving directed SSSP can also be applied on undirected graph with the above mentioned changes.

And, a good way to get a shortest path with smallest number of edges is to add a small constant weight ($\epsilon$) to all edges. Note that if we have two shortest path having $x$ and $y$ edges ($x > y$) before, then adding small value to all edges changes the weight of the shortest path with $x$ and $y$ edges by amount $x\epsilon$ and $y\epsilon$. As $x\epsilon > y\epsilon$, now the shortest path with $y$ edges is having lesser cost. Thus after changing the edge weight by a very small amount you can apply your favorite SSSP algo to get the path with minimum number of edges. Note that as $\epsilon$ is very small a path which was not shortest before can't be shortest after changing the weights.


If $f(n)$ is $O(g(n))$ is it also $O(g(n-d))$?

The answer to your first question (whether $f(n) = O(g(n))$ implies $f(n) = O(g(n-d))$) depends on the function $g$: indeed, what you want holds iff $g(n) = O(g(n-d))$. This is a relation that holds for many functions, for example polynomials and exponentials, but not for the function $g(n) = 2^{2^n}$.

As for your second question, if $f$ is monotone (increasing) then $f(n-d) \leq f(n)$, and in particular $f(n-d) = O(f(n))$. The same holds if $f(n) = \Theta(h(n))$ for some monotone $h$. For example, if $f$ is a degree $a$ polynomial then $f = \Theta(n^a)$, and so $f(n-d) = O(f(n))$, since $n^a$ is monotone.


Algorithmic complexity of a Maximum Capacity Representatives variant

I'm assuming that the goal of your optimization problem is to maximize $\min \{ c(x,y) : x,y \in T \}$. The decision problem is then:

  Given a system $S_1,\ldots,S_m$ of disjoint sets, a cost function $c\colon S \times S \to \mathbb{R}_+$ (where $S = S_1 \cup \cdots \cup S_m$) and a number $\gamma \in \mathbb{R}_+$, decide whether there is a choice of representatives $t_i \in S_i$ such that $c(t_i,t_j) \geq \gamma$ for all $i \neq j$.

This problem is NP-hard (and so NP-complete), by reduction from max clique. Given a graph $G = (V,E)$ and a number $m$, let $S_i = \{i\} \times V$, define $c((i,v),(j,w))$ to be 1 if $(v,w) \in E$ and 0 otherwise, and let $\gamma = 1$. The graph $G$ contains an $m$-clique if and only if the answer to your decision problem is affirmative.


How to maximize the number of filled grid squares in a partially filled grid with Tetris shapes

This question can be reduced to the exact cover problem which is NP-Complete. A typical method for solving the exact cover problem is known as Algorithm X.

Consider the set of choices you have:
For each tetris piece of $4$ units, you can select an orientation and a location to place it on the board. For each choice, the piece will cover $4$ squares on the board. Let matrix $A$ be our exact cover matrix. The columns of $A$ are the constraints that must be satisfied exactly once i.e. there is a constraint for every unfilled grid location on the given board. Each row represents a "choice" i.e. a tetris piece, orientation and location and has $1$s in only the columns which correspond to the locations that that placement of the tetris piece would cover.

To account for the grid locations that have already been filled, we make sure that any row is removed that would either

Fall outside of the $m$x$n$ grid
Cover one of the cells already covered in the given $mxn$ grid

Then it remains to select a subset of rows $S$ such that for each column $i$:
$$\sum_{row\in S}row[i] = 1$$

Algorithm X is one way of solving this problem (with the help of the dancing links technique. Other algorithms exist as well (AC3 is taught as an introductory constraint-satisfaction solver algorithm at some universities). Soduku puzzles are another example of exact cover problems.

Notice that max cover is a decision problem, whereas the question you posted is an optimization problem. This can be addressed by just searching for the maximum number of columns covered over the search. Of course this will result in a much slower runtime since you will have to run the algorithm for longer. You may benefit from introducing some heuristics into your search as well. For example, say you are at some point in your search where:

The best cover you have seen so far covers $s$ locations.
Your current cover covers $k$ locations.
There are $x$ remaining open locations on the board that are part of a connected group of at least 4 open locations.

If $k+x\leq s$, you can cut the search tree off here, since there is no way this current layout of tiles can lead to a better solution that the one you have already found.


Phrase generators for use with testing grammars that don't use a seed

The tools you refer to are probably already deterministic. Tools that accept a seed probably only employ a pseudorandom generator which is keyed from the seed and nothing else. Therefore, given the seed, everything is completely deterministic. If the seeding process is reasonable, then a seed like $0$ or $1$ should work. For definiteness, I suggest you take your favorite "random" tool and use a fixed seed, say $1$. Now it's completely deterministic.

One reason you'd want a deterministic tool is reproducibility. You want to be able to reproduce phrases on demand. If the tool is random, that's impossible. However, if all the "randomness" is encapsulated in a user-entered seed, the output is reproducible; all you have to do is remember the seed used.

I cannot think of any other reason you'd want your tool to be deterministic, but if there is one, please let us know so that we can understand your question better.


Find the n best choices while maximizing value

Thanks to Yuvals comment i found this site discussing the set cover problem. It's exactly what I needed.


Reduction from Vertex Cover to an Independent Set problem

No. The typical reduction from Independent Set to Vertex Cover doesn't preserve the parameter ($k$). A graph with a vertex cover of size $k$ has an independent set of size $n-k$, so we no longer have $n$ restricted to the polynomial part.

This separation is one of the basic conjectures of Parameterized Complexity. Parameterized Complexity is a bivariate complexity theory where problems are given with not only the normal input, but also a parameter. For example the (natural) parameterized version of Vertex Cover is:

  Vertex Cover
  Input: A graph $G$, a positive integer $k$.
  Parameter: $k$.
  Question: Does $G$ have a vertex cover of size at most $k$?

So each parameterized problem has two (formally explicit) metrics: the size of the input $n$, and the parameter $k$. We then say that a problem $\Pi$ is fixed-parameter tractable if there is an algorithm that decides each instance $(x,k)$ of $\Pi$ in time bounded by $f(k)\cdot|x|^{O(1)}$ for some computable function $f$ dependent only on $k$ (i.e. polynomial with constant degree in $|x| = n$, but essentially free in $k$). We call the class of all such problems $FPT$.

So Vertex Cover is in $FPT$ when parameterized by the size of the vertex cover.

The main intractability framework for Parameterized Complexity is called the $W$-hierarchy, a series of classes $W[t]$ where $W[i] \subseteq W[i+1]$ and $FPT \subseteq W[1]$. Although it's split into lots of classes, the $W$-hierachy bears a practical relationship to $FPT$ in a similar manner to that of $NP$ to $P$, in that if a problem is $W[t]$-hard for some $t$, then it has no $FPT$ algorithm unless $W[t] = FPT$, and we conjecture that $FPT \subset W[1]$ for similar reasons to $P \subset NP$.

Getting back to your question again, finally, it turns out that Independent Set is $W[1]$-complete when parameterized by the size of the independent set. That is, unless $W[1] = FPT$, Independent Set has no algorithm with running time bounded by $f(k)n^{O(1)}$ for any $f$, where $k$ is the size of the independent set.

Additional Note:

Of course we don't have to parameterize by the size of the answer, we can use anything we feel like, the normal guidelines are that it should be something that can reasonably be expected to be small compared to the input size, and it should be able to vary independently of the input size. A common structural parameter for example is the treewidth of a graph. You can parameterize by measures relating to the size of the input, but then we have to introduce a bunch of different classes.


Find all non-decreasing sequences given lenght and size

Hint. Given the available time complexity, a simple recursive algorithm should work. If you need a sequence of length $k$ from the set $\{m, \dots, n\}$ you either include $m$ or you don't.


Negative lookahead in LR parsing algorithm

Yes, there is such a modification. A negative lookahead assertion at the END of a production means taking special care in computing FOLLOW sets. Before a terminal makes no sense. Before a nonterminal is a bit more complicated: the optimal strategy depends on the context. Special care while generating the shift relationship is part of the answer. On balance, this is an algorithm design problem more than a theoretical computer science problem.


The content of an implication from the snm-Theorem

Your assumptions on composition are quite strong. The idea, here, is that you are only assuming that the class of (partial) computable functions is closed with respect to composition (so you only know that you must have some program computing it) and then use smn to prove that you can uniformely and effectively compute an index for such a program from the indexes of the programs you are composing (x and y in your example).

Instead of spending time to show that you can effectively construct a turing machine computing the composition of two other turing machines (that is not so trivial) it is better to spend some time to prove smn, that gives you a much more general technique:

it proves that any partial instantiation of a computable function is still computable
it tells you that you may compute the index of the partial instatiation in a uniform and effective way in terms of the index of the source program and the parameters of the given instantiation (hence, providing a form of parameter abstraction, quite similar to lambda abstraction).

Coming back to your examples, the "source" function is

$$g(x,y,z) = \varphi_x(\varphi_y(z))$$

and you are computing the partial instantiation of $g$ with respect to x and y. The point is that $g$ can be any computable function, and you are free to choose your parameteres in any way you like. A real jolly.

I strongly suggest you to have a look at the following answer on mathoverflow, that gives a very, very nice explanation of smn.


Maximal subsets of a point set which fit in a unit disk

Let's define a function $f: \Bbb R \times \Bbb R \rightarrow \left [0, n \right ] $, returning a number of points from the set $P$, covered by a unit disk with the center at the point $(x, y)$. This is a piecewise constant function, and it's easy to see that its domain can be thought as a planar subdivision, defined by all intersections of unit disks, centered at points from the set $P$. This subdivision contains vertices (= intersection points), edges (= circular arcs) and faces (= pieces of the plane, where the function $f$ returns the same value). We'll say that these faces are labeled by this value.
We'll assume that the planar graph, defined by this subdivision, is a 4-regular one - it's a common assumption, meaning that all the points in $P$ are in general position (each intersection point belongs to exactly two circles). An example of such subdivision for $n=3$ is below, where the label for each face (including the external one) is shown in red color.

As far as I understand your maximal subsets $P_i$ can be associated with such faces of this subdivision, which have labels larger than all labels of their neighboring faces. It's kind of static interpretation of your "moving disk" semantics, which you used in your definition of the maximal subset.
The subdivision will contain as many faces as possible in the case when all the unit circles pairwise intersect each other. It can be shown, that in this case:

number of vertices is $n(n-1)$
number of edges is $2n(n-1)$
number of faces is $n(n-1)+2$

So, answers to your questions will be:

No, the number $k$ of maximal subsets is $O(n^2)$, because it can't be more than the number of all faces.
Yes, all the maximal subsets can be found in $O(n^3)$ time by naive scanning algorithm.

As for name of this problem - it looks like it may be related to some variations of the Unit Disk Cover problem.


Proving a language as undecidable without using reductions

It isn't recognizable because it is infinite, therefore it'll loop infinitely. Does this work?

No, because that claim is false. And your writing isn't at all clear, here. Recognizability is a property of languages, so your first two "it"s must refer to languages; but "loops infinitely" is a property of Turing machines, so your third "it" must be one of those.

Ultimately, though, your whole approach is doomed because the languages you call $One$ and $\overline{One}$ are both decidable. You can easily see that $One$ is decidabe just by designing a Turing machine that decides it.


Closest Pair of Points Algorithm - Fortune and Hopcroft

One thing that you might not be aware of is that there's a 'hidden' exponential factor (it's explained on page 3). In $k$ dimensions the runtime is $O(kn \log(\log(n)) + 3^kn)$, as when you partition $k$-dimensional space into hypercubes each cube has $3^k - 1$ neighbors.
The rest of the algorithm really is 'obvious' then: you split your space up in hypercubes (which is just a fancy word for splitting up each dimension separately into intervals). Each point will then map to exactly one cube, and the rest of the algorithm follows.
E.g. suppose our interval size is $1$ and our domain is $[0, 10)$. Then in 1D we have that the point $3.4$ maps to bucket $3$ and $8.8$ maps to bucket $8$. In three dimensions if our interval size and (per-dimension) domain is the same, we have that $(2.3, 8.4, 4.4)$ maps to bucket $(2, 8, 4)$ and $(4.1, 5.2, 9.5)$ maps to $(4, 5, 9)$. So you end up with three-dimensional buckets but the algorithm hashes the buckets afterwards so that doesn't matter.

If you have anything more than two or three dimensions my suggestion would be to look for another algorithm.


How do I do a subtraction question on turing machine

It seems that you have unary numbers, so there are three cases to consider: number you subtract from is greater, uqual or smaller, this gives you hint what to handle.

In unary when you subtract 11 from 111 (111 - 11 = 1) you have to delete ones in minuend until subtrahend is 0.
In case these are equal, you have to denote 0 (empty tape might denote this). In the third case, result is negative.

Case 1) 111 - 11 = 11 - 1 = 1 - 0 = 1
Case 2) 111 - 111 = 11 - 11 = 1 - 1 = 0 - 0 = 0
Case 3) 11 - 111 = 1 - 11 = 0 - 1 = - 1

So let us start with first phase: start with scratching from both sides, call it say qS:
'B111-11B' where B is blank, on qS put B at leftmost 1, switch state to qS1, which goes right until it finds B. Moves one to the left, if it is 1, put B and return to the leftmost 1 (say state qSr). After execution:
'BB11-1BB' repeat
'BBB1-BBB' if in state qS1 there is no 1 but -, put B on - and accept.

Case 2 would yield something like 'BB-BB', if you are happy with Blank tape as 0, case 1 solves it already, otherwise put 0 on the tape if there are no 1 left.

Case 3 leaves you with situation like 'B1-11B'. Here only modification is to accept when after - there is Blank. So one step later, there is 'BB-1BB', this is result already.

What could go wrong?
There might be input like 'B11-1-1B', if you are not promised it won't happen. In such case split going right in qS1 into find '-' and then find Blank. If after first '-' there occurs another one, reject on it.

To practice more you could write your code in simulator online, check addition first as Apass.Jack suggested. When you finish, try multiplication, the sooner the better.

To see a working version look at my subtraction code at simulator.

This code has format:
state read_symbol write_symbol direction new_state, everything after semicolon is a comment, halt-accept is accepting state, halt-reject is rejecting state * in direction is not move instruction (you may be familiar with S notation or do not really care how it moves, since machine halts now).

qS 1 _ R qS1 ; state to start scratching left to -
qS - - R q2 ; check if there is 1 after 1
qS1 1 1 R qS1 ; pass through 1
qS1 - - R qS2 ; minus found
qS2 1 1 R qS2 ; going for rightmost 1
qS2 _ _ L qSr ; blank found after all 1
qS2 - - * halt-reject ; second minus found, reject bad formatted input
qSr 1 _ L qSr2 ; scratch last 1
qSr - 1 * halt-accept ; scratched 1 at the beginning appears here.
qSr2 1 1 L qSr2 ; leave 1 as is
qSr2 - - L qSr2 ; leave - as is
qSr2 _ _ R qS ; start another pass

q2 1 1 R q2c ; there is a - but still input may be malformed, check it

q2c 1 1 R q2c;
q2c - - * halt-reject ; found second -, reject
q2c _ _ * halt-accept ; there is negative number on tape, accept

q2 _ _ L q2m ; there is only minus left, clean it up
q2 - - * halt-reject ; malformed
q2m - 0 * halt-accept ; accept after cleanup

; tested on accepting -, 1-, -1, 1-1, 11-1, 111-1, 1-11
; testet on rejecting 1--1, 11-11-, --, -1
; to explore it more, maybe -11-11 should give -1111? Not handled now


Computational complexity of generating a random vector

You can't create a uniformly random number in $[0,1]$ in finite time, because that would require infinite precision.
Probably that's not what you want.  Probably you want to generate a random float in the range $[0,1]$.  Then we have to ask what assumptions you are willing to make about your pseudorandom number generator. For many of them it is probably reasonable to treat generating a random float in that range as taking $O(1)$ time.  If so, you can create a $N$-dimensional vector with $N$ calls to that pseudorandom generator, i.e., in $O(N)$ time.
See How to come up with the runtime of algorithms?, How does one know which notation of time complexity analysis to use?, Is there a system behind the magic of algorithm analysis? and a good textbook for an overview of asymptotic running time analysis.


I'm assuming you meant $l(x) = a^{b-x}/h(x)$, where $a \geq 1$. This term is $o(1)$ so can be ignored. For the main term, we cannot conclude anything since we only have an upper bound on $h$; we would like a lower bound on $h$. It could be, for example, that $g(k) = \log k$ and $h(k) = e^{-k}$, a function certainly satisfying $h(k) = O(k)$, and in that case $f(x) = \Omega(e^x)$.

Assuming you meant $h(k) = \Theta(k)$, or at least $h(k) = \Omega(k)$, we can estimate the sum using an integral:
$$ \sum_{k=0}^x \frac{g(k)}{h(k)} = O\left(\sum_{k=0}^x \frac{\log k}{k}\right) = O\left(\int_0^x \frac{\log k}{k} dk\right) = O(\log^2 x),$$
using $\int \frac{\log k}{k} = \frac{1}{2} \log^2 k$. If $g(k) = \Theta(\log k)$ and $h(k) = \Theta(k)$ then $f(x) = \Theta(\log^2 x)$.


Determining if we can balance these graph weights

This solves the problem if the function $f$ is not constrained to the edges of a spanning tree.

You can think of your problem as a flow problem where each vertex $u\in V$ "generates" $w(u)$ units of flow and "sinks" 1 unit of flow.

To reduce this problem to a standard flow formulation you can create a new directed graph $G' = (V', E')$ in which each edge $e \in E'$ has a capacity $c(e)$:

$V' = V \cup \{s,t\}$,  where $s$ is a new "source" vertex and $t$ is a new "sink" vertex.
For each $v \in V$, add to $E'$ the edge $(s,v)$ with capacity $w(u)$.
For each edge $e \in E$, add $e$ to $E'$ with capacity $c(e) = w(e)$.
For each $v \in V$ add to $E'$ the edge $(v,t)$ with capacity $1$.

Compute the value $f^*$ maximum flow from $s$ to $t$ in $G'$. If $f^* = |V|$ then your all units of flow can be generated and sunk (one unit from each vertex $u \in V$), therefore your problem problem admits a solution.
If $f^* < |V|$ your problem admits no solution (to see this you can show that you can convert any feasible solution to your original problem to a flow of $|V|$ in $G'$).


Fundamental algorithms in formal language-automata theory

They're simple, but the various DFA $\leftrightarrow$ NFA $\leftrightarrow$ RE conversions are quite handy.

Also, being able to find the Parikh mapping of a semilinear language is quite useful for more advanced applications (especially when you get out of the regular languages), since it lets you answer a lot of decidable properties.


min vertex cover to access k edges in a tree

There is a $\mathcal{O}(nk)$ DP approach.

Call an edge covered if we select a vertex next to it. Root the tree at an arbitrary vertex $r$. Define $DP[i][b][t]$ as the maximum number of edges in the subtree of node $i$ that can be covered by selecting at most $t$ nodes from the subtree. If $b = 0$ we are not allowed to select node $i$, and if $b = 1$ we must select it.

If we calculate this DP, we can solve the problem, as the minimum number of nodes to cover $k$ edges is the smallest $t$ for which $max(DP[r][0][t], DP[r][1][t]) \geq k$. Further note that it suffices to only calculate the $DP$ for $t \leq k$, as any $k < n$ nodes cover at least $k$ edges.

To give the recurrence to calculate the DP, we first give the knapsack-function: let $K(V_{1}, \dots, V_{m})$ be an array such that

\begin{equation*}
K(V_{1}, \dots, V_{m})[t] = \max_{t_{1} + \dots + t_{m} = t} \sum_{j = 1}^{m} V_{j}[t_{j}]
\end{equation*}

Note that $K(K(V_{1}, \dots, V_{m-1}), V_{m}) = K(V_{1}, \dots, V_{m})$, and that $K(A, B)$ can be directly calculated by the above formula in $\mathcal{O}(|A| \cdot |B|)$ time. Hence calculating $K(V_{1}, \dots, V_{m})$ takes $\mathcal{O}(\sum_{i = 2}^{m} |V_{i}| \sum_{j = 1}^{i-1} |V_{j}|)$ time regardless of the order we combine the sets in. If we are interested in only the first $k$ values of the DP, the complexity drops to $\mathcal{O}(\sum_{i = 2}^{m} |V_{i}| \min(k, \sum_{j = 1}^{i-1} |V_{j}|))$

Let $C_{i}$ be the set of children of node $i$, and $C_{ij}$ be the $j$th child of $i$. Then
\begin{gather*}
DP[i][0][t] = K(V_{1}, \dots, V_{|C_{i}|})[t]\\
DP[i][1][t] = |C_{i}| + K(V'_{1}, \dots, V'_{|C_{i}|})[t-1]
\end{gather*}
Where
\begin{gather*}
V_{j}[t] = \max(DP[C_{ij}][0][t], DP[C_{ij}][1][t] + 1)\\
V'_{j}[t] = \max(DP[C_{ij}][0][t], DP[C_{ij}][1][t])\\
\end{gather*}
Calculating the answer with this recursion takes $\mathcal{O}(nk)$ time. Informally this is because over the course of the algorithm, we combine single-element DPs into a DP representing the whole tree. We do at most $\frac{n}{k}$ combinations of sets of size $k$, and any element costs us at most $2k$ time (if element $x \in A$ costs us $|B|$ time when calculating $K(A, B)$) before it gets merged into a set of size $k$, so the total amount of work is at most $\mathcal{O}(k^{2} \frac{n}{k} + k n) = \mathcal{O}(nk)$. This is easy but tedious to formalise with induction.

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
const int INF = (int)1e9 + 7;

vector<int> knapsack(const vector<int> a, const vector<int> b, int k) {
    int n = a.size();
    int m = b.size();
    vector<int> c(n+m-1, -INF);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) c[i+j] = max(c[i+j], a[i] + b[j]);
    }
    if (c.size() > k) c.resize(k);
    return c;
}

pair<vector<int>, vector<int>> dfs(int i, int p, int k, const vector<vector<int>>& g) {
    vector<int> dp0 = {0, 0};
    vector<int> dp1 = {-INF, (int)g[i].size() - (p != -1)};
    for (auto t : g[i]) {
        if (t == p) continue;
        vector<int> dp0_t, dp1_t;
        tie(dp0_t, dp1_t) = dfs(t, i, k, g);
        int m = dp0_t.size();

        vector<int> off0(m), off1(m);
        for (int j = 0; j < m; ++j) off0[j] = max(dp0_t[j], dp1_t[j] + 1);
        for (int j = 0; j < m; ++j) off1[j] = max(dp0_t[j], dp1_t[j]);
        dp0 = knapsack(dp0, off0, k+1);
        dp1 = knapsack(dp1, off1, k+1);
    }
    return {dp0, dp1};
}

int minCover(int k, const vector<vector<int>>& g) {
    vector<int> dp0, dp1;
    tie(dp0, dp1) = dfs(0, -1, k, g);
    for (int i = 0;; ++i) {
        if (max(dp0[i], dp1[i]) >= k) return i;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    vector<vector<int>> g(n);
    for (int i = 0; i < n-1; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    int t = minCover(k, g);
    cout << t << '\n';
}


How to find time complexity for functions in lazy functional languages?

I would consider an approach based on potential. Note that lazy evaluation changes the internal state of an object and therefore takes away an important advantage of functional programming.

As an example, imagine the following three functions

sort : List $\rightarrow$ List. Sorts the list using Selection Sort.
unique_special : List $\rightarrow$ List. For every odd position $i$ in the input list, the element at that position is removed from the list if it is equal to the element at $i+1$.
head : List $\rightarrow$ X. Finds the first element of the list.

Given a list $L$, I will use $\Phi(L)$ for its potential. $\Phi(L) : \{1, \dots, |L|\} \rightarrow \mathbb{N}$ is a function describing the cost of each element.

A "clear" list has a constant potential, i.e. $\Phi(L)(i) = 1$ for all indices $i$.

Let L be a list and sort(L) = L'. Then $\Phi(L')(i) = \sum\limits_{j=1}^{|L|} \Phi(L)(j)$, because Selection Sort will have to look at every element in $L$ to find a minimal one. After this, $L$ is completely evaluated, i.e. it is not "lazy" anymore. This means the potential of every element is reduced to $\Phi(L)(i) = 1$. Here you can see the importance of the fact, that lazy evaluation can change within an object. If you assume that is not possible, for example by disallowing variables (e.g. via "where" in Haskell), the analysis becomes easier.

For unique_special, consider again L' = unique_special(L). To evaluate the first element, the next one has to be evaluated as well (to compare them). $\Phi(L')(1) = \Phi(L)(1) + \Phi(L)(2)$. Of course, would $L'(1)$ be evaluated, the potential of $L(1)$ and $L(2)$ would become 1.

Later elements require additional knowledge of whether the previous elements were deleted. You have $L'(2) = L(1)$ if the first element was deleted and $L'(2) = L(2)$ otherwise. Hence, $\Phi(L')(2) = \Phi(L)(1) + \Phi(L)(2)$ and $\Phi(L')(3) = \Phi(L)(1) + \Phi(L)(2) + \Phi(L)(3) + \Phi(L)(4)$.

Generalizing this formula results in $\Phi(L')(i) = \sum\limits_{j=1}^k \Phi(L)(j)$, where $k = \lfloor \frac{i}{2} \rfloor \cdot 2$.

Finally, consider head(L). This does not create a new list, it just requires you to pay the potential of $\Phi(L)(1)$.

As you can see, this clearly increases the complexity of function definitions, especially if you want to include changing potential of the same data structure in your analysis. It gives you the opportunity for a more abstract analysis though:

Let $L$ be a completely evaluated / non-lazy list and the call head(sort(L))). The cost of this call will be $\Phi(\text{sort}(L))(1) = \sum\limits_{j=1}^{|L|} \Phi(L)(j) = |L|$.

A second example: What is the cost of the call head(unique_special(L')), where $L' = \text{sort}(L)$?

\begin{align*}
& \Phi(\text{unique_special}(L'))(1) \\
=& \Phi(L')(1) + \Phi(L')(2) \\
=& \sum\limits_{j=1}^{|L|} 1 + \sum\limits_{j=1}^{|L|} 1 \\
=& 2 |L|
\end{align*}

You can put more detail into the description of $\Phi$ to observe more accurate results.

Regarding generalization to other data structures, I didn't think about that too much so far. It should be clear that similar structures such as queues work in a similar way. However, for example for a Union-Find structure, I can't think of a way my approach would give you any advantage.

An addition regarding non-linear data structures, for example binary search trees. While it is the easiest option, there is no definite need to use a set $\{1, \dots, n\}$ as the domain of $\Phi$. A common way to index the nodes of a binary tree is to use strings in $\{0,1\}^*$. The root is labelled with the empty string $\varepsilon$ and for a node $v$, the left successor is $v0$ and the right successor is $v1$. For example, the following tree

   5
 4   8
1   6 9

would have the domain $\{\varepsilon, 0, 00, 1, 10, 11\}$.

Imagine a function delete : Tree $\times$ Node $\rightarrow$ Tree to remove a certain node from the tree. You need to check if either of the subtrees is empty. Let delete($T$, $v$) = $T'$, then the potential is $\Phi(T')(v) = \sum\limits_{\substack{w \in \{0,1\}^* \\ w \text{ is a descendant of } v}} \Phi(T)(w)$, where we assume $\Phi(T)(w) = 0$ if $w$ is not a node of $T$.


Markov chain probability in a complete graph

The probability that you state is the probability that a random edge of the complete graph connects one of the $k$ nodes to one of the other $n-k$ nodes. This means that in your process, a random edge is chosen, and if exactly one vertex already knows the information, then the other vertex is made aware of it. Information spreads exactly when the chosen edge is of this form, which in your case happens with the probability you mention.


The problem is NP-hard, by reduction from SUBSET-SUM. Given a multiset of numbers $x_1,\ldots,x_n$ and a target $T$, consider $n$ buckets with capacity $C=x_1+\cdots+x_n$, initially filled with $x_1,\ldots,x_n$, and ask whether you can obtain a bucket filled with exactly $T$. You can prove by induction that all buckets are always with filled either with $C$ or with the sum of some (possibly empty) subset of the $x_i$s.


computer science in the movies as an educational angle

I haven't seen it yet, but Travelling Salesman could be pretty interesting.


Context-free grammar for language involving multiplication

Write $L$ in the following way:
$$
L = \{ a^sbc^s : s \in \mathbb{N}^+ \} \cup \{ a^sb^2c^{2s} : s \in \mathbb{N}^+ \} \cup \{ a^sb^3c^{3s} : s \in \mathbb{N}^+ \}.
$$


Countability union of all finite and countably infinite sequences over finite alphabet

Your solution for proving that $\Sigma^*$ is countable is correct.
However the set $\Sigma^\omega$ of infinite sequences is not countable,
since it is in bijection with the set of subsets of $\mathbb{N}$, which is not countable. See this question.


Why does paging not have external fragmentation?

The details depend on the processor architecture, but the principle is the same everywhere. All page tables of a given type at a given level have the same size. When all memory blocks have the same size, there is no fragmentation: a memory block is allocated starts at an offset which is a multiple of the block size, so the size of any hole is a multiple of the block size. If a gap opens in the page table, the operating system can use this gap the next time it needs to allocate a page table.

Furthermore the size of a page table pretty much always divides the size of a page — both are powers of two. So a page contains a whole number of page tables with no leftover space. This means that the operating system can allocate pages for page tables and no table spreads over multiple pages, so there's no need for the page tables to be consecutive and therefore there's no fragmentation of the address space for the page tables themselves.


Lower bounding the minimum equivalent graph

Yes it's too pessimistic. If by 'consistently', we mean we will deduce the existance/non-existance of a hamilatonian cycle a $1-\epsilon$ fraction of the time but will get an incorrect answer the rest of the time, we STILL haven't found a polynomial time algorithm that guarantees coming to the correct conclusion. So it isn't theoretically impossible to 'consistently' lower bound this problem.


The problem can be solved efficiently: in $O(K^2 T \log (KT))$ time.

Build a graph where each vertex corresponds to a pair $(t,i)$, where $t$ is a time step and $i$ is one of the nodes that is allowed to be visited at time $t$.  Add edges from $(t,i)$ to $(t+1,j)$ for every $t,i,j$, with a length that corresponds to the travel time from $i$ to $j$.  Add a source node $s$ with edges from $s$ to each $(1,i)$ of length 0, and a sink node $t$ with edges from each $(T,i)$ to $t$ of length 0.  Then, find the shortest path in this graph from $s$ to $T$.

The graph has $O(KT)$ vertices and $O(K^2T)$ edges, so Dijkstra's algorithm for finding shortest paths will run in $O(K^2 T \log (KT))$ time.


The number of Binary Search Tree that exist with same Postorder and Inorder

Your confusion might stem from this: The number of binary trees on $n$ vertices is $C_n$, the $n$-th Catalan number. Since in a BST, the left-right order of vertices is fixed, the number of BSTs with a given inorder traversal is also $C_n$. However, with the added restriction that the postorder traversal must be the same as the inorder traversal, the BST can only have left branches.

In more detail, recall that inorder = left-visit-right and postorder = left-right-visit.

If both traversals must be the same (visit is at the root) there can be no right subtree, and this is then the same at the left child, and so on. This leaves only one form: a tree with only children to the left.

What is your book stating, more precisely? Perhaps we can find the reason for the confusion.


Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?

The difference is IMHO well explained in that book, the part you are referring to says

  The number of anonymous functions in an expression is understood to be equal to the number of times the asymptotic notation appears.

So this $$ \sum_{i=1}^n O(i) $$

means a placeholder for $$ \sum_{i=1}^n f(i), $$

where $f(i)$ is an anonymous function from the set $O(i)$ — but it is always the same function in all terms of the sum. However, in $O(1) + O(2) + \dots + O(n)$, each term represents a placeholder for a (potentially) different anonymous function $f_i$ from the set $O(i)$. Note the book also says, the latter has "no clear interpretation", so it is quite meaningless.


How do I find maximum and minimum number of times the search loop will execute when searching through an array of 1,048,576 integers

I assume your input is random and your array of size $N$, $A[1..N]$.

In case of binary search if the number you are searching for is located at $(1+N)/2$, i.e. right in the middle of the input array then you will find it after the first if-statement.

Similarly in case of sequential search, if number your are searching for is the first element of the array then you stop after the first if-statement.

In both cases you do only one comparison.


How large would a database containing perfect knowledge of chess be?

Claude Shannon indicated that the State Space Complexity (number of legal positions reachable from the initial position in chess) has a lower bound of approximately $10^{43}$. If each entry consists of $20$ bytes, as indicated in your question. The total number of bytes for your database would have a lower bound of $2 * 10^{44}$ which is a very large number indeed.

I would suggest reading Section 2: General Considerations of Shannon's paper, Relevant quote:

  Another (equally impractical) method is to have a "dictionary" of all possible positions of
  the chess pieces. For each possible position there is an entry giving the correct move
  (either calculated by the above process or supplied by a chess master.) At the machine's
  turn to move it merely looks up the position and makes the indicated move. The number of
  possible positions, of the general order of $64! / 32!(8!)^2(2!)^6$
  , or roughly $10^{43}$, naturally
  makes such a design unfeasible.

References:

https://en.wikipedia.org/wiki/Game_complexity
Programming a Computer for Playing Chess - Shannon


Maximum number of states in NFA concluded from the converted DFA

No, because there is no maximum.  There are infinitely many NFA's that are all equivalent and accept the same language.  For instance, you can take any NFA you think it might have come from and add some extra disconnected states, and the new NFA will also have the same language and thus could correspond to the same DFA.

(Your only hope is that if you know exactly what conversion procedure was used, and if the conversion procedure retains useless states and forms a bijection from NFAs to DFAs, then maybe.  But in practice I would not expect ordinary conversion procedures to have that property.)


What's the relationship of $n^n$ and $n!$ complexity with respect to EXPTIME?

$\mathsf{EXPTIME}$ is the class of problems solvable by algorithms whose running time is $O(2^{n^c})$ for some $c>0$. In contrast, $\mathsf{E}$ is the class of problems solvable by algorithms whose running time is $O(2^{cn})$ for some $c>0$.

These definitions show that problems solvable in time $O(n!)$ or $O(n^n)$ are in $\mathsf{EXPTIME}$, but not necessarily in $\mathsf{E}$.


Does "static" or "dynamic" imply a compiler or interpreter implementation of a programming language?

First, as a commenter mentioned, there isn't necessarily a clear general distinction between compilers and interpreters. A compiler is a program that takes source code, and produces a program which takes the input and produces the output. An interpreter is a program that takes source code and an input and produces the output. Under this definition, there are fairly trivial ways of converting an interpreter into a compiler and vice-versa (this is called the curry/uncurry operation in functional programming). There are also some more interesting general ways like partial evaluation.

What is true is that you may define the execution semantics of many programming languages may be defined on an abstract machine which loses much of the information in the original program. Most interpreters do this in some sense.

Second, keep in mind that all the various uses of "static/dynamic" are different things. For example, a static architecture is one where each component may only be connected to a fixed set of other components, while a dynamic architecture is one where some process connects them (e.g.: dependency injection). Most compilers are completely unaware of your application's architecture, so this question is pretty irrelevant for static/dynamic architecture.

In particular, for your question, "static typing" and "dynamic typing" are not really even on the same dimension. "Dynamic typing" is not a type system, although using it typically requires having an Any type. "Static typing" is usually just called "typing."

Anyway, from both a practical and theoretical perspective, anything an interpreter can do a compiler can do, and vice versa.


Difference between logic, fuzzy logic, probabilistic logic, quantum logic?

Russell and Norvig catalogue a few formal languages in the following table[*]:

\begin{array} {lll}
\hline
\text{Language} &
\text{Ontological Commitment} &
\text{Epistemological Commitment}
\\
&
\text{(What exists in the world)} &
\text{(What an agent believes about facts)}
\\
\hline
\text{Propositional logic} &
\text{facts} &
\text{true/false/unknown}
\\
\text{First-order logic} &
\text{facts, objects, relations} &
\text{true/false/unknown}
\\
\text{Temporal logic} &
\text{facts, objects, relations, times} &
\text{true/false/unknown}
\\
\text{Probability theory} &
\text{facts} &
\text{degree of belief $\in [0, 1]$}
\\
\text{Fuzzy logic} &
\text{facts with degree of truth $\in [0, 1]$} &
\text{known interval value}
\\
\hline
\end{array}

(Note this is within the context of artificial intelligence.)

So the most important difference between fuzzy logic and probabilistic logic seems to be that in probabilistic logic you do not deal with degrees of truth, only degrees of belief.

I couldn't tell you very much about quantum logic other than that it appears to have originated in this paper by Birkhoff and von Neumann.

[*] Russell, S. and Norvig, P. (2009). Artificial Intelligence: A Modern Approach (third edition). Pearson. Chapter 8, First-Order Logic.


Find m smallest elements in an array of size n where m = n/2

Find the median in $O(n)$ time. Then go over the array and take out all elements smaller than the median.


For the sake of notation, let's call a family of languages $\mathcal{L}$ that contains

the empty set $\emptyset$ and
all singleton sets $\{a\}$, $a$ some symbol,

a founded family, and

$\qquad\displaystyle \mathcal{L}_+ = \{ L \in \mathcal{L} \mid \varepsilon \not\in L\}$.

Let $L \in \mathrm{REG}_+$ arbitrary. We will construct $L$ from only the empty and singleton sets using the trio operations

$\varepsilon$-free homomorphism,
inverse homomorphism and
intersection with regular languages,

thus proving that (1) all founded trios also contain $\mathrm{REG}_+$. Furthermore, (2) $\mathrm{REG}_+$ it is a founded trio itself. Therefore, we have shown that $\mathrm{REG}_+$ is the minimal founded trio.

It suffices to show that $\Sigma^+ \supset L$ is contained in every founded trio $\mathcal{T}$; the rest is trivial by $L = \Sigma^+ \cap L \in \mathrm{REG}_+$.

We define for any alphabet $\Sigma$ a marked copy $\hat{\Sigma} = \{ \hat{a} \mid a \in \Sigma \}$ and two homomorphisms $h,g : \Sigma \cup \hat{\Sigma} \to \Sigma^*$ by

$\qquad\displaystyle
  h(a) = \begin{cases}
           a &, a \in \Sigma \\
           \varepsilon &, a \in \hat{\Sigma}
         \end{cases}
$

and

$\qquad\displaystyle
  g(a) = \begin{cases}
           b &, a = b \in \Sigma \\
           b &, a = \hat{b} \in \hat{\Sigma}
         \end{cases}
$.

Now consider

$\qquad\displaystyle L' = \Sigma \hat{\Sigma}^*$.

By noting that

$\Sigma = h(L') \iff h^{-1}(\Sigma) = L'$,
$g(L') = \Sigma^+$ and
$g$ is $\varepsilon$-free,

we obtain from the trio closure properties that

$\qquad\displaystyle \Sigma \in \mathcal{T} \implies \Sigma^+ \in \mathcal{T}$.

But since $\Sigma$ is the pre-image of every $\{a\} \subseteq \Sigma$ with suitable constant homomorphism $h_a(b) = a$ we have $\Sigma \in \mathcal{T}$ by foundedness and closure under inverse homomorphism.
We check the conditions of a founded trio for $\mathrm{REG}_+$:

Closure under $\varepsilon$-free homomorphism: clear since $\mathrm{REG}$ has this property and no such homomorphism can generate $\varepsilon$ from an $\varepsilon$-free language.
Closure under inverse homomorphism: clear since $\mathrm{REG}$ has this property and the image of $\varepsilon$ is always $\varepsilon$.
Closure against intersection with regular languages: clear by def.
Foundedness: clear by def; all required sets are regular and don't contain the empty word..

$\mathrm{REG}$ actually is the minimal "founded" trio if you add $\{\varepsilon\}$ to the base; a similar proof goes through.

Furthermore, $\mathrm{REG}_+$ is not a full trio (cone) because of it's lack of empty words. We extend above proof by noting that containment of $\mathrm{REG}_+$ now implies containment of $\mathrm{REG}$ (any regular language $L$ is the image of $\hat{a}L \in \mathrm{REG}_+$ by a homomorphism that deletes only $\hat{a}$). Since $\mathrm{REG}$ is itself a cone it is also the minimal cone.

The properties extend to (semi-)AFLs, i.e. $\mathrm{REG}_+$ is the minimal (semi-)AFL and $\mathrm{REG}$ is the minimal full (semi-)AFL.


I suggest you start by looking at BDDs and ZDDs.

Your problem is similar to the problem of finding an optimal BDD.

I'll explain.  Suppose we have sets $S_1,\dots,S_k$ over a universe $U$ containing $n$ items (so $S_i \subseteq U$).  A BDD is a finite-state automaton (a DAG) for recognizing the language of all of the allowed sets, where each set is presented to the finite-state automaton as the $n$-bit string that is the characteristic function of that set.  In other words, given a total order on $U$, each set $S \subseteq U$ corresponds to a binary string $[S] \in \{0,1\}^n$: $[S]_i=1$ if $S$ includes the $i$ element of $U$, otherwise not.  (This order is known in the BDD literature as a "variable ordering".)  Then define the language $L$ by $L=\{[S_1],[S_2],\dots,[S_k]\}$.  A BDD is a finite-state automaton that recognizes the language $L$.

Notice that you have the freedom of what "variable ordering" to choose.  The choice of the variable ordering determines how each set is represented as a binary function, which can affect the size of the BDD.  It is well-known that the problem of choosing the optimal variable ordering (the one that leads to the smallest BDD) is NP-hard.  Nonetheless, there are various heuristics for trying to find a good variable ordering, and in real-world problems, they often work reasonably well.

So, your problem can be framed as the problem of choosing the optimal variable ordering to represent your sets as a BDD.

ZDDs are a variant of BDDs that are better in some circumstances.  ZDDs are especially oriented at representing a set of sets, so they might be particularly helpful for your needs.  ZDDs are especially handy if you need to represent a bunch of sets that are related to each other in some way; ZDDs provide a compact and efficient encoding for that situation.


I think you're mixing up the weight vector $w$ and the actual hyperplane defining the decision boundary. The way to interpret $w$ is as a vector which is orthogonal to any vector lying on the hyperplane. See these slides for some visualization.

As you've said, the decision is defined by $1$ if $w_1 x + w_2 y > 0$ and $0$ otherwise. So to find the actual hyperplane (decision boundary) we can just solve for the place where the decision changes, which is at $0$. Using your $w$ we have
$$
\begin{align*}
w_1 x + w_2 y &= 0\\
\implies 5 x + -5y &= 0\\
\implies x &= y.
\end{align*}
$$
So the decision boundary is given by the line $y = x$. Plotting this with your points we see that this $w$ does indeed define a separating hyperplane.


Showing Context Free Grammars that are regular if and only if L(G) = Σ∗.

This proof-snippet is what you are probably looking for.

We follow your definition. $N$ is a fixed non-regular context-free language over $\Sigma$, $\#$ is a new symbol. For a given grammar $G$ let $L = N\#\Sigma^* \cup \Sigma^* \# L(G)$. Assume $L(G) = \Sigma^*$, then $L = \Sigma^*\#\Sigma^*$ which is a regular language. On the other hand, if $w\notin L(G)$, then $L\cap \Sigma^*\#w = N\#w $, which is not regular (as regular languages are closed under quotient, and $N$ is not regular). Thus also $L$ itself is not regular (as regular languages are closed under intersection).

Conclusion: $L$ is context-free, and $L$ is regular iff $L(G) = \Sigma^*$.


Need of reducing problems if we already know that a problem is undecidable

There's a difference between the statements:

There is an undecidable problem.

and

The problem HALT(TM) is undecidable.

For the first one, it sounds like you proved by by showing directly

The problem A(TM) is undecidable.

The point of using a reduction, is that it lets you deduce the undecidability of HALT(TM) from the undecidability of A(TM), as opposed to starting "from scratch".  More generally, reductions let you compare the hardness of different problems to each other, which is a general theme in computability and complexity.


Shortest distance between a point in A and a point in B

I have a solution which may seem a bit convoluted, but should be more efficient than the naive $\mathcal O(n^2)$ brute-force search:

let $v$ be the axis between the centres of mass of $A$ and $B$.
Sort the points in $A$ and $B$ along this axis in descending and ascending order respectively, resulting in the sequences $a_0$, $a_1$, ... , $a_n$ and $b_0$, $b_1$, ... , $b_n$.

The rest is in pseudo-code to make it clearer:

d = infinity.
for j from 1 to n
    if (b_1 - a_j) along v > d then break endif
    for k from 1 to n
        if (b_k - a_j) along v > d then
            break
        else
            d = min( d , ||b_k - a_j|| )
        endif
    enddo
enddo

That is, by pre-sorting the points along $v$, you can filter out pairs that will never be within $d$ of each other since $b_k-a_j$ along $v$ will always be $\le \|b_k-a_j\|$.

In the worse case this is still $\mathcal O(n^2)$, but if $A$ and $B$ are well separated, it should be much faster than that, but not better than $\mathcal O(n\log n)$, which is required for the sorting.

Update

This solution is by no means pulled out of a hat. It's a special case of what I use in particle simulations to find all the interacting pairs of particles with spatial binning. My own work explaining the more general problem is here.

As for the suggestion to use a modified line-sweep algorithm, although intuitively simple, I'm not convinced that this is in $\mathcal O(n\log n)$ when disjoint sets are considered. The same goes for Rabin's randomized algorithm.

There doesn't seem to be much literature dealing with the closest pair problem in disjoint sets, but I've found this, which makes no claim to being under $\mathcal O(n^2)$, and this, which doesn't seem to make any claims about anything.

The algorithm above can be seen as a variant of the plane sweep suggested in the first paper (Shan, Zhang and Salzberg), yet instead of using the $x$-axis and no sorting, the axis between the sets is used and the sets are traversed in descending/ascending order.


Given a binary tree $t$, prove that $size(t) < 2^{h(t)}$

If a binary tree has height $h$ then it has at most 1 node at depth 0, at most 2 nodes at depth 1, ..., at most $2^{h-1}$ nodes at depth $h-1$ (the maximal depth), and so at most $1+2+\cdots+2^{h-1} = 2^h-1$ nodes in total.

You can also prove this by induction. When $h=1$, the tree consists only of a root, so at most $1=2^h-1$ vertices. Given a tree of height $h$, its two subtrees have height at most $h-1$, and so together contain at most $2(2^{h-1}-1)$ vertices. Together with the root, the tree contains at most $2(2^{h-1}-1)+1=2^h-1$ vertices.


Find a regular grammar that generates words with even number of a's

"How do I make sure that $b$'s can be put anywhere in between $a$'s in v and u?"
Hint, you may need another non-terminal.

Here is a hint about the higher-level approach to the question although you did not ask for it, since it looks like you are not in the reasonably correct way to move forward. I would also encourage you to go forward with your approach as far as possible, if only to experience and see why it does not work (it may work in the end).

Let us define two simpler languages,
$$E=\{w | w\in \{a,b\}^*, |w|_a = 0(\text{mod } 2)\}$$
and $$O=\{w | w\in \{a,b\}^*, |w|_a = 1(\text{mod } 2)\}.$$

Can you write regular grammar for $E$ and $O$ ? Can you piece together some E's and O's to form $L$?

Once you have done the problem, you might be able to see a general strategy on how to generate regular grammars for these "simple" languages.


Suppose that $L_1 \in \mathsf{P}$ and $L_2$ is non-trivial. Pick $y \in L_2$ and $z \notin L_2$ arbitrary. The following is a polynomial time reduction from $L_1$ to $L_2$:

Input: $x$.
Check whether $x \in L_1$.
If so, output $y$.
Otherwise, output $z$.

This runs in polynomial time since $L_1 \in \mathsf{P}$.


Loop Invariant Code Motion - am I missing something?

You can also replace with

if (loop_condition) {
    loop_invariant_code
    do {
        loop_body
    } while (loop_condition)
}

With all he precautions of course. That makes the loop a bit simpler, and saves one test of the condition. And because you have no extra evaluations of loop_condition, this should be correct even if loop_condition has side effects.

And in the first example starting with i = 10 you should be able to optimise the first loop condition away.

But absolutely, you cannot just move code with side effects out of a loop, and you should be careful moving code without side effects, in case the loop is not executed and the moved code just wastes time. This more critical in languages that do overflow checks, so adding a+b can actually have a side effect on overflow.

Note: The wikipedia article also mentions strength reduction (for example, instead of calculating i*6, set tmp = 0 before the loop starts, and increase tmp by six at each iteration). Setting tmp = 0 would also only be executed if the loop condition is tested once.


How to determine likely connections in a social network?

What you're looking for is a heuristic. No algorithm can say, given a graph of friends as the only input, whether two individuals not directly connected are friends or aren't; the friendship/acquaintance relation isn't guaranteed to be transitive (we can assume symmetry, but that might even be a stretch in real life). Any good heuristic will therefore need to be based on an understanding of how people interact, rather than some mathematical understanding of the nature of graphs of relations (although we will need to quantify the heuristic in these terms).

Suggesting friends of friends with equal probability is a relatively cheap but inaccurate heuristic. For instance, my father has friends, but I wouldn't say I'm friends with any of them (although I'd probably say I'm a friend of my father's for the purposes of, e.g., a social network). Having a person at a relatively close distance doesn't necessarily make them a great candidate.

Suggesting people to whom you have a great many extended connections also seems like a poor choice in general, because this will tend to lead to exponential growth of friends of people who pull ahead early on (the seven degrees of separation from Kevin Bacon game is an example of this).

I suggest a circuit-based model. Assume that each link is a resistor of resistance $R$. Then the best candidate for a new friend might be the individual with the lowest equivalent resistance. Here's a poorly-executed ASCII graphics example:

  _____
 /     \
a---c   f
|   | /
b   d---e
| \ |
g   h   i

Say we want to find new friends for a. a's current friends are b, c, and f. We evaluate the net equivalent resistance between a and each of d, e, g, h, and i:

pair   resistance
(a,d)   6/7
(a,e)  13/7
(a,g)   7/4
(a,h)   1/1
(a,i)   inf

According to this heuristic, d is the best candidate friend, followed closely by h. g is the next best bet, followed closely by e. i can never be a candidate friend by this heuristic. Whether you find the results of this heuristic to be representative of real human social interactions is what's important. Computationally speaking, this would involve finding a subgraph containing all paths between two individuals (or, perhaps interestingly, some meaningfully selected truncation of this), then evaluating the equivalent resistance between the source and sink nodes.

EDIT: So what's my social motivation for this? Well, this might be a rough model of how hard it is to get in touch with, and subsequently communicate possibly significant amounts of information through, intermediaries (friends). In CS terms (rather than physics terms), this might be construed as bandwidth between two nodes in a graph. Extensions of this system would be to allow different kinds of links between people with different weights (resistance, bandwidth, etc.) and proceed as above.


Restrictions that set binary variable to 1 when integer variable equals x, 0 otherwise

In this case (where the possible sets of values are finite) a graphical approach can work nicely for determining a suitable set of constraints. Draw the points in the set $\{1,\dots,12\}\times\{0,1\}$ in the plane, using $+$ for allowed and $-$ for disallowed combinations:

$\begin{array} & & + & - & - & - & - & - & - & - & - & - & - & - \\
 & - & + & + & + & + & + & + & + & + & + & + & +\end{array}$

Can you find a set of lines separating the $+$s from the $-$s? Note that $Y+MONTH\ge 2$ already take care of the $-$ in the bottom left corner.


$O(n\log n)$ algorithm for minimizing number of inversions in leaves of complete binary tree

Let us denote by $L(x)$ the set of leaves in the subtree rooted at $x$. The idea is that the decision whether to switch the two children $x_1,x_2$ of $x$ depends only on $L(x_1),L(x_2)$, and depends on how many of the pairs $(a,b) \in L(x_1) \times L(x_2)$ satisfy $a < b$ and how many satisfy $b < a$.

If the sets $L(x_1),L(x_2)$ were available to you in their sorted forms, then you could count the number of pairs of each type by merging these sets and doing some accounting. This suggests a recursive algorithm which sorts the leaves using the merge sort strategy.

Details left to you.


Best pathfinding algorithm for undirected unweighted graph

assuming you don't have any heuristic function about the distance to the target, a good solution that is valid is bi-directional BFS:
Algorithm idea: do a BFS search simultaneously from the source and the target: [BFS until depth 1 in both, until depth 2 in both, ....].
The algorithm will end when you find a vertex v, which is in both BFS's front.

Algorithm behavior: The vertex v that terminates the algorithm's run will be exactly in the middle between the source and the target.
This algorithm will yield much better result in most cases then BFS from the source [explanation why it is better then BFS follows], and will surely provide an answer, if one exist.

why is it better then BFS from the source?
assume the distance between source to target is k, and the branch factor is B [every vertex has B edges].
BFS will open: 1 + B + B^2 + ... + B^k vertices.
bi-directional BFS will open: 2 + 2B + 2B^2 + 2B^3 + .. + 2B^(k/2) vertices.

for large B and k, the second is obviously much better than the first.

NOTE, that this solution does NOT require storing the whole graph in memory, it only requires implementing a function: successor(v) which returns all the successors of a vertex [all vertices you can get to, within 1 step from v]. With this, only the nodes you open [2 + 2B + ... + 2B^(k/2) as explained above] should be stored. To further save memory, you can use Iterative Deepening DFS from one direction, instead of BFS, but it will consume more time.

In your case, the difference between BFS and bi-directional BFS, assuming 6 degrees of seperation is between developing ~200^6 = 2.4e13 nodes, and 2*200^3=16,000,000. As you can see, bi-directional BFS needs much less nodes to be developed than the alternative.

Disclaimer: Most of this answer (except the last part) is copied from my answer on StackOverflow.com, as suggested in meta (and effectively applied by a mod in security.SE)


Is occurrence typing (flow-sensitive typing) a form of dependent typing?

No, I would not consider this a dependent type.  The type of x does not depend on the value of x.
I suppose you could say that the type of the expression x depends on the type of the variable x, but that doesn't make this dependent typing.
You link to Wikipedia, but the Wikipedia article on dependent types say "a dependent type is a type whose definition depends on a value" and says " The return type of a dependent function may depend on the value (not just type) of one of its arguments" and "A dependent pair may have a second value of which the type depends on the first value".  Here the type of x does not depend on values; only on the types of the variables.  Beware that these English sentences describing terms like "dependent types" or "occurrence types" are not to be taken too seriously and you need to look at the precise mathematical formalism if you want to be precise.
I would not consider the feature you describe as dependent typing.  Rather, I would consider it an instance of flow-sensitive typing.


How does left-factoring prevent backtracking?

Suppose the input is ab. In compiler terms you have two tokens a and b which are read in linear sequence. So, when you read a it is not clear which production rule to apply since you have three possible rules which begin with a: $A \rightarrow ab \mid ac \mid ad$. To choose the right production rule you need check all possible rules which is done by backtracking.

However, if you factor this grammar  then you have only one production rule which begins with a: $A \rightarrow aB$ which is the only single possible rule and thus there is no need in backtracking.

Nondeterminism, when parsing, can be resolved using lookahead technique, where left-factoring is one of the steps in order to transform the initial grammar into $LL(k)$-grammar.  For more details please read about $LL(k)$-parsers.


comparison in speed between the processor and the hard disk

This is to some extent a comparison between apples and oranges. The assumption is that the basic operation on a CPU takes 1 ns (since the clock frequency is 1 GHz), whereas a basic operation on the hard disk takes 4 ms. The quoted factor is just 4 ms / 1 ns = 4×106.


Turing machine and language decidability

A TM decides a language if it enters the accepting state for word in the language and it enters the rejecting state if it is not. Thus it halts on all inputs. Note the machines defined above are not entirely standard. They way they denote acceptance and reject is by writing a $1$ or $0$ and then by entering a halting state. This is equivalent to the standard definition, but less elegant.

Machine 1 does not reject words not in the language. It only accepts the language.

Machine 2 does not halt for words not in the language. It only accepts the language.

Machine 3 rejects and hence halts for words not in the language, therefore it decides the language.


Min-entropy of a random pre-image of a random function

Since $X_v$ is a random variable which is uniformly distributed over its support $F^{-1}(v)$, its min-entropy depends only on the size of the support (and it equals the entropy). The min-entropy is at most $n/4$ if and only if $|F^{-1}(v)| \leq 2^{n/4}$. Now $|F^{-1}(v)|$ is binomially distributed $\mathrm{Bin}(2^n,2^{-n/2})$, since for each string $x \in \{0,1\}^n$, the probability that $F(x) = v$ is $2^{-n/2}$. Therefore you are interested in bounding
$$
\Pr[\mathrm{Bin}(2^n,2^{-n/2}) \leq 2^{n/4}].
$$
You can obtain a good bound on this event, which is rather unlikely, using Chernoff's bound or Hoeffding's bound. Let us know if you encounter any difficulties.


Finding the Big-O and Big-Omega bounds of a program

$1.6180^n$ is not an upper bound to the running time of your program, not even up to multiplicative constants (in fact it is a lower bound).
However $O(\phi^n)$ is a valid upper bound, where $\phi = \frac{1+\sqrt{5}}{2} > 1.618$ is the golden ratio. It is also easy to see that your program takes $\Omega(\phi^n)$ time, so the above upper bound is asymptotically tight.
That said, $\phi^n \not\in O(n^2)$, so that answer is incorrect.
Moreover, $\phi^n \not\in \Omega(e^n)$ since $\phi < e$, so that answer is incorrect too.
Finally, notice that your answers contradict each other since you say that the running time of the program is both in $\Omega(e^n)$ and in $O(n^2)$ but $\Omega(e^n) \cap O(n^2) = \emptyset$.


Think of the file system and its files as a big cabinet with lots of physical folders in an office of bureaucrats. The sheets in the folders are arranged in fixed ways such that every bureaucrat knows exactly where to expect which information before taking the folder out of the cabinet.

Not let us assume that a bureaucrat (a program) performs a certain operation on a folder/file. It will take the folder to the desk, spread the sheets on the desk, cut certain things out, glue them together, paint marking son certain sheets, translates the text of a sheet to a new one, discards sheets entirely, add sheets, and do all kinds of crazy stuff on the data on the desk in the way that the bureaucrat wants it to do. After all that, the bureaucrat puts the relevant sheets nicely back into the folder such that everything is orderly, puts the folder back into the cabinet and then throw everything that is left on the desk back into the trash bin.

Note that the bureaucrat's desk is the RAM in this analogy. Now how are things stored on the desk? Well, that depends on what precise step the bureaucrat performs at a time instant. Even more, different bureaucrats doing essentially the same task may do things in a different order. So we can't really say anything about the organization of a bureaucrat's/program's desk/RAM other than whatever is put back into the cabinet/file system is put there orderly. In between, it is up to the bureaucrat how things are stored and in which encoding.

For most data in the RAM, the question how it is encoded does however make sense. However, this encoding can change frequently. For example, when a web browser receives text from a server, it may change the encoding multiple times before the data is actually displayed.

I hope that this analogy helps clearing things up. It has its limits, though, as in a computer, folders are not taken out of the cabinet, but they are rather copied and later overwritten, as this is cheaper in a computer than it is in real life. Also, because the memory sizes of the processes in a computer are not fixed, there is memory management going on, and one can say something about where memory allocation information is stored and how that information is encoded.


If I have a large random array of 0s and 1s that I want to sort what kind of an algorithm and data structures should I consider?

Use counting sort: run through the array once and count the number of 0's. Then run through the array once more and write in it the counted number of 0's, followed by 1's. In any case, this is a purely academic exercise because nobody would ever need to do such a thing in real life.


A uniform shuffle of a table $a = [a_0, ..., a_{n-1}]$ is a random permutation of its elements that makes every rearrangement equally probable. To put it in another way: there are $n!$ possible rearrangements of $n$ elements and you need to pick one of them uniformly at random.

Many methods for shuffling seem uniform to people but are not and so it is common to see them implemented badly. For instance, shuffling by repeatedly exchanging two randomly chosen elements, as in the question, is not uniform and is also wasteful, as it generates twice as many random numbers as necessary.

A simple algorithm for a uniform shuffle is this:

import random
def shuffle(a):
    n = len(a)
    for i in range(n-1):
        j = random.randint(i, n-1)
        (a[i], a[j]) = (a[j], a[i])

This works in time $\Theta(n)$ as follows: assuming $a_0, ..., a_{i-1}$ are already shuffled, randomly select an element $a_j$ among the remaining $a_i, ..., a_{n-1}$ and exchange it with $a_i$.

To see that the result is uniformly shuffled, observe that initially every element has $\frac{1}{n}$ chance to land in place $0$ and $\frac{n-1}{n}$ to land in one of the remaining places $1, \ldots, n-1$. Therefore place $0$ is uniformly shuffled. In the next step, every element has probability $\frac{1}{n-1} \cdot \frac{n-1}{n}$ to land in place $1$, because this happens when it is not placed at 0 (probabilty $\frac{n-1}{n}$) and it is selected to be at place 1 (probability $\frac{1}{n-1}$). We may proceed inductively: an element lands in place $i$ with probability
$$\frac{n-1}{n} \cdot \frac{n-2}{n-1} \cdot \frac{n-3}{n-2} \cdot \cdots
  \cdot \frac{n-i}{n-i+1} \cdot \frac{1}{n-i} = \frac{1}{n}.$$
The first $i$ factors arise for an element not being placed anywhere among places $0, \ldots, i-1$, and the last one for it being chosen to be placed at $i$.


Build an FA that accepts only the words baa, ab, and abb and no other strings longer or shorter

The question is not clear as formed: if you want an NFA which is not a DFA and matches the language then you could take your DFA and add a new unreachable state with an $\epsilon$-transition to itself, or add other $\epsilon$-transition self-loops or many other things that will not change the language.
If the aim is to use non-determinism to reduce the size of the automaton, then you can omit the garbage state (so that the word would just "fall out of" the NFA at that point). Given that you have already optimised the paths for $ab,abb$ (based on their shared prefix) and $baa$ has no shared prefix or suffix with the other words, it looks like this is the only possible optimisation to be made.


Reason for finding partial order of a graph

One possible use: It lets you answer the question "is vertex $y$ reachable from vertex $x$?" in $O(1)$ time.


Let me explain how to solve this, leaving all details to you.

Given an instance $(G,k)$ of CLIQUE, we want to construct an equivalent instance of $\frac{n}{3}$-CLIQUE, say $G'$. Let us denote by $|G|$ the number of vertices in $G$. There are several cases to consider:

Case 1: $k = |G|/3$. In this case you can take $G' = G$.
Case 2: $k > |G|/3$. In this case you want to increase the number of vertices to $3k$ without changing the size of the maximum clique.
Case 3: $k < |G|/3$. This is the most complicated case. You want to increase the number of vertices to some $n'$ while increasing the size of the maximum clique by some $\Delta$. You are done if you can ensure that $k+\Delta = n'/3$. (In fact, it suffices to have $k+\Delta > n'/3$, since then we can use Case 2.)

You take it from here.


Applications for boolean logic operations in zero-one integer linear programming (ILP)

Yes, there are many applications.  To find some, go to that question and look through the linked and related questions on the sidebar; that will already show you several applications.  Next, do a search for the search term "ILP" on this site, and browse through the search results.  You will find many examples of problems that can be solved with zero-one ILP using these techniques.


Select largest subset, subject to a separate weighting constraint

Use dynamic programming.

Let the $(c,w)$ pairs be $(c_1,w_1),\dots,(c_n,w_n)$.  Define $A[k^*,n^*,W^*]$ to be the largest possible sum of $c$-values obtainable by selecting $k^*$ pairs from $(c_1,w_1),\dots,(c_{n^*},w_{n^*})$ such that the sum of their $w$-values is at least $W^*$.  Then you can write down a recursive definition of $A[k^*,n^*,W^*]$:

$$A[k^*,n^*,W^*] = \max(A[k^*,n^*-1,W^*], A[k^*-1,n^*-1,W^*-w_{n^*}]+c_{n^*}).$$

Now fill in this table using dynamic programming.  The running time will be $O(nkW)$, where $n$ is the number of $(c,w)$-pairs in the input.

This is basically an adaptation of the dynamic programming algorithm for the knapsack problem: https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem


In computer science how is using passive voice regarded?

The bottom line advice is: Use whichever voice best aids understanding.

Many people over-use the passive voice, thinking that it makes them sound more scientific.  In practice, it's more common for the passive voice to make sentences harder to follow.

Therefore, as a rough guideline, it's helpful to use the following principle: use the active voice whereever possible.  If you find yourself writing in passive voice, check whether your sentence would be clearer, simpler, or easier to understand if written in the active voice.

I recommend you read style guides on clear writing.  You'll find they tend to warn against over-use of passive voice: active voice often makes sentences simpler, more direct, more forceful, more vivid, and thus both more concise and more memorable.  Strunk & White have some good examples of this guideline; see, e.g., Rule 11 and Rule 12.

There are some special cases where there are conventions or norms within the field that are worth following.  See, e.g.,

Use of “I”, “we” and the passive voice in a scientific thesis
Is it recommended to use “we” in research papers?.


Minimum number of vertices whose removal makes the graph an independent set

Yes, and the algorithm is straight forward branching.

Suppose that you are given a graph $G$ and an integer $k$.  If $k = 0$, we simply return whether $G$ is an independent set.  If $G$ is an independent set, we return "yes".  Otherwise, we branch.  If there is an edge $uv$ in $G$, we recurse on $G-u, k-1$ and $G-v, k-1$.  Since the budget drops with one for every recursive call, we call ourselves at most $2^k$ times.

The correctness is left as an exercise.


Bias of first values produced by a family of RNGs

Yes.  This general approach (use a hash of the index as seed to your prng) is a sound way to perform repeatable but pseudorandom experiments.

The most critical factor is to choose the pseudo-random number generator wisely, so that its statistical properties are sufficient for the kind of simulations you are doing.  Some pseudo-random number generators are especially awful: for instance, on some platforms rand() is terrible (its least significant bit alternates between 0 and 1), and Excel's RAND() has been criticized in the statistical literature.  So, choose wisely.  But this issue is more a matter of choosing a suitable pseudo-random generator, which is something you need to do anyway.

It's important to include the hashing step.  If you don't do that, then you're feeding closely related seeds into the pseudo-random generators.  For some pseudo-random generators, bad things might happen: you might get closely related outputs.  For instance, that's exactly what the article you mentioned is warning about, when you use Java's Math.random().  Using a good hash function will fix this, because now the seeds to the pseudo-random generator will look unrelated (each bit will be different with probability about 1/2, etc.).

In particular, if you're concerned about this risk, one extremely effective solution is to use a strong cryptographic hash function (e.g., SHA256) as your hash.  This ensures that the resulting seeds will look entirely unrelated.  After all, any detectable relationship in the resulting seeds would likely count as a "break" of the cryptographic hash function, and would be huge news.  So, heuristically, if you use a cryptographic hash function to hash the index and use its output as the seed, you're likely on safe ground.  This can be formalized using the random oracle model, but I'll spare you the technical details -- you can read more about that sort of analysis in the cryptographic literature if you really want, but in the interests of space, I'll spare you all the mathematics.

I expect that using a good hash will be more effective/reliable than throwing away the first few numbers, and more effective than trying to choose a different pseudo-random number generator.  Those alternatives are a crapshoot: they might work, but they might not.  In contrast, there is sound science behind the "hash the index and use the result as a seed" approach.


Convert integer of mixed radix to standard positional numeral system and vice versa

If you have numbers $x_1,\ldots,x_n$ in the ranges $x_1 \in \{0,\ldots,b_1-1\},\ldots,x_n \in \{0,\ldots,b_n-1\}$, you can get a number in the range $\{0,\ldots,b_1\ldots b_n-1\}$ using the formula
$$
x_n + b_n x_{n-1} + b_n b_{n-1} x_{n-2} + \cdots + b_n b_{n-1} \cdots b_2 x_1 = \\
x_n + b_n (x_{n-1} + b_{n-1} (x_{n-2} + \cdots )).
$$
The second formula gives an efficient way of calculating the transformation (from inside out), and also hints at calculating the inverse transformation efficiently.


Solving recurrence relation with square root

The answer cannot be $O(\log\log n)$. Already without applying any recursion we have the inequality $T(n) = T(\sqrt{n}) + n \ge n$. So the complexity cannot be smaller than $O(n)$.

But now to your computation.  Setting $n=2^m$, we obtain as you did
$$ T(2^m) = T(\sqrt{2 ^ m}) + 2^m=T(2 ^ {\frac{m}{2}}) + 2^m.\tag{1}\label{eq1}$$ You defined $$S(m) = T(2^m).$$ Then equation $\eqref{eq1}$ should become the following equation,
which is different from $S(m)\,$$= S(\frac{m}{2})\,$$ + m$, the wrong equation in the question.

$$S(m) = S\left(\frac{m}{2}\right) + 2^m.$$

The equation above falls into the third case of the master theorem, therefore $S(m) \in \Theta(2^m)$. And from this follows $T(n) \in \Theta(n)$.


Classification when some classes are dependent

I'm afraid there is no exact answer to your question.
In the scenario you described above male and female mammals are very similar, similar enough that the average person wouldn't notice the difference.
In such a case, I would suggest going with the first option of classifying into 10 classes of mammals and then building 10 classifiers of male-female.

This of course isn't an answer that applies to all cases, it is strongly dependent on a few factors, mainly on the classification scenario at hand.
The size of the dataset is also a significant parameter.
Unfortunately I don't think there is a methodological way to address this issue, only experience can point you towards the best solution.


Context-free grammar for $L=\{0^n1^{2n} \mid n \geq 0\}$

As Yuval commented, this is a very basic exercise so you should probably go over the basic definitions. One simple answer for this particular question is:
$$S\rightarrow0S11|\varepsilon$$


Kolmogorov Complexity proving there exists a constant for when if two strings are equal length

Consider a procedure which has two inputs, $P$ and $DIFF$. Here $P$ is a self-delimiting program, and $DIFF$ is a list of indices, stored in some self-delimiting fashion (we leave the encoding vague for now). The procedure runs $P$, flips all the indices in $DIFF$, and prints the output. Using the invariance property of Kolmogorov complexity, we immediately get that there is a program of length $|P|+|DIFF|+O(1)$ which simulates the procedure above.

Now take any two vectors $x,y$. Let $P$ be a self-delimiting program of size $C(x)$ producing $x$, and let DIFF be the list of differences, which can be encoded using $H(x,y)(1+\lceil \log |x| \rceil)$ bits (this improves on your exercise; we're using the fact that $|x|$ is known by the procedure). It follows that $C(y) \leq C(x) + H(x,y)(1+\lceil \log |x| \rceil) + O(1)$.


There are probably better examples, but here is one, off the top of my head:

Let's say you want to check whether the edit distance between two strings $S,T$ is $\le d$, and if it is, compute the edit distance.  You can use the standard dynamic programming algorithm to compute the edit distance, but "prune" the computation (stop the recursion) at any place where the edit distance is known to be $>d$.  This means you probably won't need to fill in the entire table; you'll only need to fill in some of the entries.  Thus, using a dictionary can give a performance boost.


What does the $^*$ operator do in the theory of parsing?

It does exactly what you describe: $L^*$ contains all possible finite concatenations of words in L, including the empty word. This operator is known as the Kleene star, it is fundamental in the theory of regular languages and more generally of grammars.


How do I check for the "preference" of non queues vertices?

The previous step was

          if switching v to the opposite set improves the sum of weights then
             switch v;

so clearly you already know how to check for the preference of a vertex. Whether or not it is in the queue is immaterial.

To do it efficiently requires some additional data storage and pre-calculation which is not explicitly described in the pseudocode. In more detail,

Best_Non_Overlapping_Pairs(G: weighted graph)
    repeat k times
       randomly assign each vertex to either V1 or V2 with equal probability;

       initialise two arrays of edge weight sums, internalSums and externalSums
       for each edge e = (s, t) in E do
          if s and t are in the same partition
             increment internalSums[s] and internalSums[t] by weight(e)
          else
             increment externalSums[s] and externalSums[t] by weight(e)

       for each vertex v in V do
          put v on the queue;
       loop until the queue is empty
          pop v from the queue;
          if internalSums[v] > externalSums[v]
             switch v;
             swap internalSums[v] and externalSums[v]
             for each edge e = (v, u) in E do
                update internalSums[u] and externalSums[u] appropriately
                if u is not in the queue and internalSums[u] > externalSums[u]
                   enqueue u
       store the best solution to date;

  Is it even needed? I've implemented the algorithm without this part and it seems working as intended.

I must confess that I would be unable to distinguish easily between the algorithm working as intended and the algorithm selecting a purely random partition and skipping the rest of the process.