Cont: NP-hard or not: partition with irrational input or parameter Please take a look at NP-hard or not: partition with irrational input or parameter first.

In  Will irrational parameters make a problem not well-defined on complexity, I got an answer of "No". Then I checked that some well-defined problems  indeed have irrational paprameters(e.g., In the sum of square root problem, it has square roots).

Now I want to use this "property" (irrational parameters donot make a problem ill-defined on complexity) to modify method 1 such that determining the complexity of original problem is well-defined in some cases and it is NP-complete.

More concretely, suppose that $x_*$ in  method 1 is actually $0.52+\sqrt{2}\times 10^{-10}$.  Then we ask such a problem:

  Given a set $N=\{a_1,...,a_{n+2}\}$ with $n+2$ numbers where

  $a_1,...,a_{n+2}$ are positive and rational,

  find a set $S\subseteq N$, such that $f(S)=0.52+\sqrt{2}\times 10^{-10}$, where
  $f(S)=\sum_{i=1}^n a_i \textbf{I}_{i \in S} + (0.51+\sqrt{a_{n+1}}\times 10^{-10})\textbf{I}_{n+1 \in S}+  (0.47-\sqrt{a_{n+2}}\times 10^{-10})\textbf{I}_{n+2 \in S}$ and $\textbf{I}$ is an indicator function.

Then for such a problem, we can argue that it is NP-complete, since there is one instance  with rational inputs satisfying

  $\sum_{i=1}^n a_i = 0.02$ and $a_{n+1}=a_{n+2}=2$.

Is this correct?

Without answering your specific question, let me comment on a basic matter that I see appearing in several of your questions.   Trying to reason about this as "irrational parameters do or don't make the problem ill-defined" seems likely to be confusing.

Instead, back up and understand the fundamentals.  The fundamentals are that we need to specify a problem precisely before we can ask for its running time.  How do we specify a problem?  The most fundamental way is as a decision problem, and a decision problem is a formal language: a subset of $\{0,1\}^*$.  Thus, the problem is: given a string $x \in \{0,1\}^*$, answer whether it is in the language $L$.  More generally, if you want to discuss algorithms for problems that produce multiple bits of output, a problem specifies a function $f:\{0,1\}^* \to \{0,1\}^*$.  In other words, given any bit-string that is the input, the function $f$ tells us a bit-string that is the desired output.

So, to specify a problem carefully, you specify that mapping $f$.  Usually, this is done by specifying the input and how it is represented as a binary string (as a convenience, this latter step is often omitted if it is obvious how to do it, but it's exactly this step that is tripping you up, so for you, do not omit it), and by specifying the correct output (as a function of the input) and how it is represented as a binary string (again, you better not omit this).

When you start talking about irrational numbers, you are going to run into the problem that irrational numbers cannot be represented as a binary string.  There is no encoding of numbers that enables you to encode all possible irrational numbers and that ensures that all encodings are finite.  Thus, if your problem statement says "the input is an irrational number...", you are going to have a problem.

Then, to prove that a question is NP-complete, you construct a reduction.  So, go do that.  Don't try to prove it with one line ("there is one instance with rational inputs satisfying..") constructed in an ad-hoc way -- instead, explicitly construct the reduction.  If you understand the concepts, you should be able to tell whether your reduction is correct or not, without needing to ask us.

Before asking another in this line of questions, I suggest that you study basic material on P, NP, reductions, and complexity classes.  Make sure you understand it at the basic level, before trying to apply it to your specific problem.  Textbooks are written to make it easier to understand these concepts in the context of some simpler problems, and that will make it easier to pick up than to try to both learn the concepts and apply it to your harder problem at the same time.


Efficiently finding the intersections of sets that yield a desired set Given a collection of sets $\{S_1, S_2, \dots, S_n\}$, find all the "reduced" intersections between those sets that yield the desired set $\{x\}$ as the result. A "reduced" intersection is defined as an intersection between sets where $S_i\cap S_j\cap \dots \cap S_k = \{x\}$, such that removing any one of the sets in the intersection changes the result from the desired set $\{x\}$ to something else.

For example, for the collection of sets $\{A,B,C,D,E,F\}$, where:

$A = \{c,d,f,g,x\}$,

$B = \{c,d,g,p,t,x\}$,

$C = \{e,i,x,y\}$,

$D = \{a,i,o,p,q,w,x\}$,

$E = \{f,t,w,x\}$, and

$F = \{a,b,c,d,e\}$, then:

$A \cap B \cap E = \{x\}$ is a reduced intersection, because $A\cap B
   = \{c,d,g,x\}$, $A\cap E = \{f,x\}$, and $B\cap E = \{t,x\}$. Removing any of the sets $A$, $B$, or $E$ from the intersection $A
   \cap B \cap E$ yields a different result than the desired set $\{x\}$.
$C \cap D \cap E = \{x\}$ is NOT a reduced intersection, because
$C\cap E = \{x\}$. Removing set $D$ from the intersection $C \cap D
   \cap E$ still yields the desired set $\{x\}$ as the result.

My question is: given a collection of sets, what is the most efficient algorithm to find all the reduced intersections between those sets that yield a desired set?

Note that it doesn't matter whether the desired set has only a single element in it or not. In this example, I just used a single element $x$ for simplicity.

Your problem is equivalent to enumerating all inclusion-minimal set covers, a problem addressed here.

Suppose that you're looking for all collections of sets whose intersection is some set $T$. All the relevant sets must contain $T$, so you can just consider all sets containing $T$, and remove $T$ from all of them. This reduces to the case $T = \emptyset$.

Now let $U$ be the union of all sets. The intersection of a collection of sets is empty iff the union of their complements is $U$. In other words, if you complement all sets, then you're interested in inclusion-minimal set covers.


Why are there multiple computer languages instead of multiple libraries? If someone realizes that a computer language is deficient under some aspect or the other, couldn't he just create a library for the new language instead of a new language?

Couldn't you have a library In C that lets you process list as if they were lisp? Or that write simple code as if it was Python?

Why does evolution have to mean breaking with the past?

There are many features that cannot be simulated by a library (or rather - are very hard to simulate by a library), for example garbage collection, or exception handling. And even features which can, say object-oriented programming, are much easier to use when they're part of the core language.

You can certainly have a library in C implementing an interactive python interpreter, and then you can just put python code in quotes as input. There are several problems with this: it will be hard to debug, and syntax highlighting could be a nightmare. However, the real issue here is that if you've gone that far, you actually have a python interpreter.

Simulating python in any other way seems difficult: how would you implement control structures, for example? How would you implement message passing, operator overloading and so on? You will need to replace the usual operators by named functions like add and so on, which aren't going to be very easy to use. And to implement message passing you will need to use variadic functions with string parameters, taking care to handle somehow named parameters. You will do all that, and still lack the interactive python interpreter.

You can say the same regarding any other language - even if you could simulate language features, it would be awkward. This even goes to object-oriented programming in the C++ tradition. You will need to have a special calling mechanism which wouldn't be able to do static type-checking, for example. And how about templates? This sounds even harder. You will need to have void* pointers, and to instantiate the code yourself.

Summarizing, modern languages are more than just syntactic sugar above C, and even if they were just that, it would still be very awkward to program them directly in C.


What's the difference between the concatenation and union of symbols within a language I feel like I'm confusing myself perhaps but I'm having a bit of trouble figuring out how exactly this language works. I'm given the following regular expression

(a + b)* (abba* + (ab)*ba)

Can someone clarify to what union is compared to concatenation? Looking at

(a + b)*

Is it { $\epsilon$, a, b, ab, ba, aa, aab, bbb...)? I just want to make sure, for union, that I can have any combination of a and b in whichever order.
Can I also have an example of what a word from this language may be? From what I gathered

aaababbaabbaababba
abbaba
bba
ba

would all be valid words in the given language, correct?

Simply put,

the kleene star of concatenation gives
$$(ab)^* = \{\epsilon, ab, abab, ababab, ...\} $$

while the kleene star of union gives
$$(a+b)^* =\{\epsilon,a,b,aa,ab,ba,bb,\ldots\}$$

so you got it correctly, and indeed all the words you write belong to the language.

Recall that for any two sets $L,K$ we have
$LK = \{xy \mid x\in L, y\in K\}$,
$L+K = L \cup K$,
$L^* = \{\epsilon\} \cup L \cup L^2 \cdots$.

and recall that the regular expression "a" corresponds to the set $\{a\}$ and operations between regular expressions correspond to the above operations on sets.


Complexity of specific cases of MAX2SAT I know that MAX2SAT is NP-complete in general but I'm wondering about if certain restricted cases are known to be in P. Certainly the languages
$L_k:=\{ \phi \,|\, \phi\,\text{is an instance of 2SAT which has an assignment satisfying at least k clauses.}\}$
can be solved in $O(n^k)$ through brute force search since for each language $k$ is fixed. However, I'm wondering about the case when a fraction of the clauses is specified. Does any fraction yield an NP-hard problem? Specifically I'm wondering about the case of satisfying at least half of the clauses of a 2SAT instance.
The reduction I saw from 3SAT to MAX2SAT constructs 10 clauses from each clause in 3SAT such that out of these ten, exactly 7 are satisfied when the original 3SAT clause is satisfied and at most 6 are satisfied when the original clause is not satisfied. So in this reduction the fraction of $7/10$ works but $1/2$ does not because unsatisfying truth assignments of a 3SAT instance can still yield an instance of 2SAT that has an assignment satisfying more than half of the clauses. I thought about another construction or adding extra clauses to an instance of 2SAT but I've been unsuccessful so far.

You can always satisfy at least half of clauses: for each variable $x$, find the number of clauses that contain $x$ and the number of clauses that contain $\lnot x$. Select the one which satisfies the most clauses. Remove clauses containing $x$ and $\lnot x$. Repeat for other variables.
Since for each $x$ we satisfy at least half of removed clauses, we satisfy half of the clauses overall.
On the other hand, it's also tight: let $\alpha > \frac 12$ be the fraction of clauses for which we can give an answer. Let $\beta > \frac 12$ be the maximum fraction of clauses we can satisfy in a specific clause. Then we can add clauses so that $\beta$ (for the new clause) becomes arbitrary clause to $\alpha$:

If $\beta < \alpha$, then we can add clauses $(x_i \lor \lnot x_i)$, until $\beta > \alpha$ (since these clauses are always true, $\beta$ increases).
If $\beta > \alpha$, we can add clauses $(x_i)$ and $(\lnot x_i)$, until $\beta < \alpha$ (since exactly half of clauses is true, $\beta$ decreases).

I didn't check, but to get $O(\frac 1m)$ difference (i.e. to find the exact number of clauses), I think it suffices to add $O(m)$ clauses. In other words, if we can solve for some $\alpha > \frac 12$, we can check for any $\beta$ whether $\beta$ fraction of clauses can be satisfied, and therefore we can solve MAX2SAT in polynomial time.


For $T(n) = 16(T/4) + n^2\lg^3n$ prove: $T(n) = \Theta(n^2\lg^3n)$ Define:
$
\lg x = \log_2x
$.

Let
$
f(n), g(n)
$
be some non-negative functions.

Define
$
f(n) = \Theta (g(n))
$
if
$$
\exists c_1,c_2 \in R\colon 0 < c_1g(n) \leq f(n) \leq c_2g(n)
$$

I want to prove that the function defined by the recurrence relation
$
T(n) = 16(T/4) + n^2\lg^3n
$
has the asymptotics
$
T(n) = \Theta(n^2\lg^3n)
$

I wanted to prove that by substitution method:

$$
T(n/4) \leq n^2\lg^3n
$$

Now,

$$
T(n) \leq 16(n^2\lg^3n) + n^2\lg^3n = 17n^2\lg^3n
$$

But in order for the proof to work, I should have gotten

$$
T(n) \leq n^2\lg^3n
$$

I also need to show that this is a lower bound, but I want to start by showing that it's an upper bound.

What is the right way to prove these things?

What you want to prove is false.

$T(n) = 16 T(n/4) + n^2\log^3 n$ has solution $T(n) = \Theta(n^2 \log^4 n)$.

To see this notice that this recurrence fits in the general form $T(n) = a T(n/b) + f(n)$ once you set $a=16, b=4, f(n)=n^2\log^3 n$.

Since $f(n) = n^2 \log^3 n = \Theta( n^{ \log_b a } \cdot \log^k n)$ for $k=3$, you can apply the Master theorem to conclude that $T(n) = \Theta(n^{ \log_b a } \cdot \log^{k+1} n)$.


What's the accurate definition of a compiler? Wikipedia:

In computing, a compiler is a computer program that translates computer code written in one programming language (the source language) into another language (the target language).

This implies that the compiler can also convert from a low-level language to a high-level language. But this has also got a specific name decompiler.
So what should be the definition for a compiler? 1) or 2)?

