PAC learning model definition The probably approximately correct (PAC) learning model is defined as:

A concept class $C$ is said to be PAC-learnable if there exists an algorithm $A$ and a polynomial function $poly(·,·,·,·)$ such that for any $ε>0$ and $δ>0$, for all distributions $D$ on $X$ and for any target concept $c∈C$, the following holds for any sample size $m≥poly(1/ε,1/δ,n,size(c))$:

$Pr[R(hs)≤ε]≥1-δ$

where $R(hs)$ is the generalization error over a sample $S$ of size $m$ containing instances of variable $X$ following distribution $D$ and $size(c)$ is the maximal cost of the computational representation of $c∈C$.

I know $poly(1/ε,1/δ,n,size(c))$ is a polynomial. But what is the explicit form of $poly(1/ε,1/δ,n,size(c))$? What are the variables? What is its degree?

There are no constraints on $poly(\cdot,\cdot,\cdot,\cdot)$ other than its being a polynomial, or more generally, a polynomially bounded function (that is, a function bounded by a polynomial); the difference doesn't matter in this case. Without loss of generality, you can assume that for some $A,B > 0$, $poly(x,y,z,w) = A(xyzw)^B$.

The definition is trying to model the situation that only a small number of samples is needed to learn the concept. In order to quantify "small", we need first to decide with respect to what quantities it is going to be small (in this case, $\epsilon,\delta,n,size(c)$), and second, how small is "small". In this case, we define "small" to be any function growing at most polynomially in $1/\epsilon,1/\delta,n,size(c)$. In other cases we have more stringent requirements, say we want "small" to be polynomial in $\log \frac{1}{\epsilon}, \log \frac{1}{\delta}, n, size(c)$.

A standard definition in complexity theory is that of polynomial time. We say that an algorithm for solving some problem is efficient if on an input of size $n$ it runs in time polynomial in $n$, that is, its running time $T(n)$ is bounded by some polynomial in $n$. In your terminology, we could state this as $T(n) \leq poly(n)$ for some polynomial $n$. As before, if $T(n) \leq poly(n)$ for some polynomial $poly(\cdot)$, then in fact $T(n) \leq An^B$ for some $A,B>0$, and so without loss of generality we can assume that $poly(n) = An^B$. But we don't want to decide in advance on the values of $A,B$. We are happy as long as some values of $A,B$ work.

Your case is similar, only the polynomial is allow to depend on several quantities rather than just one quantity.


An approximate quantity of multiplications in $\mathbb{F}_p$ amounting the same bit complexity as one inversion in $\mathbb{F}_p$ Consider a prime finite field $\mathbb{F}_p$ of quite large characteristics $p$, for example $\log_2(p) \approx 256$ bits. I would like to know an approximate quantity of multiplications in $\mathbb{F}_p$ amounting the same bit complexity as one inversion in $\mathbb{F}_p$. Of course, this depends on many factors, hence I propose to listen your ideas rather than exact results. May be, is there an article or book, which discusses this topic?

The standard algorithm for inverting an element is using the extended Euclidean algorithm. You can read all about this connection on Wikipedia.


Functor in category theory: The free theorem for fmap According to nLab article:
https://ncatlab.org/nlab/show/functor

Definition
External definition
A functor $F$ from a category $C$ to a category $D$ is a map sending each object $x \in C$ to an object $F(x) \in D$ and each morphism $f : x \to y$ in $C$ to morphism $F(f) : F(x) \to F(y)$ in $D$, such that

$F$ preserves composition: $F(g\circ f) = F(g)\circ F(f)$ whenever the left-hand side is well-defined,

$F$ preserves identity morphisms: for each object $x \in C$, $F(1_x) = 1_{F(x)}$.

So, functor is often called "structure preserving".
However, there is an interesting article:
https://www.schoolofhaskell.com/user/edwardk/snippets/fmap

The free theorem for fmap
When we write down the definition of Functor we carefully state two laws:

fmap id = id
fmap f . fmap g = fmap (f . g)

These are pretty well known in the Haskell community.
What is less well known is that the second actually follows from the first and parametricity, so you only need to sit down and prove one Functor law when you go to supply a Functor!
This is a “folklore” result, which I've used in conversation many times before, but it continues to surprise folks, so I decided to write up a slow, step by step proof of this result as it is a fun little exercise in equational reasoning.
To prove this we're going to need the free theorem for fmap and a few lemmas.

So, my question is does this apply not only to the category of set and function composition but also category theory in general?
Thanks.