In computing, a compiler is a computer program that translates computer code written in one programming language (the source language) into another language (the target language).

A compiler is a computer program that translates computer code written in a high-level programming language into a low-level language.

As the comment points out, there's not a formal definition for "compiler", instead it's understood to be that program which translates source code into the target language. Both definitions given are adequate. The definition in Wikipedia is a good one:

In computing, a compiler is a computer program that translates
computer code written in one programming language (the source
language) into another language (the target language). The name
"compiler" is primarily used for programs that translate source code
from a high-level programming language to a lower level language
(e.g., assembly language, object code, or machine code) to create an
executable program.


Is the set of all context-free languages contained in the set of all languages that have a w-grammar? Word grammar (w-grammar) is a context free grammar in which all laws are of the following forms:
$A \rightarrow B, A \rightarrow \epsilon, A \rightarrow w_1B, A \rightarrow Bw_2$
$A, B \in N$ (nonterminal), $w_i \in \Sigma^\ast$
$ L_{w-grammar} $ - set of all languages that have a w-grammar
$ L_{CFG} $ - set of all languages that have a context free grammar
Is the following statement is true $ L_{CFG} \subseteq L_{w-grammar} $ ?

The class of languages accepted by this kind of grammar is known as linear languages (the definition on Wikipedia is slightly different, but equivalent). According to Wikipedia, the language of all balanced parentheses (generated by $S \to SS \mid (S) \mid \epsilon$) is context-free but not linear.


How to write recurrence relation for the following scenario? A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function $g(x)$ for each node x. If the cost of computing $g(x)$ is min{no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x} then what is the worst case time complexity?

Since $g(x)$ is applied on the 2 halves of the binary tree, I guess the recurrence relation must look something like :
$$T(n) = 2T\Big(\frac{n}{2}\Big)+k$$
What I could understand from the question is that $g(x)$ is applied on all the $n$ nodes and  instead of $k$ it must be something of the order $O(n)$ but I'm not sure what it is. Am I heading in the right direction?

Hints:

Can you make a guess?  If you can make a guess, can you prove it?

What do you know about the height of a balanced search tree?

If the entire tree has $n$ nodes, what can you say about the number of nodes in the left subtree?  What is the smallest it could be?  The largest it could be?  What about the right subtree?

Can you derive a recurrence relation?

Imagine you treat the cost of computing $g(x)$ to be measured in dollars, and you charge \$1 to each node in the right/left subtree (whichever is smaller) to account for the cost of computing $g(x)$.  For any given node, what can you say about how many dollars it is charged?

If you know about amortized analysis, you might review that material.

It's not clear to me what $k$ represents in your proposed approach or where you got that recurrence relation.  Why don't you try harder to work out what recurrence relation might be suitable and what its solution is?


How would I go about determining popularity and relevance among articles and use it to improve my search algorithm Disclaimer:
First of all I've had a lot of trouble finding the right stack exchange site for this question and I don't know if it's correct here either.

The Problem:
I'm working on a search algorithm for a django powered website which allows people to write articles on various subjects and search for articles on the webpage.

I've got a database in which I store articles for people to read on a website. I'm storing each article with a bit of information like:

Articles:

A title.
A predetermined category where the writer can choose from when adding
an article (sports, economy, politics).
Tags which the writer of the article can input themselves.
Length of the article in characters
A short description
Dated added
Date updated

I've a few easy ways a user can search an article based on the title ( for example shortest first or newest first)

I'm now working on adding a way to search based on popularity but I have a hard time to determine what I define as popular.

I'm saving article views in a different database table which contains:

Views:

User ID
article ID
Timestamp

Each row inside this table is considered 1 view so I can see exactly when certain articles are doing well in terms of amount of views it gets. If I would search for an article with the most views in the database it would look something like this in django:

Article.objects.order_by('-views')[:30]

In this case views is stored in the table, However I store it in a different table so I can have the functionality described above.

The problem however is that if I have 1 article which is a few years old with a high number of views, for example lets say there has been a sports event (like the Olympic games of 2014) and a lot of people have read the article but the article is no longer very relevant as this same event has been done again (that would be the Olympic games of 2018 happening this year).

Now lets say someone searches for popular articles about the Olympic games. Even though the articles about the Olympic games of 2014 have gathered more views than those of 2018 (as they have been written roughly 4 years ago and therefor have had more time to gather views)

In this case the more relevant articles should be presented to the user before the more popular articles.

My Potential Solution:

I'm thinking of adding a column to the article table for memorizing the 'importance' of each article, then I can have Importance be determined by other factors

for example if I want to have the amount of views be a factor for each view importance gets a bit higher, but if the view has been within the last week it might count as 2 views. therefor favoring more actual articles slightly more over articles with more views but written a few years ago. this also allows me to for example measure the time each reader spends on an article and have that influence importance as well.

However I'm not sure if this would be the best way of doing things as there are a few problems like:

If importance is stored in the database it has to be updated regularly and periodically which may cause performance problems whenever the user accesses an article while the database is updating it's articles importance.
Calculating the importance in real time every time a user doe a search will also take a huge amount of processing power if the amount of users is very high, it will also probably cause a lot of redundancy whenever 2 users search for the same articles and the exact same importance factor is calculated twice.

How would I go about implementing this way of sorting the search results without needing lots of processing power? Is this the best way to do it? How do other search engines handle this problem?

It seems to me like 'relevance' is a qualitative abstraction. Thus you need to define your own heuristic for your service which defines what relevance is.

I think it would be best to look for solutions in third party applications such as elasticsearch instead of implementing your own.


Binary to ASCII using logical operations I am learning Computer Architecture from Introduction to Computing Systems (2nd Edition) and am stuck on this question.

What operations can be used to convert the binary representation of 3 into ASCII representation for 3? What about binary 4 to ASCII or any other digit?

The concepts I have learnt until now are Basic Logic gates and Bit Masking so I have to use them for conversion. Can someone help me understand what my approach should be?

By looking at a ASCII table you can see that the $4$ least significant bits of all characters between $0$ and $9$ correspond to the respective integer representations of the numbers between $0$ and $9$, while the 4 most significant bits are always $0011$ (leading zeroes are not shown in the table, so keep in mind you need to pad binary numbers to 8 bits).

If $x$ is the binary representation of a number between $0$ and $9$, you can then obtain the ASCII representation of the corresponding character as
$$
x \;| \;00110000,
$$

where $|$ denotes a bitwise logical or and the second operand is in binary.


Generate random point inside a polyhedron I would like to know if there are known algorithms for generating a random point(say following a probability distribution P) inside an arbitrary polyhedron(possibly non-convex and may contain holes)?

I find approaches for 2D case like the one described here but none in the case of polyhedrons(3D). Whether extending this approach for 2D is the only way, in which case that random point will still be forced to be on the surface of a triangle of a tetrahedron in the 3D triangulation of the given polyhedron?

If you polytope is convex, this answer should work. Otherwise you can always do rejection sampling: Sample a point from the bounding box, check whether it's inside the polygon. That gets really slow for high dimensions and "unboxy" polytopes though, because the bounding box potentially has a huge volume compared to the region you're interested in.


End-Of-The-Line Augmented Problem of PPAD Famous PPAD class of problems is  formally defined by specifying one of its complete problems, known as End-Of-The-Line:

End-Of-The-Line Problem:
$G$ is a (possibly exponentially large) directed graph with no isolated vertices, and with every vertex having at most one predecessor and one successor. $G$ is specified  by giving a polynomial-time computable function $f(v)$ (polynomial in the size of $v$) that returns the predecessor and successor (if they exist) of the vertex $v$. Given a vertex $s$ in $G$ with no predecessor, find a vertex $t≠s$ with no predecessor or no successor. (The input to the problem is the source vertex s and the function $f(v)$). In other words, we want any source or sink of the directed graph other than $s$.

Let's consider the slightly augmented version of End-Of-The-Line problem.

End-Of-The-Line Augmented Problem: The definition is same as for End-Of-The-Line expect that it's required to find not a vertex $t≠s$ with no predecessor or no successor, but the exact end of the path of the given source vertex $s$.

Intuitively, it seems like End-Of-The-Line Augmented Problem is not more in PPAD, just because it requires something more stronger than End-Of-The-Line Problem. How to show that End-Of-The-Line Augmented Problem is NP-hard?

This question is answered in the original paper by Papadimitriou 1994 original paper (pdf). It turns out that the problem is not only NP-hard but also PSPACE-hard, this is theorem 2 on page 506.


A simple variant of Huffman is due, I believe, to David Wheeler.

Suppose the alphabet is $\Sigma = \{s_1, \dots, s_n\}$ and let $\star$ be some new character that's not in $\Sigma$. For each character $s\in\Sigma$, let $p(s)$ be the most common character to occur immediately after $s$ in your dataset.

To compress the string $X=x_1\dots x_N$, you first scan through it and, each time $x_{i+1}=p(x_i)$, replace $x_{i+1}$ with $\star$, giving a new string over alphabet $\Sigma\cup\{{\star}\}$. Then run ordinary Huffman on the resulting string. The idea is that the character $\star$ should be really common in the modified string, so it should get a really short codeword.

For example, if your alphabet is $\{a,b,c,d\}$ and $p(a)=a$, $p(b)=a$, $p(c)=d$ and $p(d)=c$, then the string $abacd$ would be transformed to $ab{\star}c{\star}$ and $cdcdcd$ would be transformed to $c{\star}{\star}{\star}{\star}{\star}$.

Since all your example strings begin with Z, it might also be worth storing the most common initial character to allow you to replace the first character of the string with $\star$, too.


Maximum cut using a 1/2 approximation greedy algorithm I have the following greedy algorithm for max cut problem:

Initialization: $A \leftarrow \{v_1\}$ , $B \leftarrow \{v_2\}$
For $v \in V − \{v_1, v_2\}$ do:

if $d(v,A) \geq d(v,B)$ then $B \leftarrow B \cup \{v\}$,

else $A \leftarrow A \cup \{v\}$.
Output $A$ and $B$.

Here, $v_1$ and $v_2$ are arbitrary vertices in $G$ and $d(v,A)$ denotes the number of edges between vertex $v$ and set $A \subset V$.

To show that this is a factor 1/2 approximation algorithm, I used the upper bound that $opt \leq |E|$ and internal_degree(v) and external_degree(v).

But there is a problem, I can not say that when the algorithm terminates, we have external_degree(v) $\geq$ internal_degree(v) for all v (there is a counterexample) , of course since each vertex is check once so time complexity is O(n).

Is there any other way to show this factor?

Let us say that an edge $(v,w)$ belongs to $v$ if when $v$ is processed, $w \in A \cup B$, and that $(v_1,v_2)$ belongs to $v_2$. Denote by $N_v$ the number of edges belonging to $v$, and by $C_v$ the number of those edges that are cut by the algorithm. Step 2 ensures that $C_v \geq N_v/2$ (this clearly holds for $v = v_2$ as well). Therefore $\sum_v C_v \geq \sum_v N_v/2$. Finally, notice that $\sum_v N_v$ is the number of edges in the graph, and $\sum_v C_v$ is the size of the cut produced by the algorithm.

Here is a sketch of another proof. At any point in time, define the score of an edge $(u,v)$ as follows:

If $u,v \in A$ or $u,v \in B$, the score is 0.
If $u \in A$ and $v \in B$ or vice versa, the score is 1.
Otherwise the score is 1/2.

You can check that the initial score is at least half the number of edges, the score never decreases, and the final score is number of edges cut by the algorithm.


How to properly describe this behavior (in terms of time complexity) After completing the time analysis for an algorithm I have been working on, I need some help to write its time complexity properly, let me describe how it works...

The algorithm has two inputs $x$ and $y$.

When $x < 15$, steps to solve are $2^y$, so I know this is $O(2^y)$.