Composition following from identity does not hold for the category of sets and functions (to my knowledge), if by that you mean the sets and functions in ZF(C) or the like that mathematicians usually consider. As you mentioned, the given argument relies on parametricity, and the functions definable in set theory needn't be parametric. In fact, assuming that all functions are parametric is anti-classical. Even in constructive scenarios which could admit parametric models, people might want to keep their options open.
It's probably not a huge surprise in light of the above, but things aren't going to work out in a lot of other situations, either. For instance, the argument you referenced is essentially appealing to parametricity to obtain naturality, because parametricity is a stronger requirement than naturality (based on a notion that doesn't involve composition). However, Haskell functions (or those of similar systems) are parametric with respect to a specific sort of "logical relation" that subsumes naturality with respect to a specific category. This parametricity does not automatically imply naturality even with respect to certain related categories. For instance, if you consider functors $\mathsf F, \mathsf G : \mathsf{Type}_M → \mathsf{Type}$ from a Kleisli category, then a parametric function with type $∀ a. \mathsf F(a) → \mathsf G(a)$ is not automatically natural. So, there are examples like this where functoriality doesn't automatically follow just from the identity rule.
For instance, consider the Kleisli category for lists. There is a functor:
$$\mathsf F : \mathsf{Type}_{\mathsf{List}} → \mathsf{Type}$$
$$\mathsf F\ A = \mathsf{List}\ A$$
where the action of $\mathsf F$ on arrows is given by the following code:
-- drops one element of the list unless it has only one element
contract : List A → List A
contract (_ :: xs@(_ :: _)) = xs
contract xs = xs

mapF : (A → List B) → List A → List B
mapF f [] = []
mapF f (x :: xs) = contract (f x) ++ mapF f xs

This action on arrows doesn't satisfy the composition rule, but it does satisfy the identity rule. There is a functorial action for this object mapping (it is the 'bind' operation), but mapF is another function with the same type and behavior on the Kleisli identity arrow (pure or return in Haskell).
I would imagine that composition following from identity is the exception rather than the rule.


Sorting almost sorted array Encountered this question but I couldn't solve with the complexity they solved it:

Suppose I have an array that the first and last $\sqrt[\leftroot{-2}\uproot{2}]{n} $ elements has $\frac{n}{5}$ inverted pairs, and the middle $n - 2\sqrt[\leftroot{-2}\uproot{2}]{n}$ elemnts are sorted. What is the complexity of sorting the unsorted array?

They claim in the answer that sorting array with $I$ inversions is $O(n\log{\frac{n}{I}})$.Why?

If you have an array with a sequential range that covers all but k elements, and you know the range, then you sort the k elements in O (k log k), then merge two ranges that you know to be sorted in O (n). That sorts the whole array in O(n) as long as k is O (n / log  n).

In your case k = $O (n^{1/2})$ so clearly you can sort the array in O (n).

And you don't need to know the sorted range, because for large n we have n/2 inside the sorted range, so you can just count the elements in ascending / descending order from n/2 upwards / downwards.


Why is the manifold hypothesis true? The manifold hypothesis is the statement that real-world high dimensional data (such as images) lie on low-dimensional manifolds embedded in the high-dimensional space. It has been tested to be true quite extensively. So could someone explain or give some intuition why it is true? Why doesn't real world data such as dogs form manifolds of same dimension as the image space?

Presumably you don't really get a manifold.

For one thing, there's probably a nonzero chance of any particular coordinate being perturbed arbitrarily -- an impurity in a crystal, a grey hair on a head of brown ones, etc. -- so you'd really get something more like a probability distribution concentrated near a lower dimensional platonic ideal.

Second, there are probably all sorts of behaviors going on that aren't allowed in a manifold, like self-intersections, edges, and components of different dimensions.

That said, simple statements like "the left side of someone's face usually looks about like the mirror image of the right" cut the dimensionality of the space nearly in half.  Add enough such independent conditions and you whittle things down quite a bit.


The content of an implication from the snm-Theorem I have a question on the statement of the s-m-n Theorem and the implication
$$
 \varphi_{f(x,y)} = \lambda z \varphi_x(\varphi_y(z))
$$
for some recursive function $f(x,y)$ cited in the above link. In what sense does this follows from the s-m-n theorem and in what sense does it gives anything new?

To be more specific. As I see it to apply the s-n-m-theorem the function on the right side must be partial recursive or computable, but $\varphi_x(\varphi_y(z))$ is just the composition of computable functions (by the universal turing machine theorem $(y,z) \mapsto \varphi_y(z)$ and so on are computable). But knowing this already says that it has some Gödel coding, and the fact that this is effective (and total) is given by the typical proofs that the composition of computable functions is computable (i.e. by giving an algorithm to construct a suitable Turing machine). So the statement that there exists some recursive $f(x,y)$ gives nothing new to what I know from the basic proof that the composition of computable functions is computable?

So have I missed anything? Or in what sense does this follow from the snm-theorem? And does it states anything nontrivial?

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.


Turing machine - definition of program - naive question In the paradigm of Turing machines what is considered a program?
Can't find a definition anywhere.
Is it a member of L(M)?

The Turing machine itself is the program.
You can see this in universal Turing machines. A universal Turing machine accepts a description $\langle M \rangle$ of a Turing machine $M$ and an input $x$, and runs $M$ on $x$. Thus $M$ (or rather, $\langle M \rangle$) is the code or program, and $x$ is the input or data.


Benes (Fat Tree) Network for number of inputs/outputs that is not 2^n I was reading about Benes Network construction in this book.
Their construction is easy for a number of inputs and outputs that is an exponent of two.

However it seems to me that for a number of i/o that falls between $2^{n}$ and $2^{(n+1)}$ one has to construct a network with $2^{(n+1)}$ ports and leave many unattached, which is wasteful.
Is there a synthesis method for Benes networks or maybe an alternative topology that has the same properties (re-arrangeable not blocking) for arbitrary number of I/O?

Wasting ports to achieve an exact number of terminals is a common attribute of staged networks (butterfly, benes, folded-clos, etc.). The mesh, torus, and flattened butterfly topologies are a bit better because each dimension can have a different width, but this results in having uneven bisection bandwidth along each dimensional cut. The HyperX topology is a generalization of the flattened butterfly that allows each dimension to be configured independently in terms of width and weight (number of links connecting each pair of routers). The paper describes an algorithm to find the "optimal" configuration given a requirement for system size, bisection bandwidth, and router radix. An implementation of this algorithm is here. Given the requirements, it finds a satisfactory topology configuration that minimize cost (like wasted ports).


Measuring entropy for a table (e.g., SQL results) We're running some benchmarks for an approximative query-answering system. It's sufficient to just think of it as running some SQL queries with joins. We are counting the results returned as part of the benchmark. However, the results often contain a lot of redundancy, so just counting results seems coarse.
Consider the following table containing results for a query like "for the US, give me its states and its car manufacturers":
================================
|| ?us_state | ?us_car_manu   ||
||============================||
|| Alabama   | Chrysler       ||
|| Alaska    | Chrysler       ||
|| ...         ...            ||
|| Wyoming   | Chrysler       ||
|| Alabama   | General Motors ||
|| Alaska    | General Motors ||
|| ...         ...            ||
|| Wyoming   | General Motors ||
|| Alabama   | Ford           ||
|| Alaska    | Ford           ||
|| ...         ...            ||
|| Wyoming   | Ford           ||
===============================

All 200 (50 × 4) results are of course unique. However, given that there is an inherent Cartesian product, the number of results flatters the amount of "information content" or "entropy" of the table: every additional car manufacturer adds fifty results for the fifty US states. (Again, this is just an example; I'm not interested in better ways to represent or run this particular query.)
As such, we're looking for a metric that will give an indication as to the (loosely speaking) redundancy-free content in the table for better comparison of content across different results for different queries. Other result tables may contain a mix of different types of Cartesian products (e.g., consider generalising the query to any country, where each country itself has its own product of states and car manufacturers, etc.).
Currently we're working off a simple metric which just counts unique term–position combinations: for the above example, the metric gives 50 + 4 = 54. This may be sufficient for comparison, but is not sensitive to the combination of terms for individual results.
Thanks to Wikipedia, I'm aware of—but not familiar with—the notion of entropy in information theory. However, I'm unclear on how the concept of entropy could be applied to this use-case. (I'm not interested in the entropy of the result strings; each term can be considered a "symbol".) Roughly speaking, each query variable could be considered as a free variable with the result terms in that column providing a set of possible outcomes and their frequency of occurrence being used as a probability mass function. This way I could compute the Shannon entropy for each column. But thereafter, I don't know how columns can be combined, or how tuples or results can be considered ... if a notion of conditional entropy would be better, etc.
And so ...

Does anyone have pointers to related material on the measure of entropy/redundancy/etc. in tables or similar structures?
Otherwise, does anyone have any ideas on how to use Shannon entropy in a convincing way for tabular data?

Information-theoretic approach to database dependency theory has long history; here is couple of references:

An information-theoretic approach to normal forms for relational and XML data by  M. Arenas and L. Libkin (2005)
Information dependencies by M. M. Dalkilic and E. L. Roberston (2000)


A slightly different version of the halting problem I got stuck with a question and would like to have a little guidance for the solution.

I need to prove that the next problem is undecidable:

Input - A program
Problem - Does the number of possible inputs for which the program halts is larger than those for which the program won't halt?

I tried to build a reduction that (in case the input is even) halts for every even number, goes to an infinite loop for every odd and runs the program with the input. Or in case the input is odd does the opposite - but it only works if I am able to prove that the number of real odd numbers is equal to the real even numbers.

I won't give you the solution - I think you're on the right track. However I will give a possible way of making this question precise:

Prove that this problem is undecidable:

Input: A (code for a) Turing Machine $M$
Output: $\texttt{Accept}$ if the number of inputs for which $M$ halts is a finite number $\leq n$
$\texttt{Reject}$ otherwise.

Since there are an infinite number of inputs, if $M$ halts for a finite number of them, then it doesn't halt for an infinite number of them.

Of course, it's possible for a machine to halt on an infinite number of inputs, and not halt on an infinite number of inputs (say, halt on even numbers and not on odd numbers). In this case, a hypothetical machine for this problem would $\mathtt{Reject}$.

You might notice some similarity to the halting problem at this point.


P vs. NP and Godel's Theorems This post is based loosely on a previous post, but the presentation is somewhat different and hopefully much more succinct.
Basically, I'm wondering if it is plausible for there to be a formal proof of P!=NP if ZF is consistent (obviously the converse is true). The idea is this: since proofs to sentences in ZF can be viewed as witnesses in an NP-language, if P!=NP then this means that for some fixed $k$ not all provable sentences $\phi$ of ZF have a proof of length $\leq {|\phi|}^k$. But if ZF is inconsistent, then every sentence of sufficient length has a relatively short proof derived from a fixed contradiction. So we get that P!=NP implies that ZF is consistent. So if we have a formal proof of P!=NP then this would imply through Godel's Second Incompleteness Theorem that ZF is inconsistent (and thus P=NP) as well. Is there a problem with this approach?

if P!=NP then this means that for some fixed $k$ not all true sentences $\phi$ of ZF have a proof of length ≤ $|ϕ|^k$.

You do not need to assume $P \neq NP$ to prove this claim. If all true sentences $\phi$ of ZF have a proof of length $\leq |\phi|^k$ then the halting problem could be solved by enumerating all proofs of "$M$ is halting" and "$M$ is not halting" up to that size. So it's not possible for all true sentences to have a short proof. Instead of  $|\phi|^k$ we can take a function that grows even faster, e.g. $2^{2^{2^{|\phi|}}}$. There's no computable limit on how long a proof can be compared to its statement.
However, to speak about true sentences, we are assuming implicitly that ZF already has a model. So this reasoning does not prove that ZF is consistent - it assumes it from the start. There's no contradiction between "not all true statements have a short proof" and "all statements have a short proof" if there are no true statements.


Why is b-tree search O(log n)? B-tree is a data structure, which looks like this:

If I want to look for some specific value in this structure, I need to go through several elements in root to find the right child-node. The I need to go through several elements in the child-node to find its right child-node etc.

The point is, when I have $n$ elements in every node, then I have to go through all of them in the worst case. So, we have $O(n)$ complexity for searching in one node.

Then, we must go through all the levels of the structure, and they're $log_m N$ of them, $m$ being the order of B-tree and $N$ the number of all elements in the tree. So here, we have $O(log N)$ complexity in the worst case.

Putting these information together, we should have $O(n) * O(log n) = O(n * log n)$ complexity.

But the complexity is just $O(log n)$ - why? What am I doing wrong?

You have introduced $n$ and $m$ as the order of B-tree, I will stick to $m$.

Their height will be in the best case $\lceil log_m(N + 1) \rceil$, and the worst case is height $\lceil log_{\frac{m}{2}}(N)\rceil$ but there is also a saturation factor $d$, that you have not mentioned.
The height will be $O(log N)$, please notice that $m$ disappeared, because it effectively is multiplication by a constant.
Now at every node you have at most $m$ sorted elements, so you can perform binary search giving $log_2(m)$, so the proper complexity is $O(log(N) * log(m))$.
Since $m << N$, and what is more important, is that it does not depend on $N$, so it should not be mixed, or it might be given explicitly (with $m$ not $N$ or appearing $n$).


How is the traveling salesman problem verifiable in polynomial time? So I understand the idea that the decision problem is defined as

  Is there a path P such that the cost is lower than C?

and you can easily check this is true by verifying a path you receive.

However, what if there is no path that fits this criteria? How would you verify the answer of "no" without solving the best path TSP problem, and finding out the best one has a worse cost than C?

NP is the class of problems where you can verify "yes" instances. No guarantee is given that you can verify "no" instances.

The class of problems where you can verify "no" instances in polynomial time is co-NP. Any language in co-NP is the complement of some language in NP, and vice-versa. Examples include things like non-3-colourability. The problem you describe, "Is there no TSP path with length at most $C$?" is also in co-NP: if you unpick the double-negation, a "no" instance to that problem is a "yes" instance to TSP and we can verify those in polynomial time.

There are some problems, such as integer factorization and any problem in P, that we know to be in both NP and co-NP. (Thanks to user21820 for pointing this out.)

It's not known whether NP and co-NP are the same set of problems. If they're the same, then we can verify both "yes" and "no" instances of TSP. If they're different, then P$\,\neq\,$NP, since we know that P$\,=\,$co-P (because we can just negate the answer of a deterministic machine, giving the answer to the complement problem).


How to reduce the low-rank matrix completion problem to integer programming? Consider the low-rank matrix completion problem:

  Given an integer $k$ and a subset of entries of some $n \times n$ matrix, fill in the rest of the entries so that the resulting matrix has rank at most $k$.

This problem is clearly in NP, since the set of additional entries is the required certificate. Therefore, it can be written as an integer program. How can one do this?

I'm having trouble seeing how to get rid of a rank constraint, even at the expense of adding integer constraints.

Simplifying the problem:

  Given

  a positive integer $r$
  positive integers $m, n \geq 2$
  a partial binary matrix $\mathrm A \in \{*, 0,1\}^{m \times n}$ (where $*$ denotes an unknown entry)

  determine whether it is possible to complete the given partial matrix $\mathrm A$ with values in $\{0,1\}$ such that the resulting completed matrix has rank at most $r$.

Let us consider an example.

Example

Let $r = 2$, $m = n = 3$ and

$$\mathrm A = \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & *\end{bmatrix}$$

Visual inspection of partial matrix $\mathrm A$ tells us that if the unknown $(3,3)$ entry is $0$, then the rank of the completed matrix is $2$. However, it would be nice not to have to rely on visual inspection.

If the rank is at most $2$, then there are matrices $\mathrm U, \mathrm V \in \{0,1\}^{3 \times 2}$ such that $\rm A = U V^{\top}$ holds at all known entries of $\rm A$. From the $(1,1)$ entry, we obtain the equation

$$(u_{11} \cdot v_{11}) \oplus (u_{12} \cdot v_{12}) = 1$$

where addition and multiplication are done over the finite field $\mathbb F_2$. Translating the equation above to propositional logic, we obtain

$$\Phi_{11} := \mbox{Xor} \left( u_{11} \land v_{11}, u_{12} \land v_{12} \right)$$

If $a_{ij} = 1$, we have $\Phi_{ij}$. If $a_{ij} = 0$, we have $\neg \Phi_{ij}$. Taking the conjunction of the CNFs of $\Phi_{ij}$ or $\neg \Phi_{ij}$, we obtain the following formula

$$\Psi := \mbox{CNF} (\Phi_{11}) \land \mbox{CNF} (\neg \Phi_{21}) \land \mbox{CNF} (\neg \Phi_{31}) \land \mbox{CNF} (\Phi_{12}) \land \mbox{CNF} (\Phi_{22}) \land \mbox{CNF} (\neg \Phi_{32}) \land \mbox{CNF} (\Phi_{13}) \land \mbox{CNF} (\Phi_{23})$$

which is in CNF by construction. If $\Psi$ is satisfiable, then there are matrices $\mathrm U, \mathrm V \in \{0,1\}^{3 \times 2}$ such that $\rm A = U V^{\top}$ holds at all known entries of $\rm A$. Using SymPy:

from sympy import *

u11, u12, u21, u22, u31, u32 = symbols('u11 u12 u21 u22 u31 u32')
v11, v12, v21, v22, v31, v32 = symbols('v11 v12 v21 v22 v31 v32')

Phi11 = Xor(u11 & v11, u12 & v12)
Phi21 = Xor(u21 & v11, u22 & v12)
Phi31 = Xor(u31 & v11, u32 & v12)

Phi12 = Xor(u11 & v21, u12 & v22)
Phi22 = Xor(u21 & v21, u22 & v22)
Phi32 = Xor(u31 & v21, u32 & v22)

Phi13 = Xor(u11 & v31, u12 & v32)
Phi23 = Xor(u21 & v31, u22 & v32)
Phi33 = Xor(u31 & v31, u32 & v32)

Psi = to_cnf(Phi11) & to_cnf(Not(Phi21)) & to_cnf(Not(Phi31)) & to_cnf(Phi12) & to_cnf(Phi22) & to_cnf(Not(Phi32)) & to_cnf(Phi13) & to_cnf(Phi23)

print "Formula Psi is \n", Psi

# is Psi satisfiable?
print "\nSatisfiable? \n", satisfiable(Psi)

produces $\Psi$ (in CNF)

And(Or(Not(u11), Not(u12), Not(v11), Not(v12)), Or(Not(u11), Not(u12), Not(v21), Not(v22)), Or(Not(u11), Not(u12), Not(v31), Not(v32)), Or(Not(u21), Not(u22), Not(v21), Not(v22)), Or(Not(u21), Not(u22), Not(v31), Not(v32)), Or(Not(u21), Not(v11), u22), Or(Not(u21), Not(v11), v12), Or(Not(u22), Not(v12), u21), Or(Not(u22), Not(v12), v11), Or(Not(u31), Not(v11), u32), Or(Not(u31), Not(v11), v12), Or(Not(u31), Not(v21), u32), Or(Not(u31), Not(v21), v22), Or(Not(u32), Not(v12), u31), Or(Not(u32), Not(v12), v11), Or(Not(u32), Not(v22), u31), Or(Not(u32), Not(v22), v21), Or(u11, u12), Or(u11, v12), Or(u11, v22), Or(u11, v32), Or(u12, v11), Or(u12, v21), Or(u12, v31), Or(u21, u22), Or(u21, v22), Or(u21, v32), Or(u22, v21), Or(u22, v31), Or(v11, v12), Or(v21, v22), Or(v31, v32))

and the satisfying assignment

{v31: False, v11: True, v32: True, u31: False, v22: True, u22: True, u11: True, v21: False, u12: True, u21: False, v12: False, u32: False}

Hence,

$$\mathrm U = \begin{bmatrix} 1 & 1\\ 0 & 1\\ 0 & 0\end{bmatrix}$$

$$\mathrm V = \begin{bmatrix} 1 & 0\\ 0 & 1\\ 0 & 1\end{bmatrix}$$

and, thus,

$$\mathrm U \mathrm V^{\top} = \begin{bmatrix} 1 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\end{bmatrix} + \begin{bmatrix} 0 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & 0\end{bmatrix} = \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & \color{red}{0}\end{bmatrix}$$

Thus, if the missing entry of $\rm A$ is zero, then we obtain a rank-$2$ matrix.

Translating to binary integer programming, formula $x_i \lor x_j$ becomes the linear inequality $x_i + x_j \geq 1$ and $\neg x_i$ becomes $1-x_i$. From $\Psi$ (in CNF), we obtain $32$ linear inequalities

$$\begin{array}{rl} - u_{11} - u_{12} - v_{11} - v_{12} &\geq -3\\ - u_{11} - u_{12} - v_{21} - v_{22} &\geq -3\\ & \vdots\\ v_{31} + v_{32} &\geq 1\end{array}$$

plus the inequality constraints $0 \leq u_{ij}, v_{ij} \leq 1$ and the integrality constraints $u_{ij}, v_{ij} \in \mathbb Z$.

To summarize, we reduced a simplified version of the original matrix completion problem to SAT and then we reduced SAT to binary integer programming. However, the reduction to SAT requires the computation of the CNF of either $\Phi_{ij}$ or $\neg \Phi_{ij}$, which produces a formula whose number of conjuncts may be non-polynomial in $r$.


Question on Virtual memory and Physical memory This is the question where I'm stuck:
With a 32-bit virtual address, 4 KB pages(12 offset bits), and 4 bytes per page table
entry, we can compute the total page table size:

Number of page table entries = 2^(32-12) = 2^20
Size of page table is 2^20 * 2 = 4MB

I understand this, but what I don't get is that each page table entry is of 4 bytes which is 32 bits. That would make the Physical address= 32+ 12 (offset bits)= 44 bits. Wouldn't it?

I've read and understood the point that Virtual Memory size should be bigger than Physical address because that's when the Virtual memory can hold more memory value (Main memory+Disk, though virtually) than the physical address. Am I right?

Also, I've found a block diagram showing all virtual
addresses pointing to physical through a page table, and from  there they are mapped to main memory and disk address; mapped to disk if valid bit is 0 or else mapped to main memory.

Let me know if I'm wrong anywhere.

The page entry contains other things than the base of the physical page.  Typically:

a present or absent bit (to handle the case where the page is not present in the memory: is on disk or just does not exist)
access right: may the process read, write, execute the page
some kind of use count (to help the OS makes its choice when there is a need page out)

and obviously some bits may be unused or reserved for future usage.

Note that, although in 64-bit system we are in a phase where the virtual address space is bigger than the physical address space, historically on architectures which lived long enough that tends to be followed by a phase where the physical address space is bigger than the virtual one.  The additional memory may be visible only by the OS (which will put other processes there), or even made available to user processes with some kind of bank switching (see extended and expanded memory or more recently PAE in x86 world, some other architectures have had similar things)


Is a BST considered a data structure or abstract data type and why?

It seem abstract in that it is and idea created and implemented with nodes  arranged a certain way.

But it did not show up in the text here:

https://en.wikipedia.org/wiki/Abstract_data_type

Here:

https://en.wikipedia.org/wiki/Binary_search_tree

they are referred to as data structure b.c. other ADTs can be created from them.

In this train of thought, can I assume that SLLs and DLLs are data structures as well.

Is is not so black and white, perhaps more of a spectrum of classification?

A binary search tree is a data structure.  The interface it supports (the list of operations you can perform on it and their semantics) is an abstract data type.

See https://en.wikipedia.org/wiki/Abstract_data_type for explanation of the difference between an ADT and a data structure.


Can we reduce an NP to an NP Problem? Lets say Problem A,B are in NP.

Can we reduce Problem A to B? Meaning A $≤_p$ B? or A $≤_t$ B

Is there a difference in "hardness" of a Problem even in NP?

Or must Problem B at least be NP-Complete?

It depends on the problems. Just knowing that $A$ and $B$ are in $NP$ doesn't tell you whether $A$ is reducible to $B$.

If $B$ is in $P$ and $A$ is $NP$-complete, then $A$ cannot be reduced to $B$ (unless $P=NP$).

If $A$ is in $P$ then it can be reduced to any problem $B$ except $\emptyset$ and $\Sigma^*$.

If $B$ is $NP$-complete then any problem (in $NP$) can be reduced to it.


Knapsack-like problem with profit formula Given two sets of $N$ integers, weights and reps, that store info about some dumbbells, find out the maximum profit by taking at most $M$ dumbbells. Each dumbbell can be taken at most once.

The profit is given by the following formula:
$$
\min(\mathit{takenweights}) \times \sum_{i=1}^m \mathit{takenreps}(i),
$$
where $m \leq M$.

For example, if $M = 3$, the weights are $3,5,6,2,4,9$, and the reps are $8,3,4,10,7,4$, then the output should be $60$, obtained by taking the third, fifth and sixth dumbbells (minimum weight $\min(6,4,9) = 4$ and total rep $4+7+4=15$).

I was thinking of using two double arrays, one for the minimum and one for the profit, where $dp(i,j)$ is the maximum profit obtained by taking $i$ dumbbells among the first $j$, and $dp_{\min}(i,j)$ is the minimum for $dp(i,j)$.

However, I couldn't find a recursion formula.

Do you have any suggestions?

One simple algorithm is as follows. Start by choosing the dumbbell which is going to have the minimum weight (we are going to try all possibilities). Then take the $M$ dumbbells with maximal rep among those with weight above the minimum weight (if there are enough).

To implement this algorithm efficiently, start by sorting the dumbbells according to weight and according to rep (separately), and find the $M$ dumbbells with maximal rep. Now go over the dumbbells in order of weight, each time removing the dumbbell with lowest weight and updating the set of $M$ best dumbbells. If you're careful you might be able to implement this in $O(N)$, so together with the initial sorting, the algorithm might run in time $O(N\log N)$.


Coloring a cubic-graph with 2 colors Given a cubic graph, I want to color its vertices in 2 colors (Say A & B).

A vertex is considered "Good" iff the majority of its neighbors is colored differently than that vertex. (For example, vertex colored A has neighbors  A B B is considered Good, and a vertex colored A has neighbors A A B is considered "Bad")

I suggest the following algorithm:

Pick a random uncolored node
Color it in a way that 2 of its neighbors are X, and the last one is Y (Sometimes of course the neighbors are already colored and we determine from that what color the node needs to be and its neighbors also)
Color the node Y

Running this algorithm seems to work, but I couldn't find an example that it doesn't. And even worse - I cannot even understand how to even begin the proof that this algorithm is correct (if at all)

I feel like I need to use the fact that this is a cubic-graph. But I cannot seem to understand how would that help me here.

EDIT (Observations):

It seems that if I get to pick X uncolored nodes, may graph would have at least X "good" nodes (According to the algorithm)
That X would be at least |V|/4

I want to start by proving that there can be more than |V|/4 "Good" nodes, because in all of my examples there are at least |V|/2 "Good" nodes.

A 2-coloring of a cubic graph in which all vertices are good is known as an unfriendly partition. Such a coloring always exists, and the following algorithm finds it:

Start with an arbitrary coloring, say everything is colored blue.
While there exists a bad vertex: pick some bad vertex, and flip its color.

Why does the algorithm terminate? Consider the number of monochromatic edges. Flipping the color of a bad vertex decreases the number of monochromatic edges. Since there are $1.5n$ edges, the algorithm terminates after at most $1.5n$ steps.

In fact, the entire algorithm can be implemented in $O(n)$ time, essentially since every step only affects $O(1)$ vertices. The basic idea is to maintain a stack or queue of bad vertices.


A regular expression for strings with at most one triple of adjacent zeroes I am trying to come up with a regular expression for the following language:

  The set of all strings with at most one triple of adjacent 0s.

What does "triple of adjacent 0s" mean? Does it mean 010101, or something else?

It's hard to say for sure precisely what is meant by "triple of adjacent 0s". My best guess would be that it means the substring 000. In this case, an easy way to get a regular expression is to find an expression for strings with no such substring, and a regular expression for strings with exactly one such substring, and then take the union.

No such substring: $r = (1 + 01 + 001 )^*(\epsilon + 0 + 00)$ should do it.

Exactly one such substring: $s = (1 + 01 + 001 )^*000(1 + 10 + 100 )^*$ looks promising, but you should check it to be sure.

If my interpretation is correct, your answer would be $r + s$. In fact, and again, I may be jumping the gun here, I think that this can "simplify" (?) to something like $(1 + 01 + 001 )^*(\epsilon + 0 + 00 + 000)(1 + 10 + 100 )^*$.


Creating a DFA that only accepts number of a's that are multiples of 3 I am brand new to DFA's and my first exercise requires me to create a DFA instance such that the number of a's in the string is a multiple of 3. We only have two types of symbols: a, b. To my understanding something like "aaabbaaa" would work but "aabbb" would not. Any help or hints would be greatly appreciated

The key idea here is to make a ring of three states, $q_0, q_1, q_2$ with $a$ transitions
$$\begin{align}
q_0 & \stackrel{a}{\rightarrow}q_1\\
q_1 & \stackrel{a}{\rightarrow}q_2\\
q_2 & \stackrel{a}{\rightarrow}q_0
\end{align}$$
On input $aaa$, for example, you'll start in state $q_0$ and pass to state $q_1$ on the first $a$, $q_2$ on the second, and back to $q_0$ on the third $a$. Clearly, any multiple of three $a$s will leave you in state $q_0$, so we make that a final state.

What to do about $b$s in the input? They don't have any effect on the number of $a$s, so include transitions
$$\begin{align}
q_0 & \stackrel{b}{\rightarrow}q_0\\
q_1 & \stackrel{b}{\rightarrow}q_1\\
q_2 & \stackrel{b}{\rightarrow}q_2
\end{align}$$
and you're done. In fancier terms, we're $q_n$ to "remember" whether the number of $a$s seen so far was congruent to $n\pmod{3}$. This idiom, using the states to remember certain situations, is fundamental when designing FAs.


Updating a mst after increasing the weight of an edge in the mst Suppose we have a weighted undirected graph $G$ and a minimum spanning tree $T$
Let $G2$ be a new graph by increasing the weight of one edge $e = (a,b)$ that is part of $T$.

I'm using a common algorithm to update $T$ so we don't have to find a mst of $G_2$ from scratch. The algorithm is to first take out $e$ from $T$, which will result in two subtrees $T_a$, which contains $a$, and $T_b$ which contains $b$. Then, I iterate over all the edges in $G_2$ and find the edge with the minimum weight that has one ed in $T_a$ and the other end in $T_b$. Call this edge $e_2$. Then I add this edge into $T$ to get $T_2$.

I'm having a lot of difficulty proving that $T_2$ is a mst for $G_2$. I've proved that $T_2$ is a spanning tree of $G_2$, but again, I'm having a lot of difficulty with proving that $T_2$ is a minimum spanning tree.

Any help would be greatly appreciated!

Let $S$ be a spanning tree of an  edge-weighted graph. We call $S$ a local-minimum spanning tree (local-MST) of the graph if every edge not in $S$ weighs the heaviest in the cycle created when that edge is added to $S$.

Here is a very useful characterization of MST.

A spanning tree is an MST if and only if it is a local-MST.

Proofs of the above theorem can be found here or here.

Once we are armed with above theorem, it is easy to prove the algorithm in the question does produce an MST.

Proof of the algorithm: $G$ and $G_2$ will be referred as $(G, w_1)$ and $(G, w_2)$ respectively, where $w_1$ is the the original weight function and and $w_2$ is the updated weight function. $w_1$ and $w_2$ are the same except on $e$.

Let $G_a$ be the subgraph spanned by $T_a$ and $G_b$ be the subgraph spanned by $T_b$. Every vertex of $G$ is either in $G_a$ or in $G_b$.

Consider an arbitrary edge $f$ of $G$. Let $\mathcal C$ be the cycle created when we add $f$ to $T_2$.

If $f$ is in $G_a$ or $G_b$, then $e$ is not part of $\mathcal C$. So $\mathcal C$ is also the cycle created when we add $f$ to $T$. Since $T$ is an MST of $(G, w_1)$, $f$ weighs the heaviest in that cycle with respect to $w_1$ and, hence, with respect to $w_2$ as well.
Otherwise, $f$ connects one vertex in $G_a$ and one vertex in $G_b$. $\mathcal C$, as a cycle, must include $e_2$ since $e_2$ is the only edge in $T_2$ that connect $G_a$ and $G_b$.

In the above illustration, all green edges together with $e$ is the cycle created when $e_2$ is added to $T$.  All blue edges together with $e$ is the cycle created when $f$ is added to $T$. All green and blue edges together is $\mathcal C$.

Since $T$ is a local-MST w.r.t $w_1$, $e_2$ weighs the heaviest on the green cycle w.r.t. $w_1$. Since $w_2$ and $w_1$ agrees except on $e$,
$$w_2(e_2)\ge w_2(\text{every green edge}).$$

Similarlyly we have
$$w_2(f)\ge w_2(\text{every blue edge}).$$

Since $w_2(f)\ge w_2(e_2)$ by the specification of the algorithm, $f$ weighs the heaviest among all green edges and all green edges. That is, $f$ weighs the heaviest in $\mathcal C$ w.r.t. $w_2$.

There are configurations other than the illustration. For example, $e_2$ or $f$ might be the same as $e$. The green cycle and the blue cycle might have multiple overlapping segments. In every case, similar argument  with the same inequalities shows that $f$ weighs the heaviest in $\mathcal C$ w.r.t. $w_2$.

So we have shown that $T_2$ is a local-MST of $(G, w_2)$. By the above theorem, $T_2$ is an MST of $(G, w_2)$.


Finding maximum-cardinality independent set with a particular oracle We suppose we have a polynomial algorithm which receives a graph $G$ (any graph) and returns a stable set of $G, SA(G)$ with the following property:

$\alpha(G) − |SA(G)| \leq k$ , for every natural $k$ ($k$ is a constant)

$\alpha(G)$ is the stability number

I need to show that this algorithm can be used to find(in polynomial time) a stable set (of maximum cardinality) in a graph.

I discovered that if I give $k=0$ then we get to this relation. But does that mean that the algorithm finds the stable set with maximum cardinal.

If $k = 0$ then your algorithm outputs a stable set of maximum size. In the general case, try duplicating each vertex $k+1$ times, and see if it helps.


if $L\in BPP$ then $NP\subseteq BPP$ Let $L$ to be the following problem:
  $$L = \{ \langle M,x,1^t \rangle \mid \text{$M$ accepts $x$ after $t$ steps with probability at least $3/4$} \}.$$
  Show that if $L\in BPP$ then $NP\subseteq BPP$.

I already showed that $L$ is $BPP$-hard. I think a reduction from $3SAT$ to $L$ need to be shown (logarithmic/polynomial? not sure)

It's not clear to me how to do that - I'd be glad for guidance.

This is similar to the proof that PP contains NP. Given a 3SAT instance $\varphi$ on $n$ variables, construct a machine $M$ that with probability $3/4 - 2^{-n}/4$ accepts, and with probability $1/4 + 2^{-n}/4$ chooses a random truth assignment and accepts if the truth assignment satisfies $\varphi$. If $\varphi$ has $N$ satisfying assignments, then $M$ accepts with probability
$$
p = \frac{3}{4} - \frac{2^{-n}}{4} + \frac{M}{2^n} \left(\frac{1}{4} + \frac{2^{-n}}{4}\right).
$$
If $M = 0$ then $p < 3/4$, whereas if $M \geq 1$ then $p \geq 3/4 + 2^{-2n}/4$.

I'll let you fill in the rest of the argument.


Do lossless compression algorithms reduce entropy? According to Wikipedia:

  Shannon's entropy measures the information contained in a message as opposed to the portion of the message that is determined (or predictable). Examples of the latter include redundancy in language structure or statistical properties relating to the occurrence frequencies of letter or word pairs, triplets etc.

So entropy is a measure of the amount of information contained in a message. Entropy coders are used to losslessy compress such a message to the minimum number of bits needed to represent it (entropy). To me this looks like a perfect entropy encoder would be all that is needed to losslessy compress a message as much as possible.

Many compression algorithms however use steps before entropy coding to supposedly reduce the entropy of the message.

According to german Wikipedia

  Entropiekodierer werden häufig mit anderen Kodierern kombiniert. Dabei dienen vorgeschaltete Verfahren dazu, die Entropie der Daten zu verringern.

In english:

  Entropy coders are frequently combined with other encoders. Previous steps serve to reduce the entropy of the data.

i.e. bzip2 uses the Burrows-Wheeler-Transform followed by a Move-To-Front-Transform before applying entropy coding (Huffman coding in this case).

Do these steps really reduce the entropy of the message, which would imply reducing the amount of information contained in the message? This seems contradictory to me, since that would mean that information was lost during compression, preventing lossless decompression. Or do they merely transform the message to improve the efficiency of the entropy coding algorithm? Or does entropy not correspond directly to the amount of information in the message?

A lot of casual descriptions of entropy are confusing in this way because entropy is not quite as neat and tidy a measure as sometimes presented. In particular, the standard definition of Shannon entropy stipulates that it only applies when, as Wikipedia puts it, "information due to independent events is additive."

In other words, independent events must be statistically independent. If they aren't, then you have to find a representation of the data that defines events in ways that make them truly independent. Otherwise, you will overestimate the entropy.

To put it yet another way, Shannon entropy only applies to true probability distributions, and not to random processes in general. For concrete examples of processes that don't fit the assumptions of Shannon entropy, consider...

Markov processes

A Markov process generates a series of events in which the most recent event is sampled from a distribution that depends on one or more previous events. Obviously a huge number of real-world phenomena are better modeled as Markov processes than as discrete, independent probability distributions. For example: the text you're reading right now!

The naively calculated Shannon entropy rate of a Markov process will always be greater than or equal to the true entropy rate of the process. To get the true entropy of the process, you need to take into account the statistical dependence between events. In simple cases, the formula for that looks like this:

$$ H(\mathcal{S}) = - \sum_i p_i \sum_j  \  p_i (j) \log p_i (j) $$

This can also be represented like so:

$$ H(Y) = - \sum_{ij} \mu_i P_{ij} \log P_{ij} $$

Again quoting Wikipedia, here "$\mu_i$ is the asymptotic distribution of the chain" -- that is, the overall probability that a given event will occur over a long horizon.

This is all a complicated way of saying that even when you can calculate the overall probability of a given event, certain sequences of events are more likely than others to be generated by a Markov process. So for example, the following three strings of English words are increasingly less likely:

They ran to the tree
The tree ran to they
Tree the they to ran

But Shannon entropy will assess all three strings as equally likely. The Markov process entropy takes the difference into account, and as a result, it assigns a lower entropy rate to the process.

Entropy rates are model-dependent

If you zoom way out, here's the big picture: the entropy rate of a given sequence of events from an unknown source is model-dependent. You'll assign a different entropy rate to a particular series of events depending on how you model the process that generated them.

And very frequently, your model of the process isn't going to be quite correct. This isn't a simple or easy to solve problem. In fact, in general, it is impossible to assign a true entropy rate to a sufficiently long and complex sequence of events if you don't know what the true underlying process is. This is a central result in algorithmic information theory.

What it means in practice is that given an unknown source of sequences of events, different models will yield different entropies, and it's impossible to know which is correct in the long run -- although the one that assigns the lowest entropy is probably the best.


Dynamic programming: how to solve a problem with multiple constraints? I've got a real-world issue that I'm trying to come up with a dynamic programming algorithm to solve. It's similar in appearance to the knapsack problem, but it has more constraints, which has got me stumped. A simplified version of the problem:

Suppose I need to fill a basket with an arbitrary number of items c. The items have four properties: w, x, y, and z, each of which has a positive or negative number, with z being equal to the mean of the other three properties. My goal is to pick items such that the average z of my c items is at a maximum, but also

min(avg(w), avg(x), avg(y)) > d

for some arbitrary value d.

So, for example, c items each with w, x, and y (respectively) of (1000, 1000, -1), would have a very high average z (666.3), but would fail the second constraint if we set d >= 0, as the average y is -1.

The input would be the set of items from which to choose and the values of c and d, and the output would be a list of the c items I need to select to make the optimum full basket. Note that an item can only be selected once (no duplicates).

As I mentioned, I can see an obvious similarity to the knapsack problem, but I'm having trouble wrapping my mind around how to modify its basic structure to account for these different constraints. Or perhaps I am barking up the wrong tree trying to use the knapsack problem as a model?

Any input/pseudocode would be appreciated!

The practical solution is to formulate this as an instance of integer linear programming and apply an ILP solver.  There will be a clean formulation as ILP, and it might work pretty well.  For each item, you have an associated variable $v_i$ that is zero or one according to whether item $i$ is included in the basket or not (one means that it is included); then every one of your requirements can be expressed as a linear inequality on the $v_i$'s.

For example, the requirement that you have exactly $c$ items in the basket corresponds to the linear equality

$$v_1 + v_2 + \dots + v_n = c.$$

The requirement that min(avg(w), avg(x), avg(y)) > d is equivalent to the requirements that the sum of the $w$-fields is at least $c \times d$, and the sum of the $x$-fields is at least $c \times d$, and the sum of the $y$-fields is at least $c \times d$.  The former can be expressed as

$$w_1 \cdot v_1  + w_2 \cdot v_2 + \dots + w_n \cdot v_n > c \times d,$$

where $w_i$ is the value of the $w$-field for the $i$th possible item.  Note that $w_1,\dots,w_n,c,d$ are all constants (known from the problem statement), and $v_1,\dots,v_n$ are the variables, so this is a linear inequality.  Similarly for the sum of the $x$-fields and $y$-fields.

Finally, the goal of maximizing the average of the $z$-fields is equivalent to maximizing the sum of the $z$-fields of the selected items.  This corresponds to maximizing the following (linear) objective function:

$$z_1 \cdot v_1 + \dots + z_n \cdot v_n.$$

All of these are linear.  Finally, you can express the requirement that each $v_i$ must be either 0 or 1 by adding linear inequalities $0 \le v_i \le 1$ and requiring that $v_i$ be an integer.

The dynamic programming solution involves subproblems of the following form:

What's the maximum achievable value for the sum of $z$-fields, when restricted to choosing exactly $i$ of the first $j$ items, such that the sum of the $w$-fields is at least $\alpha$, the sum of the $x$-fields is at least $\beta$, and the sum of the $y$-fields is at least $\gamma$.

You get a subproblem for each combination of values for $i,j,\alpha,\beta,\gamma$.  That's a lot of subproblems, so the dynamic programming algorithm will probably be very slow.


About the spaces between bits Let's say I have three functions and each gives true/false answers. The first one gives 2 booleans, the second 6 and third 4. Are they written like this: 01 110010 1000? Do they get spaces between the functions? If so, do the spaces count as data? What I wanna know is, if you send an encryption key using RSA, how does RSA recognize the length of your key with the spaces? Another way to put it is if a symmetric key has 256 functions of one bit each (0 1 1 0 0 1 0, etc.) would it end up being 512 bits long because of the spaces?

I'm new in computer science and I'm learning for fun by myself. I apologize if my question is the smh type.

First of all, encoding is up to you — you get to decide the answer to the question you state.

Let's consider a more generic situation, in which you want to serialize (convert to bits) a sequence of values $x_1,\ldots,x_k$. If you know ahead of time what the length of $x_i$ is, then the most efficient encoding would be to put together all the bits of all values (no spaces!). (In practice, we also need to pack them into bytes, since data is passed around in byte chunks.)

If you don't know the length in advance, then there are several option. One option is to use some self-terminating encoding. For example, you could preface each bit by 0, and end the stream by a 1. A 2-bit string $b_0b_1$ would be encoded by $0b_00b_11$. Such an encoding is not very common. Another option is to store the length somewhere — this is quite common. For example, JPEG files store the dimension of the picture in a header. A third option is that the length, while not predetermined, is one of very few options. In that case it suffices to store just the index of the option in some header. This is probably what happens in cryptographic protocols.

Finally, there seems to be a basic misunderstanding in your question. Information is passed around in bytes. When you have a stream of bits, you pack them into chunks of 8 bits and send them in that way. There are only two options for bits — they can be either 0 or 1. What beginners sometimes do is send the bitstream as an ASCII or Unicode string, which does accept 0s, 1s, and spaces (as well as many other letters). However, this is very wasteful, spending at least 8 bits per one input bit.


Setting a cutoff for string distance filtering with different length strings I'm working to filter a table of pairwise names (1.1 M rows) based on string distance algorithms. Most are names, though some are businesses.

Edit-based algorithms seem to be best, however in attempting to set a cutoff value for match vs. non-match, there is an issue with the length of the string.  In a 16 character string, a score of 4 is usually a good match.  But of course in a 4 character string, a score of 4 is a complete non-match.

What are good options for using a string distance algorithm, but scaling the scores relative to the length of the comparison strings? This doesn't seem to be built into any of the algorithms I've found.

You can use normalized edit distance, where you divide the edit distance by the length of the larger of the two strings.  Whether this is better will depend on what you are trying to achieve.

There are many other techniques for fuzzy matching, which you might want to investigate.  The Levenshtein edit distance is only a starting point.


Optimizing coin splitting - Is this algorithm as fast as I think? In a recent exam, I've been asked to solve the following problem:

  The problem

  Two players play the following game:   Given a sequence of coin values
  $v_1,\ldots,v_n (n \vert 2)$ the players take turns in taking one coin
  from either "end" of the sequence. The value of that coin is added to
  their score.

  Player 1 always starts. What is the maximum score that Player 1 can
  reach if Player 2 plays optimally (always minimizing their potential
  score)? What is the time-complexity of your algorithm? Prove your result.

  Example:

  Given the coin sequence $1,1,3,1,1,2$ one of the best playing
  sequence for player 1 is (scores denoted as the second tuple):

  $$(\lbrack 1,1,3,1,1\rbrack,(2,0)) \rightarrow (\lbrack 1,1,3,1\rbrack,(2,1)) \rightarrow (\lbrack 1,3,1\rbrack,(3,1)) \rightarrow (\lbrack 3,1\rbrack, (3,2)) \rightarrow (\lbrack 1 \rbrack, (6,2)) \rightarrow (6,3)$$

  The best score player 1 can reach is 6.

My solution

I'm just going to roughly outline my proof here, the formal correctness is not the point of this question. I'm more interested in the correctness of my asserted upper bound of complexity.

For the following I will use tuples to denote ranges of values. $(i,j)$ specifies the value range $v_i,\ldots,v_j$.

We iteratively create a DAG $G = (V, E, \gamma)$ as follows:
Create a vertex $v$ named $(1,n)$. Create or refer to the previously created vertices $v_1, v_2, v_3$, named $(2,n-1), (3,n), (1,n-2)$ respectively.

Create the edges $e_1 = (v,v_1), \gamma(e_1) = v_1$ and $e_2 = (v,v_2), \gamma(e_2) = max\lbrace v_1, v_n \rbrace$ and $e_3 = (v,v_3), \gamma(e_3) = v_n$. Iterate through the vertices $v_{\lbrace 1,2,3\rbrace}$ using a queue or similar to repeat the process until the sequence of coins denoted by the $v$ we iterate over is empty.

The number of edges in the created graph is bounded as follows: $\lvert E \rvert \leq 3\lvert V \rvert$.
The number of vertices is denoted by the following sum: $1 + \sum_{i=0}^{\frac{n}{2}} 2i + 1 \leq n^2$

We can determine the maximum score for player 1 by "backpropagating" the edge weights through the graph, which takes $\lvert V \rvert * \lvert E \rvert$ steps.

This makes the overall algorithm asymptotically require $\Theta(n^2)$ steps

The problem I have with my answer is the upper bound for the number of vertices. I just pull that number out of thin air and my gut-feeling tells me that it is correct, but I might just be completely wrong.

Assuming that this is indeed a correct way to calculate the answer to the question, is my time-complexity argumentation sound?

You have made significant progress on this problem. Your final conclusion, "the overall algorithm asymptotically requires $\Omega(n^2)$ steps" is likely to be correct as well.

Analysis of Your Argumentation

Here are some unclear or unconventional or inconsistent notations found in your post, which makes it difficult to understand or justify your arguments about time-complexity.

Does "$n|2$" mean $n$ is even? The standard convention for for "$a$ divides $b$" is $a|b$ according to math stackexchange answers and my years of practicing number theory. So $2|n$ is the prefered notation for $n$ is even. Anyway, in current case, I strongly prefer the plain English, $n$ is even.
"use tuples to denote ranges of values. $(i,j)$ specifies the value range $v_i,\cdots,v_j$.". People use $(i,j)$ generally to mean the pair of elements $i$ and $j$ or an open interval with ends $i$ and $j$. I would suggest you use $v_{i..j}$, where the two-dot notation $i..j$ are the convention for an integer interval.
"create a DAG $G = (V, E, \gamma)$". Do you mean an edge-weighted DAG?
"Create a vertex $v$ named $(1,n)$", which does not sound like English. It is better to write "Create a vertex $v$ that represents $1..n$".
"Create or refer to the previously created vertices $v_1,v_2,v_3$, named $(2,n−1),(3,n),(1,n−2)$ respectively". Although I can probably guess your intention, I am puzzled by the notations. Did you not notice that $v_1, v_2, \cdots, v_n$ appears as the coin values in the quoted problem? It looks like you want to use "$(2,n-1)$" as a name, which would be very confusing, since I have never seen any name of a person, a item, a variable or whatever starts and ends with a parenthesis for years except for very few social online accounts.
"Create the edges $e_1=(v,v_1),\gamma(e_1)=v_1$ and $e_2=(v,v_2), \gamma(e_2)=\max\{v_1,v_n\}$ and $e3=(v,v_3),\gamma(e_3)=v_n$". Now I am more into the wanderland. Is the codomain of $\gamma$ the vertices or the indices or the coin values?
"Iterate through the vertices $v_{\lbrace 1,2,3\rbrace}$". It is better to just write $v_1, v_2, v_3$.
"the sequence of coins denoted by the $v$". Didn't you say $v$ is a vertex?

Now Let us check your computation of the time-complexity.

"The number of edges in the created graph is bounded as follows: $|E|\le3|V|$. The number of vertices is denoted by the following sum:  $1 + \sum_{i=0}^{\frac{n}{2}} 2i + 1 \leq n^2$". It looks like your estimates are correct, even though they can be tighter.
"We can determine the maximum score for player 1 by 'backpropagating' the edge weights through the graph, which takes $| V | * | E |$ steps. This makes the overall algorithm asymptotically require $\Theta(n^2)$ steps". Since it is not clear how your backpropagating works exactly, it is hard to justify the number of steps. However, since $| V |* | E | \le |V| * (3 |V|) \le 3 n^4 $, you can only say that your algorithm takes $O(n^4)$ time.

In summary, even assuming that your algorithm is indeed a correct way, there is not enough clear information to fully justify or disprove your time-complexity argumentation. There are quite some room for you to improve the description of your algorithm and the time-complexity argumentation.

A Reference Solution

For simplicity, I will assume $n$ is even. Let $f(i,j)$ be the maximal score reachable by the first player if the two players start the game with the coins sequence $v_i, v_{i+1}, \cdots, v_j$.

Then we have the base cases,
$$f(i, i+1)=\max(v_i, v_{i+1})$$
and recurrence relation
$$ f(i,j) =\max(v_i+\min(f(i+2,j),\ f(i+1,j-1)),\ v_j +
\min(f(i+1,j-1),\ f(i,j-2)))$$

The parameter pair $(i,j)$ of any $f(i,j)$ that appears in the course of computation of $f(1,n)$ will be such that $1\le i\le j\le n$ and $(i-1)+(n-j)$ must be even. The number of all such parameter pairs are $n^2/4$. The base case and the recurrence relation together shows that we need some $O(1)$ operations to obtain $f(i,j)$ for a new parameter pair $(i,j)$, assuming that the usual memorization technique in dynamic programming is used. So the time-complexity of computing $f(1,n)$ is $\Theta(n^2/4)=\Theta(n^2)$.


Succinct data structure to return occurences of letters until an index I want to try and use a succinct type data structure in order to find the amount of occurences of a letter $C$ in a string $S$ until a given index $I$.

Assume we have a string $S$ of length $n$ over the alphabet $\Sigma = \{1,2,3,\ldots,n\}$. I want to build a data structure whose space usage is at most $O(n)$ machine-size words.

Given $C$ (a valid letter from $\Sigma$) and an index $i$ such that $0 \le i \lt n$, the data structure should be able to return the number of occurrences of $C$ in $S[1..i]$ as efficiently as possible (but not necessarily in $O(1)$ time). This is the only query possible.

The data structure is aware of $S$ when created.

What I've tried to far is to split the string $S$ into blocks and to store info about each block with the number of occurrences of each letter in the  previous block. I couldn't find how to make it lighter so the memory complexity be as requested.

To put it another way, you want to implement rank queries on an arbitrary string with an arbitrary alphabet.

If $n$ is of modest size, the usual approach is to use a Wavelet tree, associating a succinct binary rank index with each node in the tree. The shape of the tree is arbitrary, but using a Huffman tree gives you a data structure that is very close to zero-order entropy compression.

When the alphabet is very large, though, the size and implementation of the tree itself becomes a concern. A way to fix this which seems to work well in practice is to store $\left\lceil \log_2 n \right\rceil$ rank-select indexes of length $|S|$, but use an index implementation that it sensitive to local variation in density, such as esp or RRR.

This is covered in Claude & Navarro's 2008 paper, Practical Rank/Select Queries over Arbitrary Sequences. There may be some more recent work than this if you chase citations, but that's a good start.


How to prove $\{a^nb^na^n \mid n\geq1\}$ is not regular using pumping Lemma Here the problem is that I’m confused how to take the pumping value $p$ is it arbitrary any value?
Also I don’t know if I should prove all $3$ conditions of the pumping lemma is false or if any one should be proved as false by considering the given language as regular by proof by contradiction.

Let's recall the Pumping Lemma statement:

For all regular language $ L $, exists a positive constant called $ p $ (i.e. $ p \geq 1 $) such that every string $ w $ in $ L $ with length $ |w| \geq p $ exist strings $ x, y, z $ such that $ w = xyz $ and that statisfying the following conditions:

$ |y| \geq 1 $
$ |xy| \leq p $
$ xy^iz \in L, \: \forall i \geq 0 $

So yes, $ p $ is an arbitrary value and a fixed costant, called "pumping length". The proof for your language may be the following:
Let's assume that $ L $ is a regular language, so for all strings $ w \in L $ it must satisfy conditions of PL.
Now choose a string $ w $ that is in $ L $, let choose $ w = a^pb^pa^p $ and we can split $ w $ in $ xyz $, so let's say that:

$ x = a^k $
$ y = a^h $
$ z = a^{p-h-k}b^pa^p $

with $ h \geq 1 $ and $ h + k \leq p $.
Now note that the first two conditions of the PL are satisfied, but for the third, if we take $ i = 0 $ then $ w = xy^0z = a^ka^{p-h-k}b^pa^p = a^{p-h}b^pa^p $ and this string clearly doesn't belongs to $ L $ and this contraddict the initial assumption of $ L $ regular, so this meanings that $ L $ isn't a regular language because it doesn't satisfy the PL.


Does XML covers the representation of any structured data and knowledge I see nowadays XML is used to structure any file or data. It can represent both flat and hierarchical relationships. For example, it can be used to show the parse tree of a sentence in a natural language.

I am not familiar with different types of data and knowledge structures, but I would like to know if XML is theoretically the ultimate representation scheme which can model and structure any data and knowledge?

What are the reasons behind the popularity of XML?

XML is nothing more than a well-defined way to store trees of strings. Since even plain strings can encode everything you can encode in practice (i.e. countable sets), yes, XML can "model" everything.

But that's nothing special.

The popularity of XML is probably due to

it being standardized and
the amount of tool support that has developed.

There is no information-theoretic miracle involved.


What is the upper and lower bound for $T(n) = T(\sqrt{n}) +3$, assuming that $T(n)$ is a constant for $n\leq 10$ By unrolling the recursion,
\begin{equation*}
\begin{split}
    T(n) &= T(\sqrt{n}) + 3 = T(n^{\frac{1}{2}}) + 3 \\
    &= (T(n^{\frac{1}{4}})+3) +3 = T(n^{\frac{1}{4}}) +6  \\
    &= (T(n^{\frac{1}{8}})+3) + 6 = T(n^{\frac{1}{8}}) +9 \\
\end{split}
\end{equation*}
Claim: $T(n) = T(n^{\frac{1}{2^k}}) + 3 \cdot k$
Base Case: $k=1$
\begin{equation*}
\begin{split}
    T(n) &= T(n^{\frac{1}{2^1}}) + 3 \cdot 1 \\
    T(n) &= T(\sqrt{n}) + 3
\end{split}
\end{equation*}
Inductive Hypothesis: Assume that k=i is true,
\begin{equation*}
\begin{split}
    T(n) &= T(n^{\frac{1}{2^i}}) + 3 \cdot i \\
    &= (T(n^{\frac{1}{2^i+1}}+3) + 3 \cdot i \\
    &= (T(n^{\frac{1}{2^i+1}}) + 3 \cdot (i +1) \\
\end{split}
\end{equation*}
These are my questions...

I am unsure if my base case is correct
I am also not sure how to proceed (what value can I substitute in to get a closed form)

Any help would be appreciated!

Where are you using that T(n) = c for n <= 10? Your formula is wrong when the argument is less than 10. K = 1 is not the base case. N <= 10 is the base case.
Clearly T(n) = c for n <= 10, T(n) = c+3 if 10 < n <= 100, T(n) = c+6 if 100 < n <= 10,000, T(n) = c+9 if 10,000 < n <= 100,000,000 etc.
Let f(n) = log_10 (max (n, 10)) so for the four cases above we have f(n) = 1, 1 < f(n) <= 2, 2 < f(n) <= 4, 4 < f(n) <= 8 etc.
Let g(n) = ceil(log_2(f(n))), then g(n) = 0, 1, 2, 3 etc, and T(n) = c + 3 g(n).


How to solve this asymptotic complexity problem? The increasing order of following functions in terms of asymptotic complexity is:

(A) f1(n) < f4(n) < f2(n) < f3(n)

(B) f1(n) < f2(n) < f3(n) < f4(n)

(C) f2(n) < f1(n) < f4(n) < f3(n)

(D) f1(n) < f2(n) < f4(n) < f3(n)

I saw this question on GeeksQuiz but I am unable to understand its answer. The correct answer is D.

I think that f(2) will have the highest complexity among all because for a given number it will give the maximum output.

Please help and explain how is it solved?

$f_3(n)$ has the highest asymptotic time since it is an exponential function. Although it is $(1+\epsilon)^n$ and might seem very tiny in terms of growth, there exists a real number $m$ where it grows faster than the rest.

Then, we have $f_4(n)$ as quadratic function.

$f_2(n)$ is unfortunately linear. Which means, it does not grow as fast as $f_4(n)$ and $f_2(n)$. Actually, while considering asymptotic growing, you should ignore the constants in the function. Thus, we can say that $O(1000000n) = O(n)$.

The tricky part is $f_1(n)$. It would grow faster than $f_2(n)$ if it was $O(n \log n)$. However, it is $O(n^{1-\epsilon} \log n)$, which makes it grow slower than a linear function.


Assignment algorithm for symmetric matrices I stumbled on the Hungarian algorithm during my personal research when I was assigned interesting problem as homework:

Given a list of objects $L$ and a pairing function $\delta : L \times L \rightarrow \left[0, 1\right]$, pair each object $\alpha$ in $L$ with exactly one $\beta$ in $L$ such that:

$\sum_{i = 1}^n \delta(\alpha_n, \beta_n)$ is maximal
$(\alpha, \beta) \iff (\beta, \alpha)$
$(\alpha, \beta) \implies \alpha \neq \beta$

Now, since we just started programming as a class, our TA wants us to use a heuristic approach to solve the problem - e.g. swap assignments until you reach a local maximum etc.

I thought of using the Hungarian algorithm to guarantee an optimal matching in (relatively) feasible time. For this, I constructed a graph with all $\alpha$ having nodes to all $\beta$ and initializing the edge of two same elements to $\infty$.

However, as it turns out, the implementation I wrote disregards the symmetric aspect of this matrix - in other words my algorithm does not guarantee that $\alpha$ is also it's the partner of the partner of $\alpha$.

I suspect that reason for this is that this is not a bipartite graph anymore. Even though there is a difference between an $\alpha$ on the left and a $\beta$ on the right, it's not a "real" bipartite graph. Is this correct?

According to the Math stack exchange I should use the more general blossom algorithm in this case, but somehow I have a feeling that I could make better use of the properties of my matrix. Is there a better algorithm for this case?

Your problem is exactly the same as maximum weight perfect matching, solved by the blossom algorithm. Although $\delta$ is not given as symmetric, you can reduce your problem to the symmetric case by replacing $\delta$ with
$$ \delta'(\alpha,\beta) = \max(\delta(\alpha,\beta),\delta(\beta,\alpha)). $$
I'll let you figure out how to translate a solution which is optimal with respect to $\delta'$ to one which is optimal with respect to $\delta$.


Can two equal classes be separated wrt an oracle? Is it known if there are two classes of languages $A$ and $B$ such that:

$A$ and $B$ are defined wrt the exact same type of machine (e.g. 1-tape Deterministic Turing Machines, 2-tape Deterministic Turing Machines, 1-tape Nondeterministic Turing Machines, etc);
neither $A$ or $B$ are defined wrt a restriction on space usage;
$A = B$;
there is an oracle $O$ for which $A^O \neq B^O$?

While the other answer answers the question as posed (at least, given your definition of 'type of machine'), I still think the question is rather ill-posed and that resolving this is a solution as well.

Problems with the current definition

First of all, as @D.W. mentioned in the comments, the claim 'Language class $X$ is defined w.r.t. machine $M$' is ill-posed. There is no need to define a class of languages with a machine at all. Even if we have a language which is commonly described w.r.t. some machine, such as $P$, there is nothing preventing us to give an equivalent definition that uses no machine at all! (Not sure if this is doable or has been done. Perhaps you can do something based on $\lambda$-calculus?)

The second problem is that oracle access is not a modifier/property of a language class! This follows immediately from the previous point: if I define a language without using a machine, how on earth am I able to use this oracle if I don't even have a machine?

The crucial mistake that leads to your problem is that a 'language' under oracle access actually depends on the definition of the language and a 'language' with oracle access is not invariant under the method you use to define the language. In fact, the often posed statement $P^O = NP^O$ is an example of really bad notation, as $P$ and $NP$ aren't actually languages here, but methods to define languages!

Let's make this precise: Let $\mathcal{X}$ be a 'definition method' for languages that can access oracles (for example, a set of machines and some acceptance rules) Let $L(\mathcal{X})$ be the language class that is defined by $\mathcal{X}$. Let $\mathcal{X}^O$ be the extension of $\mathcal{X}$ with access to the oracle $O$.

Rephrasing the question

Your question can now be rephrased as follows, let language classes $A$, $B$ such that:

  There exists an $\mathcal{X},\mathcal{Y}$ such that $A= L(\mathcal{X})$, $B = L(\mathcal{Y})$ and $\mathcal{X}$ and $\mathcal{Y}$ are 'of the same type'.
  $\mathcal{X}$ and $\mathcal{Y}$ are able to use unbounded space.
  $A=B$
  There exists an oracle $O$ such that $L(\mathcal{X}^O) \neq L(\mathcal{Y}^O)$

By combining 3 and 1, we can do without $A$, $B$ and focus on the machines:

  $\mathcal{X}$ and $\mathcal{Y}$ are 'of the same type' and are able to use unbounded space.
  There exists an oracle $O$ such that $L(\mathcal{X}^O) \neq L(\mathcal{Y}^O)$

Now, the question crucially depends on what 'the same type' means. If $\mathcal{X} = \mathcal{Y}$, then satisfying both 1 and 2 becomes impossible, as  we now do have $\mathcal{X}^O = \mathcal{Y}^O$, so $L(\mathcal{X}^O) = L(\mathcal{Y}^O)$.

So, a necessary condition for statements 1 and 2 is the claim:

  There exists an oracle $O$ such that $\mathcal{X}^O \neq \mathcal{Y}^O$.

You can define 'type' however you wish, but if two machines don't behave the same when I give them the same oracle, I don't consider those machines to be of the same type.

So, in conclusion, after rephrasing your question more formally and giving a property which I believe 'type' should adhere to, the answer to your question is actually no.


Question related to vertex cover The definition of vertex cover is as is:
Set of vertices such that each each has atleast one endpoint in that set.

In the above example, why can't we consider all vertices as vertex cover since all vertices are endpoints to all the edges.

Your misunderstanding might be a false assumption that there is a unique vertex cover. This is hardly the case – there could be many different ones.

The set of all vertices always forms a vertex cover. However, there are always smaller vertex covers (even in the complete graph!), and we are usually interested in finding a vertex cover which is as small in size as possible.


Detecting Hamiltonian path in a graph There are various methods to detect hamiltonian path in a graph.

Brute force approach. i.e. considering all permutations T(n)=O(n*n!)
Backtracking T(n)=O(n!)
Using Dynamic programming T(n)=O(2^n * n^2)

Now, there is one another method using topological sort. Topological sort has an
interesting property: that if all pairs of consecutive vertices in the sorted order are connected by
edges, then these edges form a directed Hamiltonian path in the DAG. If a Hamiltonian path
exists, the topological sort order is unique. Also, if a topological sort does not form a
Hamiltonian path, the DAG will have two or more topological orderings.

Approximation Algorithm: Compute a topological sort and check if there is an edge between each
consecutive pair of vertices in the topological order.

I have a doubt that why is it considered as an approximate algorithm? Wouldn't it give correct output every time? What are the cases when it won't give correct output?

Hamiltonian Path in a DAG is easy to solve: You can find the longest path in $O(|V|+|E|)$ time using the critical path algorithm: https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths.  For unweighted DAGs, this sounds like essentially the same thing as your topological sort.

Hamiltonian Path is NP-hard on digraphs with cycles, and on undirected graphs.


Proving if a function is an upper bound Let $f(n) = (\log n)^n$
   and   $g(n) = n^2$

By taking a large value, I could make out that $f(n) > g(n)$ .

I want to know if $f(n) \in \Theta(n^2)$ . For proving this, I need to find out the value of $c$ such that
$f(n) \le c \cdot g(n)$ .

How do I find the value of $c$ ? By seeing the function it seems like no $c$ exists. But I am not able to prove or disprove it.

Please help.

Just looking at the plot we can easily see, that these two complexities are completely different.

To prove it, we have to show that there doesn't exist a $c \in \mathbb{R}$ such that

$$(\log n)^n \le c \cdot n^2$$

We can take the $\log$
$$n\cdot \log\log n \le \log c + 2\log n$$
Because $3 \le \log\log n$ and $\log n \le n$ for big $n$, also the following inequalities have to hold:

$$3n \le n\cdot \log\log n \le \log c + 2\log n \le \log c + 2n$$

And therefore also the following inequaltiy has to hold:

$$3n \le \log c + 2n$$

This implies $n \le \log c$ or $e^n \le c$. And there is no $c \in \mathbb{R}^+$ with $c \ge e^n$ for all $n$

The proof is probably way too complicated, but it was the first thing that came to my mind.


Graphs: Dectect a sink in $\mathcal{O}(V)$ Given a directed conected graph which representation is its adjacency matrix $A$, design an algorithm to detect a sink in $\mathcal{O}(V)$ time, being $V$ the number of vertices.

As definitions can vary, in this context, a sink is defined as a vertex with $0$ exit degree and $V-1$ enter degree.

Obviously, the problem is reduced to find a $j\in\{1,\dots,V\}$ such as $a_{ji}=0$ for all $i$ and $a_{ij}=1$ for all $i\not=j$, thats what I tried. However, this solution is in $\mathcal{O}(V^2)$.

Any idea?

Assumption  :There is at most one row which contains all zero's.
You want to find a row of the adjacency matrix $A$ whose all entries are zero's. Simple observation if say the desired row is $k$th than in the $k$th column of adjacency matrix $A$ will contain all ones except the [k,k] index (it is easy to verify ). Let $n$ is the number of rows and columns in the matrix $A$.

Algorithm :

Start from the top right corner of the matrix $A$.
If $a_{i,j} = 0$ and $i \neq j$ then it's not your required column, skip this column mean move to $ j-1 $th column (see you have skipped one column in this step, so the number of columns for your search has been reduced).
if $a_{i,j} = 1$ and $i \neq j$ then it is your required column, but it is not required row (think why ? ) so change the row move to $ i+1 $th keep the column same.

Running time. : In each step you either reducing the number of rows or number of columns, so maximum number of steps is going to be at max $2n$ (number of rows + number of columns ).


compiler interaction with OS I want know if compiler interacts with operating system during compilation process.And if yes then which part of compiler interacts with which part of operating system

Compilation is only a process of converting your code to assembly language. To achieve this task there is no need to interact with OS kernel.

If you also mean linking, interaction with OS is again not a requirement. However, if certain optimizations, or naming conventions and versions are involved, linking might access operating system information. Still, again no code is executed in the kernel level.


Is Category Theory useful for learning functional programming? I'm learning Haskell and I'm fascinated by the language. However I have no serious math or CS background. But I am an experienced software programmer.

I want to learn category theory so I can become better at Haskell.

Which topics in category theory should I learn to provide a good basis for understanding Haskell?

In a previous answer in the Theoretical Computer Science site, I said that category theory is the "foundation" for type theory.  Here, I would like to say something stronger.  Category theory is type theory.  Conversely, type theory is category theory.  Let me expand on these points.

Category theory is type theory

In any typed formal language, and even in normal mathematics using informal notation, we end up declaring functions with types $f : A \to B$.  Implicit in writing that is the idea that $A$ and $B$ are some things called "types" and $f$ is a "function" from one type to another.  Category theory is the algebraic theory of such "types" and "functions".  (Officially, category theory calls them "objects" and "morphisms" so as to avoid treading on the set-theoretic toes of the traditionalists, but increasingly I see category theorists throwing such caution to the wind and using the more intuitive terms: "type" and "function".  But, be prepared for protests from the traditionalists when you do so.)

We have all been brought up on set theory from high school onwards.  So, we are used to thinking of types such as $A$ and $B$ as sets, and functions such as $f$ as set-theoretic mappings.  If you never thought of them that way, you are in good shape.  You have escaped set-theoretic brain-washing.  Category theory says that there are many kinds of types and many kinds of functions.  So, the idea of types as sets is limiting.  Instead, category theory axiomatizes types and functions in an algebraic way.  Basically, that is what category theory is.  A theory of types and functions.  It does get quite sophisticated, involving high levels of abstraction.  But, if you can learn it, you will acquire a deep understanding of types and functions.

Type theory is category theory

By "type theory," I mean any kind of typed formal language, based on rigid rules of term-formation which make sure that everything type checks.  It turns out that, whenever we work in such a language, we are working in a category-theoretic structure.  Even if we use set-theoretic notations and think set-theoretically, still we end up writing stuff that makes sense categorically.  That is an amazing fact.

Historically, Dana Scott may have been the first to realize this.  He worked on producing semantic models of programming languages based on typed (and untyped) lambda calculus.  The traditional set-theoretic models were inadequate for this purpose, because programming languages involve unrestricted recursion which set theory lacks.  Scott invented a series of semantic models that captured programming phenomena, and came to the realization that typed lambda calculus exactly represented a class of categories called cartesian closed categories.  There are plenty of cartesian closed categories that are not "set-theoretic".  But typed lambda calculus applies to all of them equally.  Scott wrote a nice essay called "Relating theories of lambda calculus" explaining what is going on, parts of which seem to be available on the web.  The original article was published in a volume called "To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism", Academic Press, 1980.  Berry and Curien came to the same realization, probably independently.  They defined a categorical abstract machine (CAM) to use these ideas in implementing functional languages, and the language they implemented was called "CAML" which is the underlying framework of Microsoft's F#.

Standard type constructors like $\times$, $\to$, $List$ etc. are functors.  That means that they not only map types to types, but also functions between types to functions between types.  Polymorphic functions preserve all such functions resulting from functor actions.  Category theory was invented in 1950's by Eilenberg and MacLane precisely to formalize the concept of polymorphic functions.  They called them "natural transformations", "natural" because they are the only ones that you can write in a type-correct way using type variables.  So, one might say that category theory was invented precisely to formalize polymorphic programming languages, even before programming languages came into being!

A set-theoretic traditionalist has no knowledge of the functors and natural transformations that are going on under the surface when he uses set-theoretic notations.  But, as long as he is using the type system faithfully, he is really doing categorical constructions without being aware of them.

All said and done, category theory is the quintessential mathematical theory of types and functions.  So, all programmers can benefit from learning a bit of category theory, especially functional programmers.  Unfortunately, there do not seem to be any text books on category theory targeted at programmers specifically.  The "category theory for computer science" books are typically targeted at theoretical computer science students/researchers.  The book by Benjamin Pierce, Basic category theory for computer scientists is perhaps the most readable of them.

However, there are plenty of resources on the web, which are targeted at programmers.  The Haskellwiki page can be a good starting point.  At the Midlands Graduate School, we have lectures on category theory (among others).  Graham Hutton's course was pegged as a "beginner" course, and mine was pegged as an "advanced" course.  But both of them cover essentially the same content, going to different depths.  University of Chalmers has a nice resource page on books and lecture notes from around the world.    The enthusiastic blog site of "sigfpe" also provides a lot of good intuitions from a programmer's point of view.

The basic topics you would want to learn are:

definition of categories, and some examples of categories
functors, and examples of them
natural transformations, and examples of them
definitions of products, coproducts and exponents (function spaces), initial and terminal objects.
adjunctions
monads, algebras and Kleisli categories

My own lecture notes in the Midlands Graduate School covers all these topics except for the last one (monads).  There are plenty of other resources available for monads these days.  So that is not a big loss.

The more mathematics you know, the easier it would be to learn category theory.  Because category theory is a general theory of mathematical structures, it is helpful to know some examples to appreciate what the definitions mean.  (When I learnt category theory, I had to make up my own examples using my knowledge of programming language semantics, because the standard text books only had mathematical examples, which I didn't know anything about.)  Then came the brilliant book by Lambek and Scott called "Introduction to categorical logic" which related category theory to type systems (what they call "logic").  It is now possible to understand category theory just by relating it to type systems even without knowing a lot of examples.  A lot of the resources I mentioned above use this approach to explain category theory.


what is the name for the space between the leaves of a tree I am trying to write a data-type not for a tree, but for the spaces in between the leaves of thee tree.  In number theory (a part of math) this is known as a topograph does it have a name in CS?

The empty space is called "OTIOSE".   Pronounced "oh-she-ohs"

otiosity

Synonyms & Antonyms for otiose
Synonyms
abortive, barren, bootless, empty, fruitless, futile, ineffective, ineffectual, inefficacious, profitless, unavailing, unproductive, unprofitable, unsuccessful, useless, vain


Showing a problem is NP complete? Reducing CLIQUE to KITE. I've got an exam next week all about this sort of thing. Ie: Find polynomial certifier for a problem, give a polynomial reduction, prove problem X reduces to Y and etc.

The problem is, there doesn't seem to be anyone available in my department to help me until after the test. I really struggle to understand it and get confused all too often when looking at it. So I was wondering if my wonderful chums of the internet could work through a problem with me! (Problem is below if you wanna skip my waffle) I apologise if there is an awful lot of it, I hope this will be useful for me or future lurkers though. Feel free to only answer part of it.

I get that $X \leq_p Y$ means that given an oracle for Y, we can solve X using a polynomial number of standard computational operations plus a polynomial number of calls to that oracle for Y.
I also get that to show a problem Y is NP complete we show:

  There exists a polynomial time certifier for problem Y.

  We give a reduction $X \leq_p Y$ from a known NP problem X. Ie: Showing that X is no harder than Y.

But in practise, I really struggle to do both of these things. It all seems a bit hand wavy at times and the slides used by my course don't really help me, they seem to be used all over the place, here's a copy: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/08IntractabilityI.pdf

So, I thought we'd look at a problem that was included on an earlier test for my own module.

Given that CLIQUE is NP-complete, show that KITE is NP-complete

The CLIQUE decision problem is given a graph G and integer k; decide whether there is an induced complete subgraph of size k. The KITE decision problem is to decide whether there is a kite subgraph of size 2k, which consists of a clique of size k with a k-size tail.

Creating the certifier

So, how exactly should I write a certifier for KITE? I don't really understand what my certificates should be to be honest. I assume I want an input graph $G=(V,E)$ and then maybe a graph $H=(V',E')$ with an integer $k$ such that $H$ is a kite of $2k$. And then check if G contains H as an induced subgraph? But that seems way too easy considering it was worth 20% of the example paper.

algo kiteCertifier(Graph G, Graph H, int k) {
  for each v in V'
    if v not in V
      return no

   for each (u,v) in E'
      if (u,v) not in E
          return no

   return yes
}

I suppose what really confuses me is that I don't get how to pick a certificate for problems, perhaps I don't really get what a certificate is or what a certifier should actually be doing.

Showing $CLIQUE \leq_p KITE$

This is where I often get confused I think. I've seen different reduction examples showing an implication in one direction, then the other, and many just show iff.

Again, it can't just be as simple as saying every kite has a clique in it can it? That's almost axiomic! I wondered if perhaps I should show a graph contains a clique iff it contains a kite.

Given a clique C of size $2k$ or $2k+1$ (i.e.: odd or even clique) we show there always exists a kite of size $2k$ within it.
Consider any k nodes $\{v_1,v_2,...,v_k\}$ in the clique. These nodes also form a clique because every node v in the clique is connected to every other node w by an edge. Now consider the nodes $\{v_{k+1},v_{k+2},...,v_{2k}\}$. Each node $v_j$ in this set is connected by an edge to $v_{j+1}$ since C is a clique. We also have that $v_k$ is connected to $v_{k+1}$ and so we now have a kite of size 2k.

Now suppose we have a kite of size 2k, by definition, it contains a clique of size k.

But again, I really don't feel confident enough on this, am I even doing anything vaguely correct? :p Any help would be greatly appreciated.

Thanks very much!

With regards to the reduction, you need to show that given an oracle for Kite, you can solve Clique in polynomial time. It doesn't really help that every Kite has a Clique in it: we're interested in solving Clique, but a graph that has a Clique doesn't necessarily have a Kite (if it has a Kite, then it certainly has a Clique - but that's not enough). You need to modify the graph so that if(f) it has a Clique, then it also has a Kite and pass that modified graph as an input to the oracle.

We don't ordinarily believe that an NP-complete problem can be solved in polynomial time. The point of a verifier/certifiate is that with help, we can solve it in polynomial time. The certificate is the "help", and you can define the certificate to be almost anything you like. For instance, for Clique, we can ask that the certificate be a list of the vertices that make up the Clique. Verifying then becomes easy: we can check we've indeed been given $k$ vertices, and that there are edges between all of these vertices. If you like, you can think of the certificate as a solution to the problem, and the verifier's job is to check that the solution is correct.


How is parallel tag checking achieved in associative Mapping? I originally posted this question on stack overflow and then realised it was better suited to computer science .

In the book on computer organization and architecture by William stallings , in the cache memory chapter and associative mapping topic , the author says that the cache control logic simultaneously checks all the tag fields for a match when presented with an address .
However , there is nothing said about how this actually happens , how the simultaneous checking takes place and I wanted to know about how this is implemented and what kind of circuitry is required to achieve this.

[I don't have this book]

Let's take a common example : A 4 ways, 16kB cache made of 4 ways of 4kB.
And a cache line of 32 bytes.

Each way of the cache is made of a 4kB RAM containing data and another RAM which stores cache tags, its size is 4096/32 = 128 lines, each tag can probably fit in a 32 bits.

The tag RAM is indexed with the low address bits (here A[12:6]), and its content is compared with the high address bits A[31:7].

If you have 4 ways, you have 4 tag RAMs, the address bits are the same, but you have 4 comparators.

Cache is made of ordinary RAM blocks.

(In current advanced CPUs, to save power and complexity, the cache ways are often not compared at the same time, there is a preferred way, selected with some heuristics, wich is tested first, the other ways are tested only if the first one do not match)


Why does a Turing machine recognise exactly one language? I am trying to understand the existence of non-recognisable languages. To get this, I need to know why a Turing machine recognises only one language, not multiple. Why is this?

The language recognized by a Turing machine is, by definition, the set of strings it accepts. When an input is given to the machine, it is either accepted or not. Any particular input to that machine is either always accepted (in the language) or always not accepted (not in the language). So there's no mechanism by which a single Turing machine even could accept more than one langauge.


Reducing a non-RE language to its complement Is there a language $L$ such that both $L$ and $L$'s complement are non turing recognizable languages, but there is a reduction between them?
I couldn't find one...

Such a undecidable language $L$ can not be in $RE$, since if there was a computable reduction from $L$ to $\overline{L}$, then $L$ would be in $R$.

Let $x'$ be the value to which $x$ reduces. $x' \in L$ if and only if $x\not \in L$. We could then decide $x\in L$ by enumerating $L$, and stopping to report that $x\in L$ as soon as we encounter $x$, and report that $x\not \in L$ when we encounter $x'$. That would make $L$ decidable, which is a contradiction. So there can be no reduction from a language in $RE$ to its complement.

By a similar argument, such a language can not be in $co-RE$ either.

There does exist an undecidable language $L$ that can be reduced to its complement. To find one, we must consider a language that is neither in $RE$ nor in $co-RE$. Let $L\in RE$ be an undecidable language. Then

$L'=\{0w|w\in L\} \cup \{1w|w\in \overline{L}\}$

is not recursive enumerable nor is its complement (see here).

But there clearly is a reduction from $L'$ to $\overline{L'}$.


Can there exist more than one optimal solution in a dynamic programming problem? In any dynamic programming problem can there exist more than one optimal state ?

If so how would I enumerate all of them ?

For example: in the subset sum problem for the given set $\{-3, -2, 7, 5\}$ and target sum $0$.

There exists two ways of reaching $0$. ie. $\{\}$ = empty set as a sum of zero, or $\{-3, -2, 5\}$ = also which has a sum of $0$.

In dynamic programming how would you distinguish between these two ?

Yes, but it's implicit in the dynamic programming table.

The dynamic programming table starts by filling out objective values for trivial sub-solutions, then combining them to obtain the optimum objective value by the time the final entry is reached. The central part to emphasise here is that the dynamic programming table has objective values as its entries, rather than the sub-solutions themselves (although you may hang on to all sorts of information to help the computation of course). So the way you obtain the actual solution from a dynamic programming table is to trace back from the final entry reconstructing the steps taken to get there.

Then if there's multiple ways to get there, in the tracing you just run into situations where you can go more than one way. If you were only interested in obtaining some solution, you just pick a route. If you want all of them, you exhaustively explored all routes back through the table.