However when $ x >= 15$, the steps to solve begin ramping down (from the $2^y$) at a rate of $-1\%$ as $x$ increases, up to $x < 50$ (don't know how to express this part)

And then, when $x>=50$ it flats out, and keep the same cost, that is $O(2^y*35\%)$, and doesn't matter what is the value of $x$ (as long as it is greater than $50$)

How to write a time complexity that has 3 delimited phases depending on the inputs?

You're interested in asymptotic behavior as $x$ increases without bound.

$O(.35 \times 2^y)$ is still $O(2^y)$.


Shifting subset sum solution by constant positive integer While reading the Wikipedia article about the subset sum problem I came across this example: "is there a non-empty subset whose sum is zero? For example, given the set $\{ −7, −3, −2, 5, 8 \}$, the answer is yes because the subset $\{ −3, −2, 5 \}$ sums to zero".

I have noticed that if we shift all the values of the set by adding a 8 to all elements we get $\{ 1, 5, 6, 13, 16 \}$ and then add the constant to the desired solution $0 + 8$, so now the question becomes is there a subset that adds up to $8$, which is not possible. My question is why does shifting the set and the solution by a positive integer "break" the solution, isn't the mathematics sound from the previous operations?

Your error is that you add your constant to the left-hand side of the equality multiple times, and only once to the right side. For example, $1+1=2$ clearly holds. If you add $8$ to both sides of it, you get $1+1+8=10$ which also holds. Erroneously you might add it twice to the left hand side and get $9+9=10$, which does not hold.

In your case, $0$ should not become $8$, but instead $8 \cdot 5 = 40$. Now a solution exists again.


Proving the decidability of whether a CFG generates a particular string or not Let $G$ be a context-free grammar and $w$ be a string of length $|w| = n$.

Consider the language $A_{CFG}$ = { <$G$, $w$> | $G$ is CFG that generates $w$ }, where <$G$, $w$> is a string encoding of $G$ and $w$.

Now we have to show that $A_{CFG}$ is decidable, or in other words, there exists an algorithm that determines whether $w$ is generated by $G$ or not.

Now, the proof given in my book converts $G$ into an equivalent CFG $G'$ in Chomsky Normal Form and one-by-one checks all derivations in $G'$ that take $2n - 1$ steps, since a grammar in CNF takes exactly $2n - 1$ steps to generate a string of length $n$.

Now, I have an alternate algorithm in mind. I want you guys to tell me if there is something wrong with it or not because this one seems to be much simpler than the one given in my book.

So, since every CFG has a pushdown automaton which recognizes the same language, we convert the CFG into an equivalent PDA. Now we simulate the PDA on our Turing machine on the string $w$. This process must end in a finite number of steps since our string is finite in length.

Is this an alternate algorithm that illustrates the decidability of $A_{CFG}$ or is there something wrong with it?

If you give a word $w$ not in the language, then the TM is not guaranteed to halt as an NPDA isn't always guaranteed to terminate in finite steps for a finite word.

So, you can produce a counter example in which your construction doesn't work. Take an NPDA which doesn't terminate for a given word (exists, of course) and run your algorithm on that word. Since that word is not in the language your TM won't ever produce any output as simulation will never end. You were supposed to output a "NO" here.

On the other hand, the CNF algorithm works because it guarantees execution in finite steps for every word, whether it belongs to the language or not.


Efficiently find maximum XOR on a graph We are given an undirected graph $G=(V,E)$, $|V| \leq 50$. We are also given a starting vertex $s$. Each vertex $v$ of the graph is associated with a natural number $N_v$. Initially our profit is  $R=N_s$.

Now we have to traverse the graph beginning from $s$ in an order. We can visit each vertex or edge any number of times. Whenever we reach a vertex $v$, $R=R \operatorname{XOR} N_v$. (Note that if we visit $k$ times a vertex $v$, then we will XOR $k$ times with $N_v$.)

Find the maximum value of $R$ that can be obtained while traversing $G$.

Note: Here traversal means  walk beginning from $s$.

I'm going to first assume that your graph is connected; that is, every node of the graph is reachable from $s$. We'll relax this condition down the line, but for now, it simplifies the problem.

Now, let's start with what we know. If $G$ is connected, then we can visit every vertex; that is, there's some path $p$ that goes to each vertex $t$.

Let's examine such a path $p = (p_0 = s), p_1, \dots, p_{n-1}, (p_n = t)$. By definition, we know that the value of such a path is just $R(p_0, \dots, p_n) = \bigotimes_k N_{p_k}$. In addition, if at $p_n = t$, we immediately turn back and travel backwards on $-p$ (the reverse path of $p$), then we would eventually arrive back on $s$ with a value of
\begin{align*}
R(p, -p) &= R(s, \dots, p_{n-1}, t, p_{n-1}, \dots, s)\\
&= \left(\bigotimes_{0 \le k \le n} N_{p_k}\right) \otimes \left(\bigotimes_{0 \le k \le \bf n-1} N_{p_k}\right) \\
&= (N_{p_0} \otimes N_{p_0)} \otimes (N_{p_1} \otimes N_{p_1)} \otimes \dots \otimes (N_{p_{n-1}} \otimes N_{p_{n-1}}) \otimes N_t
\end{align*}

Recall that xor has the property that $x \otimes x = 0$, the identity. therefore, any path from $s$ to $t$ and back to $s$ just gives a value of $N_t$. In fact, any conjunction of paths
$$
s \stackrel{p_1}{\to} v_1 \stackrel{-p_1}{\to} s \stackrel{p_2}{\to} v_2 \stackrel{-p_2}{\to} s \stackrel{p_3}{\to} \dots \stackrel{-p_n}{\to} s
$$
gives a value of
$$
N_s^{n + 1} \otimes \bigotimes_k^n N_{v_k}
$$
Furthermore, we can get rid of the $s^{n+1}$ term by deciding to stop the final path immediately before the terminal vertex if it falls on an even $n$.

In essence, this tells us that it is possible to construct a walk starting at $s$ such that the value of this walk is $\bigotimes_{v \in S \subseteq V(G)} N_v$ for any subset of vertices of $G$.

This then suggests that your problem reduces down to finding a subset of vertices $S \subseteq V(G)$ such that $\bigotimes_{s \in S} N_s$ is maximum over $V(G)$.

At first glance, this might seem like a non-trivial covering/knapsack problem. For one thing, the naive strategy here seems to be to try out every subset of $V(G)$. In addition, there doesn't seem to be any sort of monotonicity, continuity, or even some form of "optimal substructure" property for us to exploit.

Fortunately for us, this problem admits a relatively nice representation in terms of a linear algebraic system, and its solution process is equivalent to finding the rank of an induced matrix, or alternatively, Gaussian Elimination.

Now, suppose that we have a set of annotated vertices $N = \{N_v \mid v \in V(G)\}$, how do we represent this as a linear system?

Well, given an integer $N_v = 1011\cdots01_2$ in binary, then we can think of it as the column vector
$$
[\![N_v]\!] = \left(\begin{array}{c}1\\0\\ \vdots \\ 0 \\ 1\end{array}\right)
$$
Now, let's consider the semi-ring $(+ = \otimes, \times = \max = \times_{\mathbb{N}})$ over bits (0, 1). Here the addition operation is bit xor and the multiplication operation is the usual integer multiplication, which also happens to be the $\max$ operation or the $\wedge$ conjunction operation.

We wish to find coefficients $c_0, c_1, \dots, c_n$ such that
$$
c_0 [\![N_{v_0}]\!] + \dots + c_n [\![N_{v_n}]\!]
$$
is "maximized". In particular, we wish to analyze the $A_N: k \times n$ system
$$
\left(A_N = \left(\begin{array}{ccc}[\![N_{v_0}]\!] & \cdots & [\![N_{v_n}]\!]\end{array}\right)\right) \left(\begin{array}{c} c_0 \\ \vdots \\ c_n \end{array}\right)
$$
where $k$ is the size of your bit-vectors (likely $32$ or $64$). Now, chances are, this system is over-determined (but also rank-deficient). Therefore, our first instinct will be to reduce this system to reveal its rank structure.

Doing this ends up giving us an efficient algorithm: Gaussian Elimination.

The idea is as follows. We try to solve the problem of
$$
A_N c = \left(\begin{array}{c}1 \\ \vdots \\ 1\end{array}\right)
$$
through Gaussian Elimination. Now, I need to emphasize that we are only trying to solve this problem because, chances are, there is no solution! Think about it, $A_N c$ gives the bit-vector that corresponds to the final value of a walk, so if $A_n c = 1$ always has a solution, then it means that our problem is trivial: always return $2^{32} - 1$. In fact, in pretty much all interesting cases, there's no way to satisfy this attempted equality.

"What? Why are you doing this to me then?"

Simple, we actually inspect a trace of the algorithm rather than the final solution. In particular, at each iteration of Gaussian Elimination, we might find ourselves in one of two situations. Either everything still goes fine and dandy, and we can continue elimination, or we reach a contradictory state where we realize that we can't proceed. In the latter case, this corresponds to a case where you need to add a row of zeros and somehow magically pull a one out. In such cases, rather than aborting, we will just concede the impossibility and replace that row in the output with a zero.

More concretely, after $m$ iterations of elimination, we are left with a subproblem in which we only have to analyze the subsystem starting at the $m^{th}$ row. All of the prior rows will be zeros or part of the identity grid.

At the $m^{th}$ row, either there is some column $[\![N_{v_i}]\!]$ in our intermediate matrix that has a leading $1$ in that row, or it's impossible to fill that row in the output.

In the former case, we will select one such column to pivot (and with a bit of thought, you should choose the largest column), and add (subtract, since the inverse of $\otimes$ is still $\otimes$) it from every other column that still has a leading $1$ in that row.
Otherwise, we will be forced to concede that the only solution is to place a $0$ in the output at that row and move on.

This then gives an algorithm find a maximum subset with respect to $\otimes$:

for each i from 31 down to 0, do
  if there's some maximal vertex v such that N(v) >= 2^i, then
    select v as a pivot and remove it from future considerations
    for every other vertex u such that N(u) >= 2^i, do
      N(u) := N(u) xor N(v)
    end for
  else,
    // Here, we can't possibly hope to fill this row with a one, so
    do nothing
  end if
end for

Now, the set of pivots that you have selected will give you the maximum xor-subset; just xor them together to find the maximum. The number of pivots also corresponds to the rank of your system, and if there are 32 pivots, then that immediately means that your maximum value is $2^{32} - 1$. If there are 31 pivots, then that means that there's a single 0 somewhere in your bit vector; 30 pivots means that there are two holes; etc.

Finally, we relax the restriction that our graph be connected. Rather, we will simply preprocess the graph and identify the connected component that contains the vertex $s$, and proceed similarly afterwards.

Best of luck!


What is the relationship between the number of transition rules for an NDTM and the resulting number of computational branches? How can an NDTM have a growing number of branches as you feed larger and larger inputs with only finite number of transition rules specified--ie what is the relationship between the number of branches and the number of transitions?
An NDTM has a finite number of states, a finite number of input symbols and a finite number of transitions--but presumably the number of branches used grows as you feed larger and larger strings to it--how, mechanically, does this work?
if the number of branches keeps growing as word size grows does this not imply an infinte number of transition rules need be spelled out in the definition of NDTM (since there are an infinte number of word sizes) or do # of transition rules and # of branches not have a one-to-one relationship like this?

we can see how the computation tree grows with finite alphabet and rules even when using a DFA , consider the following :

We begin at 1 , then when reading a , we arrive at 1 and 2 , reading another a , 1 arrives at 1 and 2 , 2 arrives at 1 and 2 , so we are at 1,2,1,2 and so on , here is a part of the computation tree :

Hopefully you can see how the computation tree grows exponentially with every symbol , the arrows to the left represent the string read up to this level
Of course the same can be shown for a TM , you can imagine this DFA as a TM , which reads a symbol , writes nothing then goes to right , and you will yield same result
As for a relation , we know that every t(n) time nondeterministic single-tape Turing machine has an equivalent 2O(t(n)) time deterministic single-tape Turing machine.


Why do we create universal turing machines? Why do we create Universal Turing Machine explicilty to simulate the run of a word (say, $w$) on a Turing Machine $M$, given the description on it? Can't we just run $w$ on $M$ itself? I don't see the point of it.

Theoretically, the universal Turing machine $U$ was defined to prove the undecidability of certain problems. Roughly speaking, we're talking about a machine that is able to decide what any other Turing machine decides. So assuming that Turing machines fully capture the notion of decidability, then it holds that anything that can be decided, can also be decided by $U$. Conversely, any problem that is not decided by the universal machine $U$ is considered to be undecidable.
To be more concrete, the ability of $U$ to take as input an encoding of another machine $M$ and an input $w$ of $M$, enables us (the machine $U$) to ask questions about other machines $M$. For example, a consequence of this ability is that we can ask whether $M$ halts on $w$: is there a universal machine $U$ that decides whether $M$ halts on $w$? More formally, is there a machine $U$ that decides the language $Halt_{TM} = \{ \langle M, w\rangle: M \text{ is a TM and $M$ halts on the input $w$}\}$.
One, with a diagonalization argument, can prove that the $Halt_{TM}$ is undecidable. $Halt_{TM}$ is known as the halting problem: is there a program that eventually halts and tells us whether another program (which is given as input) halts?
So, thanks to universal machines, we can ask all these interesting questions about machines, and get undecidability results.


Approximation concerning Asymmetric TSP, Symmetric TSP, and Metric TSP I always considered Symmetric TSP to be inapproximable in general, and thus by extension Asymmetric TSP as well. Once you add the condition of the triangle inequality however, you obtain Metric TSP (which can be Symmetric or Asymmetric), which is approximable (e.g. Christofides algorithm).
However, I'm having doubts after finding the following paper :
An improved approximation algorithm for ATSP
Vera Traub, Jens Vygen (https://arxiv.org/pdf/1912.00670.pdf)
In their paper, there is no mention of Metric TSP, or the triangle inequality. Does this mean that I'm misunderstanding, i.e. Asymmetric TSP is in fact approximable, even without the triangle inequality?
EDIT : As Discrete Lizard pointed out, Metric TSP seems to not just imply (any) TSP respecting the triangle inequality, but rather Symmetric TSP respecting the triangle inequality. This does not change my last question though, and Yuval Filmus' answer is still correct.

Here is an excerpt from the introduction to an earlier paper of Svensson, Tarnawski and Végh, which was the first to give a constant factor approximation algorithm for ATSP:

Without any assumptions on the distances, a simple reduction from the problem
of deciding whether a graph is Hamiltonian shows that it is NP-hard to approximate
the shortest tour to within any factor. Therefore it is common to relax the problem by
allowing the tour to visit cities more than once. This is equivalent to assuming that the
distances satisfy the triangle inequality: the distance from city $i$ to $k$ is no larger than
the distance from $i$ to $j$ plus the distance from $j$ to $k$. All results mentioned and proved
in this paper refer to this setting.


In complexity, why do we find upper bounds, not lower bounds? In algorithms we use to find Big-O (upper bound), Big-omega (lower bound) and Big-Theta but why we are always interested in finding upper bounds instead of lower bounds?

Lower bounds are of great interest and an active topic of research. However, we tend to be interested in lower bounds for problems and upper bounds for algorithms.

An upper bound for an algorithm is a performance guarantee: the algorithm will not use more than such-and-such an amount of memory or processing steps when run on an input of a particular size. On the other hand, lower bounds for algorithms aren't especially interesting, since most algorithms can be modified to be fast on certain instances and knowing that an algorithm might terminate very quickly isn't often a useful guarantee.

Conversely, any algorithm is an upper bound for the problem it solves. Lower bounds for problems, on the other hand, tell you whether it's worthwhile looking for a faster algorithm than the one you already have. Examples of lower bounds you'll probably be familiar with are completeness results (especially NP-completeness) and the fact that comparison-based sorting takes time  $\Omega(n\log n)$.


Why are struct and class essentially the same in C++? struct and class in C++ are nearly identical (as covered for example here).

But why is this so? What did happen when C++ was developed and eventually standardized, that struct was allowed to define a full OOP class, yet class keyword was also added? There must be a historical reason for this, but I did not find an answer by searching.

In contrast, for example C# uses these keywords too, but there they have different and distinct meaning. I would say this is quite a valuable feature in that language.

In hindsight, it would have for example made sense to keep C++ struct be always compatible with similar C struct in memory layout, and only those class features that are compatible with that would have been supported (so no "virtual" stuff, value always copyable by memcpy, maybe even some kind of C interoperability for struct methods). Or something else perhaps; point is, the distinction could have meant something and added to the language, instead of being a (small) source of confusion it is now.

So I am looking for some historical record, quote or story, which would explain this.

Bjarne Stroustrup writes in his The Design and Evolution of C++ book (item 3.5.1):

  At this point, the object model becomes real in the sense that an object is more
  than the simple aggregation of the data members of a class. An object of a C++ class with a virtual function is a fundamentally different beast from a simple C struct.
  Then why did I not at this point choose to make structs and classes different notions?

  My intent was to have a single concept: a single set of layout rules, a single set of lookup rules, a single set of resolution rules, etc. Maybe we could have lived with
  two sets of rules, but a single concept provides a smoother integration of features and
  simpler implementations. I was convinced that if struct came to mean "C and compatibility" to users and class to mean "C++ and advanced features" the community would fall into two distinct camps that would soon stop communicating. Being able to use as many or as few language features as needed when designing a class was an important idea to me. Only a single concept would support my ideas of a smooth and gradual transition from "traditional  C-style  programming," through  data abstraction, to object-oriented programming. Only a single concept would support the notion of "you only pay for what you use" ideal.

  In retrospect, I think these notions have been very important for C++'s success as a practical tool. Over the years, just about everybody has had some kind of expensive idea that could be implemented "for classes only," leaving low overhead and low features to structs. I think the idea of keeping struct and class the same concept saved us from classes supporting an expensive, diverse, and rather different set of features than we have now. In other words, the "a struct is a class" notion is what has stopped C++ from drifting into becoming a much higher-level language with
  a disconnected low-level subset. Some would have preferred that to happen.


Error in proof of decidability $L=\{\left<M\right> \ | \ M $ is a TM s.t. $M$ does not accept any string starting with a '1' $\}$.
   Assume the alphabet to be $\Sigma = \{0,1\}$.

By Rice's theorem $L$ is undecidable. I managed to "prove" that $L$ is decidable. So can someone point out the error in my proof. To keep things clean I ignore the empty string since it can easily be dealt with as a special case.

We can write $$L = \{\left<M\right> \ | \ w\in \Sigma^*, \ w \in L(M) \implies w[0] \neq 1\}$$
$$ = \{\left<M\right> \ | \ w\in \Sigma^*, \ w \in L(M) \implies w[0] = 0 \}$$
To get $\overline{L}$ we need to negate the condition in $L$. Hence
$$\overline{L}= \{\left<M\right> \ | \ w\in \Sigma^*, \ w \in L(M) \implies w[0] = 1 \}$$

We have
$$\exists \ w\in \Sigma^* \text{ such that } w\in L(M) \text{ and } w[0] = 1 \iff \left<M\right>\not \in L \iff \left<M\right> \in \overline{L}$$
We can construct a recognizer for $\overline{L}$ by searching for such a $w$

$R=$ 'on input $\left<M\right>$ where $M$ is a valid TM:

for $w \in \Sigma^*$:
$\ \ $if $M(w) =$ accept
$\ \ \ \ $if $w[0]=1$ then accept'

So $\overline{L}$ is recognizable. Similarly we have

$$\exists \ w\in \Sigma^* \text{ such that } w\in L(M) \text{ and } w[0] = 0 \iff \left<M\right>\not \in \overline{L} \iff \left<M\right> \in L$$
We can construct a recognizer for $L$ by searching for such a $w$

$R'=$ 'on input $\left<M\right>$ where $M$ is a valid TM:

for $w \in \Sigma^*$:
$\ \ $if $M(w) =$ accept
$\ \ \ \ $if $w[0]=0$ then accept'

So $L$ is also recognizable, this means $L$ is decidable.

Your language is indeed co-c.e.; the mistake is in the argument claiming recognizability of $L$. You have the existential and universal quantifier mixed up.


Requirements for a TM to halt I'm just beginning self-studying a course on computability and automata; my textbook, describing a generic Turing Machine, lists two following halt conditions:

A TM halts, if for a particular state $q \in Q$, $\delta(q, a) = (q, a, HALT)$ for all $a$ in the alphabet and this $q$ is called a halt state;
A TM also halts, when the TM reads $a$ while being in $q$, and $\delta(q, a) = (q, a, HALT)$ is true only for this particular $a$.

I have no problems comprehending the first one, but I'm a little frustrated by the second one, that is, I don't understand, why the exclusivity of $a$ is of any importance. Won't the machine halt if we have several $a, a'$, for both of which it's supposed to halt?

And in general, are there any other halting conditions possible?

The first condition makes no sense whatsoever to me, and neither condition is expressed in the most obvious way. I can't imagine why you'd ever want to define halting in that way.

A Turing machine halts exactly when it enters the HALT state.  It's as simple as that.  The only alternative I've ever seen is to have two halting states, corresponding to accepting and rejecting the input. In that case, the machine halts exactly when it enters either one of them.

Your source seems to be adopting a different approach, in which "HALT" is not a state but an action of the machine in the same class as "move the tape head left" or "move the tape head right". That's unusual, but not problematic in its own right. However, neither definition of halting is the one that I would expect.

The second one is the closest: the machine halts if it decides to stay in its current state, leave the current character on the tape and make the HALT action. But this is still strange – surely the HALT action on its own should halt the machine, regardless of what state the machine moves to and what it writes on its tape at that step? For example, the behaviour of hte machine at the next step would seem to be undefined if $\delta(q,a)=(q',a',\mathrm{HALT})$ and $q'\neq q$ and/or $a'\neq a$.
The first definition is very unnatural. I can see no motivation for saying that the machine halts only if it's in a state where seeing any character whatsoever would cause it to stay in the same state, leave the tape as it is and making the HALT action. In fact, this is basically defining the state to be a halting state in the way that Turing machines are usually defined. If one wanted to go down that route, why not just use the conventional HALT state instead of making HALT an action of the machine?

Note, however, that these definitions of halting, and the standard one, are all equivalent in that they can simulate each other. So, whichever of these definitions you use, the same class of problems can be computed by Turing machines.


How do we show that the polynomial time reduction of one problem to another has been done in polynomial time? I have just been reading through a SO post which proves that the Halting Problem is NP-Hard. Whilst this is an easily followed proof, one slight slight aspect of it has left me scratching my head: it says that

  "This pairing can be done in polynomial time, because the Turing machine has only constant size."

So their justification for saying that the reduction was done in polynomial time is that the Turing machine 'only has constant size'.

Why would this prove that the reduction was done in polynomial time?

The reduction described in the mentioned post, from SAT to the halting problem, performs the following mapping:

$$\varphi\mapsto \big(\langle M\rangle,\varphi \big)$$

where $\varphi$ is a CNF formula and $M$ is the Turing machine which given a CNF $\psi$ as input, iterates over all the possible assignments to the variables of $\psi$, and enters a loop iff no satisfying assignment was found.

The machine $M$ does not depend on the input of the reduction, so it has some constant size description independent of the input $\varphi$. This means that you can output $\langle M \rangle$ in polynomial (even constant) time relative to the size of $\varphi$, hence the reduction is computable in polynomial time.

Note that you only need to show that you can generate $\langle M \rangle$ in polynomial time, which does not necessarily mean it has to have a constant size. Suppose e.g. that we want to show that $L=\{\langle M\rangle | \text{M halts on input $\epsilon$}\}$ is NP hard. In that case, the reduction $\varphi\mapsto \langle M_{\varphi}\rangle$ does the trick, where $M_{\varphi}$ is the machine which ignores its input, iterates over all possible assignments for $\varphi$, and enters a loop if no satisfying assignment was found. $M_{\varphi}$ does not have a constant size description, since you have to hardcode $\varphi$ into it. However, you can still generate $\langle M_{\varphi}\rangle$ in polynomial time, which makes the reduction polynomial.


Are there any steps or rules to draw a DFA? In my first lecture of "Theory of Automata", after giving some concepts of Alphabet, Language, transition function etc. and a couple of simple automata of an electric circuit with one and two switches, is this question.

I understand what an Alphabet as well as the Language of a DFA is, but are there any rules or steps to followed to reach a correct automaton for a given Language? Or we just have to imagine and think in our mind and get to a solution which satisfies the given Language?

Note:- Please keep your language as simple as you can, since this is my first lecture and I am not yet aware of concepts like regular expressions or any other thing in the subject for that matter.

Do not confuse defining an automaton and drawing an automaton.

The drawing is intended as a support for better intuition, and because
it can often be read more easily in a single look. That is what
drawing are usually for.

However, you are supposed to actually (be able to) give a formal
definition, with the mathematical notation you learned, including
specifying the transitions (not necessarily one by one).

In your example you could say, after specifying the transitions for
the accepted string: this is completed by all transitions on terminals
not yet considered in each state, each going to $q_{die}$, and all
transitions on $q_{die}$ going back to it.  Even this can be said more
formally.

It is up to you, and to your instructor, to decide on the proper level
of formalism. A drawing is usually enough in simple cases, as it is
clear how to get the formal mathematical definition from it.

But for some more abstract problems, drawings are inconvenient, and
the mathematical notation is much more easily used. Up to you to decide.

Constructing the automaton, as drawing or as math definition, depends
on the problem at hand. There are many way, and your problem may often
be to find the right one. Much of your course will be to teach you
ways of building automata. These are only early and very simple
exercises.

One point worth remembering. In order not to clutter drawings or
descriptions, the state $q_{die}$ (or some equivalent states) is often
onitted, as well as all transitions leading only to it (the reader is
supposed to complete as I explained above).  This is convenient, but
dangerous ... some constructions or reasonnings based on automata rely
on the fact that all transitions are taken into consideration ...  and
you may forget those that do not show explicitly.


Can anyone find a mapping from the set of all possible string to the natural numbers? Can anyone find a map(injection) $h$ from the set of all possible strings $S^*$ to the natural numbers $\mathbb{N}$?

$$h : S^* \rightarrow \mathbb{N} $$

Assume $S$ is finite. I would prefer an efficient map.

There should be nice applications of this question for perfect hashing, right?

Just pretend that your alphabet $S = \{0, \dots, s\}$ for some $s$ and then a string in $S^*$ is just a natural number written out in base $s+1$. There's the slight wrinkle that $0$, $00$, $000$, etc. are all representations of zero, but that's easily fixed by associating the string $x$ with the number whose base-$(s+1)$ representation is $1x$ (i.e., $x$ with a $1$ stuck on the front).


Can Stoer-Wagner find min s-t cut for given s and t? Stoer-Wagner algorithm can be used to find global minimum cut in a graph. I'm wondering if it could be adapted to find a minimum s-t cut, given s and t. We can start a single phase with {s} but there's no guarantee that vertex t will end up in the other subset. Is there any way to do it?

Finding a minimum s-t cut is easier than finding a minimum cut, so there is no reason to use or adapt Stoer-Wagner; instead, using a standard algorithm for finding a minimum s-t cut, such as using a network flow algorithm.


Algorithm to construct a parabola that hits a given target and avoids given boundaries I'm working on a video game and I'm struggling with the math behind one of the enemies.  The enemy is a grenade launcher mounted on a vertical rail, which can slide up and down, and lob a grenade at any angle with any amount of force.  The grenade's path will be a parabola which must hit the player, but there are line segment boundaries in the way represented by their two endpoints which the parabola must avoid.
Here is a drawing:

What I'd like to do is calculate the equation for the parabola of the grenade which hits a target and misses all of the boundaries, from which I can figure out the position, angle, and force for the launcher to use.  The parabola must be subject to these three constraints:

The parabola must pass through the target point $(x_T, y_T)$
The parabola must pass through the line segment $\overline{RS}$
For each boundary $\overline{EF}$, if the parabola passes through the segment, it must not happen between the line $\overline{RS}$ and the target point.

Depending on where the target is, there may be no solution, in which case I'd like it to return that information.  If there is any solution there will be multiple; I would only need one.
What I've tried so far:
We can represent the parabola as $y-y_T=A(x-x_T)^2+B(x-x_T)$, which takes care of the first constraint, and means we need to find values for $A$ and $B$ that satisfy the other two constraints (we know $A$ must be negative because of the direction of gravity).  Then for each boundary $\overline{EF}$ on the map, with endpoints $(x_E,y_E)$ and $(x_F,y_F)$, we can represent the boundary line as $(y_E-y_F)x+(x_F-x_E)y+(x_E y_F-x_F y_E)=0$.  From that I can find the points of intersection between the line and the parabola, and make sure that for every boundary, the x-values of the points are either not between $x_E$ and $x_F$, or they are not between $x_S$ and $x_T$.  This quickly becomes a nasty quadratic equation, which then creates a system of linear inequalities that I don't know how to solve.  Can anyone think of a better way to approach the problem?

Consider an endpoint $(x_E,y_E)$  of an obstacle line segment.  I'm going to assume for simplicity that if the projectile goes exactly through $(x_E,y_E)$, this is a legal trajectory, i.e., it's OK for a projectile to "just graze" the obstacle.  (If that's not OK, it is easy to adjust the solution below to just miss the corner by a tiny amount $\epsilon$, or it is easy to adjust the size of each obstacle by $\epsilon$ in each direction.)
Let's define a "grazing constraint" as one of the following possibilities:

If the point $E$ is a vertex of an obstacle (i.e., an endpoint of an obstacle line segment) or is $R$ or $S$, then "The parabola must go through $E$" is a grazing constraint.

If $EF$ is an obstacle line segment, then "The parabola intersects $EF$ and is tangent to it" is a grazing constraint.

In this way, given $n$ obstacle line segments, we obtain $2n+2$ possible grazing constraints.
Now I make two claims:
Claim 1: Any two grazing constraints uniquely determine the parabola.
Proof: If both grazing constraints are of the "must go through E" type, then together with the target $T$, we have three points, and any three points uniquely define a parabola, i.e., given three points, there is a unique parabola that goes through those three points.  A similar argument can be made if one or both of the grazing constraints are of the "tangent" type.
Claim 2: If there is any solution to your problem, there is a solution that satisfies two of the possible grazing constraints listed above.
(I don't have a proof for this claim.)
This immediately suggests a simple algorithm: enumerate over all pairs of grazing constraints, find the unique parabola that satisfies those two grazing constraints and goes through the target $T$, and check whether this parabola avoids all obstacles and intersects the starting line segment RS.  You can check whether it avoids all obstacles by iterating over all obstacle line segments, and for each, finding the intersection using the method you described.  If there is a valid solution to your problem, this method will find it.
The running time of this method will be something like $O(n^3)$, where $n$ is the number of obstacle line segments.  I don't know if there is a more efficient method.  There might well be.


Intersection of regular and not regular $L_1=\{a^n\mid n\ge1\}$ is regular and
$L_2=\{a^{n^2}\mid n\ge1\}$ is non-regular.
We know that $L_1\cap L_2$ is regular but,
here $L_1\cap L_2=L_2$; and $L_2$ is not regular. How is this possible?

To expand a bit on David's answer, you are confusing between the next two claims.

Claim 1 if $L_1,L_2$ are regular, then $L_1 \cap L_2$ is also regular.
(proof: construct the product DFA, e.g., here)

Claim 2 if $L_1$ is regular, but $L_2$ is not, then $L_1\cap L_2$ can be either regular or not-regular.
(proof: Let $L_2$ be some non-regular language. If $L_1=\Sigma^*$ then $L_1\cap L_2=L_2$ which is non-regular by its definition. On the other hand, if $L_1=\emptyset$ then $L_1\cap L_2=L_1=\emptyset$ which is regular)


Generating all words of length $n$ avoiding $A^2$ and $B^3$ I need to find a way to iterate over all sequences of words in two letters $A,B$ avoiding the sequence $A^2 = AA$ and $B^3 = BBB$.  First of all, what is the regular expression for such a thing?

I need a way of iterating over all such possible words.  I tried this one:
$$ w \mapsto \{ wA, wB, wBB\} $$

however, if I run this function again, we obtain:
$$ w \mapsto \{ wAA,wAB,wABB,wBA,wBB,wBBB,\dots  \}$$
and you can see we have obtained the expressions we are trying to avoid.

I need way of generating all the words in $\{A,B\}$ of length $n$ avoiding these two patterns.

Instead of constructing a regular expression, it is better to construct a DFA, or rather, a DFA with some "missing transitions". The DFA has the following states:

$q_0$: initial state.
$q_A$: state after seeing one A.
$q_B$: state after seeing one B.
$q_{BB}$: state after seeing two Bs.

The transition function is
$$
\begin{array}{c|cccc}
& q_0 & q_A & q_B & q_{BB} \\\hline
q_0 & & A & B & \\
q_A & & & B & \\
q_B & & A & & B \\
q_{BB} & & A & &
\end{array}
$$
This is read as follows: when at row $q$, upon reading $\sigma$, move to the appropriate column, if any. If there is no appropriate column, we have reached the (invisible) sink state.

Using this, it is not hard to see that the number of words of length $n$ in your language is
$$
\begin{pmatrix}
1 & 0 & 0 & 0
\end{pmatrix}
\begin{pmatrix}
0 & 1 & 1 & 0 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
0 & 1 & 0 & 0
\end{pmatrix}^n
\begin{pmatrix}
1 \\ 1 \\ 1 \\ 1
\end{pmatrix}.
$$
Calculation shows that for $n \geq 1$, the number of words of length $n$ in your language is
$$
\mathrm{round}(C \lambda^n), \text{where } C \approx 1.678735602594163 \text{ and } \lambda \approx 1.324717957244746.
$$
The eigenvalue $\lambda$ is also the unique real root of $x^3-x-1$.

A glance at the OEIS reveals that your sequence is A164001, and has the recurrence
$$
a_n =
\begin{cases}
n+1 & n \leq 3, \\
a_{n-2} + a_{n-3} & n \geq 4.
\end{cases}
$$
(The recurrence $a_n = a_{n-2} + a_{n-3}$ is of course related to the polynomial $x^3-x-1$ above.)


Mealy machines to model ciphers Similar questions have occurred quite a number of times (1) (2) (3), but I have, say, a specific instance of one. I'm aware of a bunch of applications of finite automata, but would you provide an academic exposition of applications of finite state machines (like, e.g., Mealy machines) in cryptography and ciphers? There is a mention about things like that in Wikipedia article on Mealy machines (subsection “Applications”). So the links to some academic texts play up on this are very appreciated. Alternatively would you share your thoughts on how to furnish this topic (FSM in cryptography) for students?

Consider the coding $a \to 0$, $b \to 1010$, $c \to 100$, $d \to 1011$, $r \to 11$.$\ \ $  I let you guess what represents $010101101000101101010110$ in this coding, but this can be easily computed by a sequential machine, as illustrated
here, slides 9-10.

What is the theory behind this? A subset $P$ of $A^+$ is a prefix code if no element of $P$ is a proper prefix of another element in $P$. For instance, the sets $\{0, 1010, 100, 1011, 11\}$, $0^*1$ and $\{0^n1^n \mid n > 0\}$ are prefix codes, with $A = \{0, 1\}$. Prefix codes are conveniently represented by the leaves of a tree. In particular, variable-length Huffman codes, the UTF-8 code and the Morse code are of this type.

Now if $B$ is another alphabet and $f:B \to P$ is an injective function, then $f$ extends uniquely to an injective monod morphism (coding) from $B^*$ to $A^*$. Further, if $P$ is a finite subset of $A^+$, the decoding function $f^{-1}$ can be computed by a sequential machine. This machine is essentially the minimal automaton of $P^*$, equipped with appropriate outputs (see the example).

Variable-length codes (whose prefix codes are a special case of) form the topic a rather advanced theory. The main reference is:
J. Berstel, D. Perrin, C. Reutenauer, Codes and automata. Encyclopedia of Mathematics and its Applications 129. Cambridge: Cambridge University Press (2010). ISBN 978-0-521-88831-8.


Revisiting Fixed Point: What does it mean in the world of computer science? A while ago I asked Fixed point, what does it mean in the world of computer science?

While the answers did help me to understand what Fixed point meant, the answers left me in a murky world when ever I thought about what a fixed point meant. In other words, no clear definition poped into my mind and I would wonder about in thought trying to match up a definition with what I was trying to learn or understand.

Today I was watching the video Categories for the Working Programmer by Jeremy Gibbons in which he stated: (Time index: 33:00)

  It's fix point because it's the solution of a recursive equation.

And I thought that makes sense; is it really that simple?

So the question is:

Can the definition of fix point be thought of simply as

  "It's the solution of a recursive equation."

A fixed point of a function $f$ is an element $x$ satisfying $f(x) = x$. A solution to a recursive equation can be put in that form.


Push Down automata:- Basic doubt I was reading CFG's and PDA's. I need to understand one basic point in that.I have solved some questions on final state acceptance by PDA.But in every answer,the string always end with epsilon(means that there is always a transition when string ends which by reading epsilon takes to final state and mostly it invloves checking that current stack TOP is same as initial symbol).

Do we assume that there is some end of string marker in PDA?I have not seen such thing in DFA/NFA.If the string ends,then there is no need to read epsillon in that,but what is the requirement for this in PDA?Or does this depends on the problem in context?

In general we do not assume that push-down automata have an end-of-string (or end-of-input) marker.

PDA have two modes of acceptance, with final state and with empty stack. Even when the automata are written for final state acceptance it is helpful in the design to check that the stack is empty. That ensures no data is unprocessed.

The PDA on wikipedia for the language $\{0^{n}1^{n}\mid n\geq 0\}$ has transitions: $(p,0,Z,p,AZ)$,
 $(p,0,A,p,AA)$,
 $(p,\epsilon ,Z,q,Z)$,
 $(p,\epsilon ,A,q,A)$,
 $(q,1,A,q,\epsilon )$, and
 $(q,\epsilon ,Z,r,Z)$. Initial state $p$ and final state $r$. This indeed is of the form you describe.

The same language can be accepted without $\epsilon$-transitions at all.

$(p,0,Z,q,Z)$, $(q,0,Z,q,AZ)$, $(q,0,A,q,AA)$, $(q,1,A,r,\epsilon)$, $(q,1,Z,s,\epsilon)$,  $(r,1,A,r,\epsilon)$, $(r,1,Z,s,\epsilon)$. Initial state $p$ and final states $p$ [to accept $\epsilon$] and $s$.


Does a notion of a context-free complete language exist? Is there a notion of a context-free complete language (in the analogous sense to a $NP$-complete language)?

Yes.

Lautemann and Schwentick prove that Greibach's "hardest context-free grammar" with a neutral symbol is complete for $LOGCFL$ and hence $CFL$ also, under quantifier-free projection without BIT.

This is Corollary 4.3 in their paper


Complexity of calculating a single model versus all models of a propositional formula with a SAT solver I have little background with SAT sovers and theoretical computer science.

How can I describe the complexity of calculating all models of a propositional formula versus just the usual SAT problem of finding just one model?

I am writing a paper, in an area where finding a single of a model of a type of propositional formula is considered "easy", but for my reasearch I need to calculated all models. (I am using Picosat that can calculate all models of a logic formula.) Is there a way to describe how "hard" or "complex" finding all models is compared to finding a single model?

The worst-case complexity of finding all models of a SAT formula over $n$ variables is roughly $\Theta(2^n)$.  (For instance, consider a formula where all assignments satisfy the assignment; then there are $2^n$ satisfying assignments, so just listing all satisfying assignments takes $\Omega(2^n)$ time.)

Nonetheless, this number probably isn't very useful in practice.  In practice, the running time to find all models depends heavily on the formula and on the number of models.  Standard methods for worst-case complexity don't offer a good way to summarize the time to do this, as the running time practice varies heavily.

So, for your paper, I wouldn't place much stock on this complexity figure.  I just don't think it is very illuminating.


Deletion in a Binary search Tree The teacher explained to us this algorithm for deleting a node in a binary search tree, but I can't understand how it works when the node to be deleted has only one child (I already know how it works theoretically).

Algorithm:

abc_delete(T, z) // z is the node that must be eliminated
{
        if((z.left == NULL) && (z.right == NULL))
                y = z;
        else
                y = abr_successor(z);

        if(y.left != NULL)
                    x = y.left;
        else
                    x = y.right;

        if(x != NULL)
                x.p = y.p;

        if(y.p == NULL)
                T.root = x;
        else
        {
                if(y == (y.p).left)
                        (y.p).left = x;
                else
                        (y.p).right = x;
        }

        if(y != z)
                z.key = y.key;
        return y;
}

abr_successor(x)
{
        if(x == NULL)
                return NULL;
        if(x.right != NULL)
                return abr_min(x.right)
        y = x.p;
        while(y != NULL && x == y.right)
        {
                x = y;
                y = y.p;
        }
        return y;
}

For example, I want to delete the node number $7$:

But, shouldn't the end result be this?

You choice is certainly correct.

However, there is nothing wrong with your teacher's code, either. Here is an excerpt from CLRS.

  The operations of insertion and deletion cause the dynamic set represented by a binary search tree to change. The data structure must be modified to reflect this change, but in such a way that the binary-search-tree property continues to hold.

We certainly prefer the operation be made in the easiest way or the fastest way. However, there is no requirement the modification must be made in the easiest way or even in any easy way. Nor does it require that the modification be made in the fastest way or even in any fast way. All it requires that the operation of deletion should produce another binary search tree that has all nodes from the given binary search tree without that specific node (and no more nodes).  How those remaining nodes form a binary-search-tree is completely free of restraints.

Your teacher's code, on the other hand, is probably the shortest clear code that does the job. The more I study it, the more ingenuity I find.


Lower bounding the minimum equivalent graph The transitive reduction $G^t = (V,E^t)$ of a graph $G=(V,E)$ is the smallest graph with the same reachability as $G$ with the property $E^t \subseteq V \times V$.

The minimum equivalent graph $G' = (V,E')$ is the smallest graph with the same reachability as $G$ with the property $E' \subseteq E$.

Consider the case when $G$ is strongly connected.

The transitive reduction is formed by an arbitrary Hamiltonian cycle, so $|E^t| \equiv |V|$ and so we must have $|E'| \geq |V|$.  We want to find a polynomial time algorithm which finds a tighter lower bound than $|V|$ for $|E'|$. I'm wondering if this is possible at all, assuming $P \neq NP$.

If $|E'|>|V|$, then $G$ can not contain a Hamiltonian cycle . So if we can find a tighter bound in polynomial time, then we have determined the existence of a Hamiltonian cycle in polynomial time.

I think this means that efficiently lower bounding this problem is a wild goose chase. The best bound we can consistently hope for is $|V|$.

Is this a too pessimistic interpretation?

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


How do you rank the strings represented by a regular expression? This question is about the use of 'ranking' of regular languages in applications such as format preserving encryption.

I understand format preserving encryption but I don't understand how regular expressions can be used to get an integer that is the input of an encryption algorithm.

Referring to this video https://youtu.be/MT5ketZ-jLw?t=24m44s at time stamp 24:44

According to the process described - In order to encrypt a string  to a ciphertext of some agreed upon format, you need to rank all the possible strings it can be - then using your FPE function encrypt the integer that represents the input plain text to an integer in the same set - unrank the output integer to a ciphertext.

I don't understand what is being ranked?  Are they actually obtaining all possible string representations of the regular expression and ranking those?  Or are they ranking something else?  Where does the DFA come to play - because I can see a brute force way you can do this without bothering with the DFA - or even regular expressions to define the format.

EDIT:

I have already most of the paper that use ranking in regular languages for encryption such as these ones

Mihir Bellare, Thomas Ristenpart, Phillip Rogaway, and Till Stegers
Selected Areas in Cryptography, pages 295-312. Springer-Verlag, 2009 (online, see sec 5 p 10 "FPE for arbitrary RLs")
Daniel Luchaup, Kevin P. Dyer, Somesh Jha, Thomas Ristenpart and Thomas Shrimpton To appear in the proceedings of USENIX Security 2014

Anyway I'm just looking for a 'laymans' explanation of how this works as I cannot find any working examples online.  This would be useful to understand the overall procedure.  All examples I have found regarding regular expressions involve creating the DFA, and most of them end there.  What happens next?

The closest I could find was this post which I think is asking the same thing

https://cstheory.stackexchange.com/questions/18589/algorithm-for-ranking-members-of-a-regular-language

Suppose you want to encode an element of $\binom{[n]}{k}$, that is, a subset of $\{1,\ldots,n\}$ of size $k$. There are $\binom{n}{k}$ such subsets. FPE functions know how to handle encoding and decoding of integers in the range $\{1,\ldots,M\}$, for an $M$ of your choice. To use such an FPE function in your case you will have to translate an element of $\binom{[n]}{k}$ to an integer in $\{1,\ldots,M\}$ for $M = \binom{n}{k}$ (ranking) and back (unranking), efficiently.

How do you efficiently rank and unrank elements of a domain like $\binom{[n]}{k}$? For which domains is it possible? The video describes one scenario where this is possible, and one general algorithm for handling this scenario. If your scenario is different then you might still be able to rank and unrank efficiently, but you will have to use a different approach.

The scenario described by the video (which I haven't watched) is probably that of languages accepted by a DFA with a small number of states. Such a language can be ranked and unranked efficiently, and the algorithms use the DFA which accepts the language. This is how the DFA comes in – it is used by the ranking and unranking algorithms. Hopefully these algorithms are described in the video, but otherwise you can ask another question here.


Is there a way to compute time without system clock I was thinking about any method where we can use RAM I/O speed, to calculate time, let's say for example:
RAM transfer rate is 1000 MB/s, so when it's half full (about 500 M Bytes written), by dividing 500 by 1000 we get the time which is epoch + 0.5 seconds
so all in all we have three routines:

one for writing data (zeros for example) into RAM
another one for checking when a specific size is full
and the third for calculating time

  Note: Sorry if it sounds stupid, because this is not my study field,

You could try to measure time from RAM transfer rates. You'd need to know the precise clock ratio between the RAM and the CPU. There would have to be a precise clock ratio; I don't think this is the case on typical PC architectures as the RAM and the CPU have their own clock and I'm not sure the RAM peak transfer rate is a constant.

You'd need to block all other sources of interrupts, because if the CPU is responding to some other interrupt, it may notice too late that the RAM is ready, so it would tend to drift.

The nail in the coffin is that while the CPU is waiting for the RAM, it isn't doing anything else. The same objection goes for anything that requires the CPU to perform computations to obtain the time — a CPU that does nothing but measure the time has no time left to do useful things.


Why do functions containing `await` need to be `async`? From what I understand, async/await enables to avoid the "callback pyramid of doom".
Let's say that I have funcA(), funcB() and funcC() that are async functions, now if I do something like that:

func someFunction() -> T {
let myValueA = await funcA()
let myValueB = await funcB()
let myValueC = await funcC()
return doSomething(myValueA, myValueB, myValueC)
}

Why do some languages (for instance JavaScript) require you to annotate your function with async ?
What would be the issue issue if the function wasn't asynchronous? I mean, since the function already contains awaits, can't it be already considered as a non blocking function ?

Thank you

The async annotation changes the way the body of the function is interpreted. Now you can clearly infer that if the body contains await, it must be async, but there are a couple of reasons why it makes sense to require an annotation.

The primary reason is, frankly, likely clarity. C# popularized this syntax and is a language that emphasizes declaring intent. My understanding (from vague recollections of blog posts) is that the C# designers view the fact that they didn't do a similar thing for generator syntax (i.e. yield) as a mistake or at least unpleasant compromise. Note that in JavaScript you do need to indicate a function is a "generator function" in much the same way as async. At any rate, both async/await and yield lead to dramatically different semantics, and you probably want to be clear that that is intended and understood. (A minor factor for C# was to make the await keyword contextual to avoid backwards compatibility issues.)

As a more technical reason, async and JavaScript's function* change the behavior of a function even if you don't use await/yield. In C#, an async method with no await will run synchronously, but it will still package up the result in a Task object. Similarly, in JavaScript, a generator function with no yield still returns an empty Iterable rather than undefined. If the async/function* aspect was inferred from usage of await/yield, then in these cases you would need to explicitly create a Task or Iterable. This isn't so bad in C# where the type system will require this, but in JavaScript there's a much greater chance for uncaught errors. Regardless, it's also bad for exploration since commenting out a line of code might dramatically change the behavior and type of the function.


Dynamic Programming, Binary Tree: How to factor in depth to recursion? I have the following problem.

I have a set of elements $x_0,\ldots,x_n$ which must retain their order inside the binary tree: if, given $x_i, x_j, i < j$, $x_i$ must be to the left of $x_j$ if $x_j$ is the root and $x_i$ is part of $x_j$'s subtree.

I also have a set of frequencies $f_0,\ldots,f_n$.  I need to build a binary tree such that the cost of accessing the elements, defined as $depth$*$f$ is minimized.

I figured this was just like chain matrix multiply, so I wrote that the dynamic table was:

T(i,j) = minimum cost tree between i and j

And I wrote the following recurrence:

$$
T(i,j) = min \lbrace T(i,k) + T(k,j)\rbrace, i \le k < j
$$

However, I can't figure out if depth is being factored in here--it appears (to me) that it isn't.

How do I construct this recurrence??

Turns out that I had a misunderstanding of the scope of dynamic programming.  As I understood it, I was "not allowed" to capture other things outside the recursion besides elementary operations.

So, I just have to literally calculate the sum of values lower than the root on either side to factor in the depth:

$$
T(i,j) = \sum_{i\leq l < j}f_l + min\lbrace + T(i,k-1) + T(k+1,j)\rbrace: i<k<j
$$

Where I can just calculate the sum outside of the recursion.


Measuring the information of a document? I'd like to measure how much information a document $D$ contains.

Clearly, the New York Times published yesterday contains more information than my diary wrote on the same day. But, I do not know how to quantify those differences.

I think there are at least two alternatives. Those are the information entropy, and tf-idf.

In general, the information entropy $H$ is employed to measure the information.
Basically the information entropy seems OK to measure document information.

For instance, let's compare two documents: $D_1 = \text{"Tom loves Mary. Tom loves Mary"}$; $D_2 = \text{"Tom loves Mary. Jack loves Jane."}$. In this case, clearly the information of $D_1$ is less than $D_2$ and $H(D_1) < H(D_2)$ holds.

The tf-idf is the second option. With tf-idf, more rare words are regarded as more informative words. This also sounds valid. In fact, tf-idf is used to measure the importance of documents in automatic document summarization.

Then, my questions are

Are there standard way to measure the information of a document?
Are The information entropy and tf-idf used for this purpose? Why or why not?

Update on Aug 17

Thanks to several kind comments, I came to clarify what my question really was. I'd like to know formal (mathematical) definition of what is information or informative in the "NYT-and-diary comparison".

Intuitively, the New York Times is more helpful than my diary in order to get valuable information. In fact, many people pay $3 for NYT, and most people do not for my diary.

However, formally (mathematically), I can not explain why NYT is more informative.

Hence, my question is equivalent to how to formally define information or informative in the NYT-diary case. Then, the questions in the comments like "what do you mean by information" is totally what I'd like to know :)

Assuming that your data comes from a Markovian source, you can estimate the entropy of the source using an optimal compression algorithm such as Lempel–Ziv, whose theoretical version (without limiting the table size) is known to asymptotically converge to the entropy. That is, if the entropy of the source (suitable defined) is $H$, then the expected compressed size of $n$ samples is roughly $nH$. Definitions and proofs appear in Cover and Thomas' Elements of Information Theory, Chapter 13 of the 2nd edition.

The entropy of the source differs from your example. It doesn't make sense to calculate the entropy of a single output – entropy is a function of a random variable (or a distribution), and the entropy of a constant random variable is zero. Instead, we consider your source text as a random variable, and our goal is to estimate the entropy of that random variable from a single sample.

If the source has no memory – that is, the individual symbols of the text are independent – then a good estimate of the entropy of the source is the empirical single-character entropy, which is the function that appears in your question. But general sources – such as a random text – do have memory: if you just sample a random list of characters according to their distribution in the English language, you will get gibberish (a nice example of this appears in Shannon's 1948 paper, p. 7). This is why we need to use a more sophisticated estimator, such as the Lempel–Ziv algorithm.

In practice, you can approximate the information content by just compressing the text using an off-the-shelf program.


How to detect number of specific object in an image and it's diameter(size)? I have two images of IRON RODS (i.e only two images) and I want to detect how many rods are there in each image and get the diameter of each rod in a image?

I don't know where to start as there are lot of articles regarding object detection and it's hard to find one for my use-case.

If you can help me with a abstract view on how to model such requirement? Please point me a right direction.

Doubt:

1) How can I train with two images and then how to count numbers of rods are there in each image and retrieve it's diameter?

Well to answer your last question, you cannot train with the images that you want to test your algorithm with, that is a paradox...

You will need more than just two images if you want to build a robust model that can detect each rod AND predict their diameter. Those are two different problems, and you might want to split your model in two branches: one to detect each rod, the other to predict its diameter as a regression problem.

If you can obtain a larger dataset with ground truth, then you can proceed to train your model. I would tend to say that using an object detector CNN would be overkill, but if you need to predict the diameter of each rod in the image, it might be necessary. So maybe look into TinyYOLO for the detection part, and then you could use the predict bounding box of each rod in the image for a small perceptron to infer the diameter.


Load balancing. Why not use priority queues? I have recently learned about various randomized algorithms for load balancing. The model is always that there are $m$ balls and $n$ bins and the balls arrive one at a time. The task is to minimize the maximum load of any bin.  However there is something I don't understand.

Why not just keep a priority queue of the loads of the bins and allocate any new ball to the bin with the lowest current load?  This seems to give you the optimal load without any complications.

You are correct that using a priority queue is a good idea.  It doesn't give an optimal answer though.  (Assuming that what you are trying to optimize is the time that the last processor finishes executing the last job.)  This scheduling problem is NP-complete, and the priority queue based method gives an answer that is within a factor of 2 of optimal.  See, for example, http://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/11approx-alg.pdf.  The wikipedia page on Job Shop Scheduling also gives some information.


Is there a continuous hash? Questions:
Can there be a (cryptographically secure) hash that preserves the information topology of $\{0,1\}^{*}$?
Can we add an efficiently computable closeness predicate which given $h_k(x)$ and $h_k(y)$ (or $y$ itself) tells us if $y$ is very close to $x$ (e.g. the Levenshtein distance or Hamming distance of $x$ and $y$ is less than a fixed constant $c$)?

Background:
By information topology on $\Sigma^*$ on I mean the topology space with points $\Sigma^*$ and with the base $\{x\Sigma^* : x \in \Sigma^* \}$.
A nice way to think about topology is considering open sets as properties of points which are affirmable/verifiable (i.e. if it is true, it can be verify/observe that it is true). With this in mind, closed sets are refutable properties.
A function $f:\Sigma^* \to \Sigma^*$ is continuous if the inverse image of opens sets are open. In our case this means that for all $y \in \Sigma^*$, there is $I \subseteq \Sigma^*$ such that
$$f^{-1}(y\Sigma^*) = \bigcup_{x\in I} x\Sigma^*. $$
A nice way to think about the information topology is looking at it as a tree of binary strings. Each subtree is a an base open set (and other open set can be obtained from taking a union of base open sets).
This is sometimes referred to as information topology of strings because each point in $\Sigma^*$ can be considered as a finite approximation to a binary string/sequence. $x$ approximates $y$ iff $x$ is an initial substring of $y$ ($x \sqsubseteq y$).  E.g. $0011\Sigma^*$ is an approximation to $00110^*$ because $0011 \subseteq 00110^*$.
And for continuity, if we take a sequence $\{x_i\}_i$ which approximate and converge to binary sequence $y$ (think of $y$ as an infinite branch in the tree and $x_i$s as points on that branch) then $\{f(x_i)\}$ converge to $f(y)$, $$f(y) = \bigsqcup_i f(x_i).$$

For modern cryptographic hash functions, no, there is no efficiently computable closeness predicate, assuming the distribution on $x$ has sufficient entropy.  The intuition is that these hash functions are designed to "have no structure", so they don't admit anything like this.

In technical terms, modern cryptographic hash functions behave "like a random oracle".  For a random oracle, there is no such closeness predicate: the best you can do appears to be to invert the hash function and then enumerate all close strings and hash them.  As a result, there's no way to do this for modern cryptographic hash functions.

Heuristically, it does possible to design a custom hash function which does admit an efficiently closeness predicate, and which is (roughly) "as secure as possible" given this fact.  Let's assume the strings we are going to hash are of fixed length.  Suppose we have a good error-correcting code, and let $D$ be the decoding algorithm (so it maps a bit-string to a nearby codeword, if it can).

To get a simple but imperfect scheme, imagine defining $h(x) = \text{SHA256}(D(x))$.  If $x,y$ are two random strings that are sufficiently close, then there is a decent chance that $h(x)=h(y)$.  If $x,y$ are not close, then $h(x)$ will look nothing like $h(y)$, and we'll get no information beyond the fact that $x,y$ are not close.  This is simple.  However, it is also imperfect.  There are many pairs $x,y$ that are close but where we can't detect this fact from $h(x),h(y)$ (e.g., because the decoding function $D$ fails).

Heuristically, it looks possible to improve this construction.  At design time, choose random bit-strings $r_1,\dots,r_k$.  Now, define the following hash function:

$$h(x) = (\text{SHA256}(D(x \oplus r_1), \dots, \text{SHA256}(D(x \oplus r_k)).$$

Now if $x,y$ are sufficiently close, it is likely that there exists $i$ such that $D(x \oplus r_i) = D(y \oplus r_i)$, and thus $h(x)_i = h(y)_i$.  This immediately suggests a closeness predicate: if $h(x)$ matches $h(y)$ in any of its $k$ components, then $x,y$ are close; otherwise, infer that they are not close.

If you additionally want collision resistance, a simple construction is the following: let $h_1(\cdot)$ be a hash function with a closeness predicate; then $h(x) = (h_1(x), \text{SHA256}(x))$ is collision-resistant (any collision for this is also a collision for SHA256) and has a closeness predicate (simply use the closeness predicate for $h_1$).  You can let $h_1(\cdot)$ be the hash function defined above.

This is all for Hamming distance.  Edit distance is probably significantly harder.

In coming up with the above construction, I was inspired by the following paper:

Ari Juels, Martin Wattenberg.  A Fuzzy Commitment Scheme.

Ari Juels, Madhi Sudhan.  A Fuzzy Vault Scheme.  Designs, Codes, and Cryptography 38(2): 237-257, 2006.

Incidentally: in cryptography, hash functions are unkeyed.  If you wanted a keyed thing, you might want to take a look at pseudorandom functions.


Is SAT-Problem with XOR and AND NP-complete Is this problem NP-complete?

I have many restrictions like this and want to find a feasible solution:

((a and b) xor (c and d)) = 1

with a,b,c,d are arbitrary literals. It looks similar to XOR-2SAT but has additional ANDs inside the clause.

Your question is likely answered by Schaefer's dichotomy theorem. In particular, if an instance of your problem is a conjunction of formulas, each one depending on a bounded number of variables, then according to the theorem your problem is either in P or NP-complete; and moreover there is a simple criterion to decide which case it is.


Is it possible to construct 3-dimensional microchips? In our daily computer, the microchips in it are 2-dimensional, but could it be possible to produce 3-dimensional ones, in some way similar to the brain structure?

Yes, it's possible to build 3-dimensional integrated circuits: we already know how to do that, and many chips already use 3D integration.

Building chips whose structure is similar to the brain structure is a different question.  Circuits on current chips (whether 2-dimensional or 3-dimensional) are very different from the structure of the brain.


Context-free grammar how to have unequal number of a's on either side of b I have been trying to create a CFG for the set
$\{w=a^iba^j \mid i \neq j\}$.

To my understanding, there are essentially 2 scenarios, one where there are more $a$s on the left side of $b$, and one where there are more $a$s on the right side of $b$.
So far I have come up with:
\begin{align}
S &= TbR \mid RbT \\
T &= aT \mid \varepsilon \\
R &= TaT
\end{align}
My intention is the have $R$ to always have more $a$s than $T$, however I don't think this is correct as $T$ can be greater than $R$ in this definition, as $R$ could take be just $a$ while $T$ is $aa$.

I need a bit of help defining 2 variables $T$ and $R$, where $R$ always has more $a$s than $T$.

Equal numbers of a’s on either side, then the middle is replaced by a+b or by ba+.


Does the Y combinator contradict the Curry-Howard correspondence? The Y combinator has the type $(a \rightarrow a) \rightarrow a$. By the Curry-Howard Correspondence, because the type $(a \rightarrow a) \rightarrow a$ is inhabited, it must correspond to a true theorem. However $a \rightarrow a$ is always true, so it appears as if the Y combinator's type corresponds to the theorem $a$, which is not always true. How can this be?

The original Curry-Howard correspondence is an isomorphism between intuitionistic propositional logic and the simply-typed lambda calculus.

There are, of course, other Curry-Howard-like isomorphisms; Phil Wadler famously pointed out that the double-barrelled name "Curry-Howard" predicts other double-barrelled names like "Hindley-Milner" and "Girard-Reynolds". It would be funny if "Martin-Löf" was one of them, but it isn't. But I digress.

The Y combinator does not contradict this, for one key reason: it is not expressible in the simply-typed lambda calculus.

In fact, that was the whole point. Haskell Curry discovered the fixpoint combinator in the untyped lambda calculus, and used it to prove that the untyped lambda calculus is not a sound deduction system.

Interestingly, the type of Y corresponds to a logical paradox which isn't as well-known as it should be, called Curry's paradox. Consider this sentence:

  If this sentence is true, then Santa Claus exists.

Suppose the sentence were true. Then, clearly, Santa Claus would exist. But this is precisely what the sentence says, so the sentence is true. Therefore, Santa Claus exists. QED