Question regarding the assumptions of the No-Free-Lunch-Theorem for Search

I think that I was indeed misunderstanding something. Any search algorithm that wants to evaluate any point $x \in \mathcal{X}$ through $f$ would implicitly add $(x,f(x))$ to the histogram $d$. For example, one could design a hill-climbing algorithm in the following way:

for a solution $x'$, visit all neighbours $x_1,\dots,x_n$
afterwards, $(x',f(x')), (x_1,f(x_1)),\dots,(x_n,f(x_n))$ are all part of the histogram $d$
choose the best neighbour from $x_1,\dots,x_n$ by computing $a(d) = \arg\min_{x=x_1,\dots,x_n} f(x)$, which is independent of $f$ since $f(x_1),\dots,f(x_n)$ are already known
repeat


Difference between a minimal DFA and a canonical DFA

Yes. The canonical DFA for a regular language $L$ is the automaton that is based on the equivalence classes of the relation defined by $L$, i.e., they cannot be "distinguished" in $L$ by extending them with the same suffix.

It is part of the Myhill-Nerode results that that yields a minimal DFA for $L$.


What does the notation $ [ i \neq k ] $ mean?

It  is used like a boolean where $[i \neq k] = 1$ if $i \neq k$ and $0$ otherwise. Notice that $[i \neq k]$ is equivalent to $i < k$ or $i > k$ for numbers, which is the right part of the equation you wrote.
It is called Iverson bracket and in general $[statement] = 1$ if $statement$ is true and $0$ otherwise.


Understanding addition overflows when performing full, signed multiplication of two 64-bit numbers

Your explanations are a bit incorrect. What line 10 does is to add the high 64-bit word of $x_l y_l$ (%rdx after line 9) to $2^{64} (x_h y_l + x_l y_h)$. The low 64-bit word has been computed in line 9 and is in %rax.

Now, all the overflows that have been ignored will affect bit 128 only, i.e. the obtained result can differ from the correct result only by a multiple of $2^{128}$. But since one is interested in the result modulo $2^{128}$, such overflows do not matter.


Can the turing machine accept these type of languages in O(n)? or better? $L = \{a^n b^n c^n ... d^n | n > 0\}$

Yes a TM with multiple head for example can easily do this. for $a^nb^n$ you can have two heads one at the first occurence of A's and other at the first occurence of B. Then at each iteration you can cross each off. If both see blank accept. If A head does not see A or B head does not see a B reject. Else cross both off with some special character.

Clearly this takes one linear pass in time O(N). Now for the lower bound. It is not possible to do with less than O(N). If you use N number of tapes by definition then it is $\Omega{(N)}$. If you use K number of tapes then it is $K \times (N/K)$ which is still O(N). The reason for this lower bound is that you have check each character since any one character can break the rule of this language. Thus we get a linear lower bound.


Use the following recursive procedure to construct $M'$ from $M$:

Run $M'$ on all non-trivial prefixes and suffixes of the input (if any), and ignore the results.
Run $M$ on the entire input, and output the result.

If $M$ always terminates, so does $M'$. The first step guarantees your first condition. The second condition is virtually automatic.


This is called the Assignment Problem, or equivalently Weighted Bipartite Matching.
You need a way to compute a numeric distance or cost between any point in C and any point in T (it sounds like you already have this). Create a graph with a vertex for each point in C, and a vertex for each point in T, and an edge between every pair of vertices from different sets (i.e., one from C, one from T) having weight equal to the cost between them, and run one of the several algorithms described on that page, e.g., the Hungarian algorithm, which can be implemented to run in $O(n^3)$ time though the description on that page is only $O(n^4)$. As this might be tricky to implement, I would suggest instead setting up a linear program and using a freely available LP solver to solve it.


Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached

Considering the strongly connected component is a good start if graph $G$ may have cycles. However, as implied by Pål GD, every vertex is a strongly connected component of a graph without cycles. We need to do more work to find the minimum set of vertices from which all vertices can be reached.

Here is the outline of an algorithm that does the job.

Find one root $r$ of $G$ by repeatedly going to the ancestor of a node. Mark $r$ as an wanted vertex.
Remove all vertices reachable from $r$.
Go to step 1 unless there is no more vertex.
return all vertices that are marked as wanted.

Exercise. Given a directed graph (that may have cycles), describe an algorithm that finds a minimum set of vertices from which all vertices can be reached. (Hint, strongly connected components are useful now. Try reducing the problem to the current question.)


checking configuration history of Turing machine using PDA

PDAs are strictly weaker than TMs. For instance, PDAs always halt after precisely $|w|$ steps, but there are algorithms (aka TM) for questions that take more steps than that.
sorting an array for example, would take definitely more than $\Omega(|w|log(|w|))$ which is larger than $|w|$ at some point.
It cannot simulate running a machine on a word as it simply takes more time! Checking configuration history takes less time because it's length is proportional to the running time of $M$ on $w$.


The only world in which NP-complete problems (e.g. 3sat, 3colorability, traveling salesman)  are solvable in polynomial time is Algorithmica, i.e. $P=NP$.

The rest of them refer to various conjectures that might hold within $P\neq NP$, for example $NP$ problems are hard/easy on average, or one way functions do/don't exist.


Dependent Type Theory Implementation of a Graph

So, there are two different things you are talking about.

The definition of a graph
The encoding of a graph

A Graph is always defined as a set of vertices and edges. This tells us what vertices are in the graph, and for any pair of vertices, whether there is an edge between them.

However, this definition is purely mathematical. A set isn't a "thing" that you can store in memory. So we need an encoding of a graph, so that the abstract mathematical set operations can be mapped onto concrete algorithmic operations.

Once you're talking about encoding, there are many different ways to implement a graph, all of which will give you something that is (in a sense) equivalent to the mathematical definition. But, there are practical trade-offs with different encodings:

What operations are fast?
What operations are easy to implement?
How much memory does the graph take?
How easy is it to use the graph in different settings.

In JavaScript, all types are dynamic, so it's easy to just say "A graph is a list of nodes and a list of edges", because the language doesn't ever require that you formally specify what a node or an edge looks like. It doesn't care, and if you make a mistake, it will just crash at runtime.

Notice that your JavaScript version of a graph doesn't actually specify how nodes and edges are represented. What does an edge look like? If you insert an edge as a 2-element array, but try to access it as an object, you will have a runtime error.

Haskell and Coq's definitions try to solve this issue with type safety. They have a formal definition of the different forms a Graph can take, so that you always know at compile-time which operations on it are valid or not.

Let's look at the versions and their tradeoffs:

data Graph a = Empty | Vertex a | Overlay (Graph a) (Graph a) | Connect (Graph a) (Graph a)

This version is interesting, because it is an inductive definition of a graph, that allows you to implement graph operations easily as recursive functions. So you know that a graph is always empty, a single vertex, the overlay of two graphs, or the connection of two graphs, and you can safely pattern match on these 4 cases.

class Graph g where
  type Vertex g
  empty   :: g
  vertex  :: Vertex g -> g
  overlay :: g -> g -> g
  connect :: g -> g -> g

This isn't actually an implementation of a graph, but instead is an interface for a graph. It says what operations are available on a graph, but not how they're implemented. Users could provide their own Graph instances, and can write code that is generic over which Graph implementation is used. This helps bring back some of the flexibility that we had in JavaScript but lost when adding types.

type Graph = Table [Vertex]
type Table a = Array Vertex a

This is a classic "Adjacency List" implementation of a graph: we store the outgoing edges for each vertex. It is space efficient, and allows for quick BFS and DFS, but is slower for checking the existence of an edge, or deleting an edge.

Structure Graph := {
  V :> nat ; (* The number of vertices. So the vertices are numbers 0, 1, ..., V-1. *)
  E :> nat -> nat -> Prop ; (* The edge relation *)
  E_decidable : forall x y : nat, ({E x y} + {~ E x y}) ;
  E_irreflexive : all x : V, ~ E x x ;
  E_symmetric : all x : V, all y : V, (E x y -> E y x)
}.

This is an interesting representation. First, it's similar to a typeclass, in that it's abstract: it works for any types $V$ and $E$ so long as they can be coerced into numbers and edge-lookup functions. This isn't saying "this is how you can represent a graph", it's saying "here's an interface for graph representations".

Second, because we are in a dependently typed setting, we want to encode some properties of the graph, so that we can't create ill-formed graphs. We can then use these properties when proving things about graphs later on. Here, there are three properties that we require all graphs to have:

The encoding must be irreflexive i.e. there are no self edges
The encoding must be symmetric i.e. any time there's an edge u->v, there's also an edge v->u
The edge relation is decidable i.e. we can take

The third condition is important because Coq is a total language. It doesn't allow for any non-terminating code, so we need to prove that our edge lookup actually halts.

Finally, there's the Coq graph definition:

Inductive Graph : V_set -> A_set -> Set :=
  | G_empty : Graph V_empty A_empty
  | G_vertex :
      forall (v : V_set) (a : A_set) (d : Graph v a) (x : Vertex),
      ~ v x -> Graph (V_union (V_single x) v) a
  | G_edge :
      forall (v : V_set) (a : A_set) (d : Graph v a) (x y : Vertex),
      v x ->
      v y ->
      x <> y ->
      ~ a (A_ends x y) -> ~ a (A_ends y x) -> Graph v (A_union (E_set x y) a)
  | G_eq :
      forall (v v' : V_set) (a a' : A_set),
      v = v' -> a = a' -> Graph v a -> Graph v' a'.

This version provides a concrete implementation, that (I think) fulfills the interface you gave. In particular, it says we can build a graph in 4 ways:

A graph can be empty
We can add a vertex to a graph
We can add an edge to a graph
We can map an equality over a graph

The beauty of this implementation is that the vertex and edge sets are stored at the type level. This is the magic of dependent types: the type of the graph depends on the values it contains. So, when adding an edge, the type system ensures that we can't possibly add an edge between two vertices that aren't in our vertex sets.

Secondly, this implementation is inductive, similar to the Haskell one, so writing proofs about this graph by induction will be easy.


What kind of model is used by 20 Questions?

You just play once with it, observe it, and you have the model. Try
something non obvious, or simply cheat with answers.

The game: you think of something, and 20Q asks questions to find what
it is.

They just collect the answers from the players.  They have a
collection of questions that are supposed to discriminate solutions.
They ask questions to users, who chooses among 7 possible answers. Recall that with just 20 yes/no answers, you can discriminate 1 million different objects. And their questions have more answers that just two.
The combinatorics of the answers will identify the right "something"to
be guessed in the available collection. If the thing they are supposed
to identify has not appeared before, they do not find it, recognize
that they lost, ans ask what it is.  Then it goes into the database,
with all the user's answers to identify it the next time.

So they fail, but not twice on the same "something/someone/somewhere"
to be guessed.  Unless users give wrong answers to questions (the
first time, or afterwards ...?).

It is probably slightly subtler, but I doubt it has much artificial
intelligence, neural network or otherwise.  A most elementary and
simplistic form of machine learning, if one dares use the expression
for it.

This is all pure guesswork from what I observed. No idea where you
could read about it. Not sure there is anything worth reading anyway.


undecidable problem and its negation is undecidable

Consider the following language:

$$L_2 = \{(M_1,x_1,M_2,x_2) : \text{$M_1$ halts on input $x_1$ and $M_2$ doesn't halt on input $x_2$}\}.$$

$L_2$ is undecidable and not semi-decidable, and same is true of its complement.  Why?  The intuition is "$M_2$ doesn't halt on input $x_2$" isn't semi-decidable, so $L_2$ is not semi-decidable; and when you look at the complement of $L_2$, the same thing happens for $M_1$.  This can be formalized more carefully using reductions.

More generally, if $L$ is a language that is undecidable and not semi-decidable, then

$$L' = \{(x,y) : x \in L, y \notin L\}$$

meets your requirements: $L'$ is undecidable and not semi-decidable, and the same is true of the complement of $L'$.


Improvement Heuristics for Asymmetric TSP

I have the exact same doubt now, so, I found your question because I did a heavy research about this theme and didn't find any good direction yet.
As you, I'm currently working on TSP and VRP variations and solving it by the Ant's Colony Optimization Method.

I have an instance of 16 cities to be visited, one origin and one destination, I optimized it using pure ant's algorithms and the best result I got was 557 km, by comparation the nearest neighboor algorithm found 586 km as a result, however, I notice that the ant's algorithms aren't precise, sometimes it returns a very bad result, better than the nearest neighboor though. But I wasn't satified with this drawback, and I started to read about heuristics (daemons actions) to be coupled with the ant's algorithms, then It is very interesting that all of them assume that we are working with a symmetric matrix, but real problems are hardly symmetric.

I first tried to apply the 2-opt heuristic, because I read that it is fast and give a good result, so it suits for a real application that an user waits to get the answer as fast as possible and as good as possible. But latter I saw that the step of 2-opt which reverses a path when exchange edges is guaranteed only when working with symmetric matrices...

Well, After all, I applied a very simple heuristic, that I don't know the name yet, but I saw some comments that it is not a good solution (because doesn't solve the crossed arcs problem and may create more of them), even though, it helps me to provide better solutions and also more precise, as an example, the instance I told about above, it gives the result of 554 km almost all the time.

The heuristic I applied does this job:
After the ACO build a solution, I refine it by exchange cities (in other words, exchange vertex or nodes), if it improves the solution, I save this new solution and continue the process of exchanging cities, using the new solution constructed until I reach the solution's vector length.

For example, if I have the following path as a solution given by the ACO:

A -> B -> C -> D -> E -> F

the heuristic moves B ahead in the path, for example:

A - > C -> B...

then:

A -> D -> C -> B -> E -> F

if it finds a better solution, for example, let's suppose the above solution is an improvement, then it continues moving the city in the second position in the solution vector:

A - > E -> C -> B-> D-> F

Then, it starts the same procedure to the third position city...

I'd like to add that the solution which updates the pheromone matrix is the solution built by the ACO and improved by this heuristic.

As I experienced, the ACO does a pretty good job creating solutions with very few crossed arcs, because this the heuristic applied is working fine, and as we are working with asymmetric matrix I think that it is possible to crossed arcs being better paths than paths without any crossed arc... But It is just my feeling, actually, I analyzed the solutions above only by the value of route's length in kilometer, but I did not plot them yet to see how they look like.

Well, I hope to help you with these informations, and if you have find any nice heuristic to couple with the ACO as a daemon action, keep me posted!


Constrained Smallest Enclosing Ball Problem

I guess one simple approach would be to use any known Smallest Ball algorithm to determine the center of the optimal ball. Then you use kNN-queries to find the closest neighbour, which is likely the required point.
However, you would need to show that the closest neighbour really is necessarily the best point. Maybe you need to actually check a number of candidates within a to-be-determined distance of the virtual center point.

Also, for a practical solution, I wouldn't use a kd-tree. R-Tree (or R*tree/R+tree/X-tree) behave better, so does the PH-Tree (a kind of quadtree).


How/why is switch made from equation to inequality for certificate of optimality for dual problem in linear programming?

If the required conditions are met then you have
$$ x_1 + 6x_2 \leq (y_1+y_3)x_1 + (y_2+y_3)x_2 = y_1 x_1 + y_2 x_2 + y_3(x_1 + x_2) \leq 200y_1 + 300y_2 + 400y_3$$
By looking at the leftmost and rightmost expressions you get the inequality you want.


How does the OS Scheduler give/take control of HW?

Your idea of interrupts is correct, but not how it works. The scheduler program will not raise an interrupt.

Let's take the round robin algorithm you have mentioned. A process is going to run for a period of time and then is supposed to relinquish the CPU. How does this work? Interrupt. It is the operating system that raises this interrupt using what is called an interval timer. The interval timer is programmable and is set to the time slice value of the round robin algorithm.

Once the interrupt is raised, the time quantum for the current process expires and the control is given to the scheduler process.


What is the optimal way to solve the following optimization problem

Yes, there is a simple way to compute $F$.

Proposition: $F(a_1,a_2\ldots a_n)=\gcd (a_1,a_2\ldots a_n)$, where $\gcd$ is the greatest common divisor.

Proof: I will leave it as an exercise. Hint, the replacement of $a_j$ by $a_j-a_i$ whenever $a_i<a_j$ is very powerful.

Here is a simple and efficient algorithm to compute $F(a_1,a_2\ldots a_n)$.

Let $r = a_1$.
Iterate $i$ through $2,3, \cdots, n$, setting $r$ to $\gcd(a_i, r)$. Here $\gcd(a_i,r)$ can be computed by any of your favorite GCD algorithms such as Euclidean algorithm or binary GCD algorithm.
return $r$.


Difference between data duplication and data redundancy

(1) Duplication

When you create tables in a database, you may want to create duplication:

CREATE TABLE user (name TEXT, id INTEGER);
CREATE TABLE friends (name TEXT, friend_of_id INTEGER);

Here you would duplicate the name of the user in both tables. That way when you display the list of friends, you do not have to access the user table to read the name. This is a simple example, but it shows what we call data duplication.

Duplication means YOU are responsible for also updating the name parameter in the friends table, when you change the name in the user table. If you do not do that consistently, then your data becomes inconsistent and users start seeing "strange things happening."

(2) Redundancy

In case of redundancy, you do not yourself have two copies of any piece of data. The database can though. This is useful for safety. For example, you can place your database on two separate computers. If one computer goes down, the same data is available on the other computer.

Redundancy is definitively a copy, but the access to either version of the data is 1 to 1 exactly the same to you. The RDBM may choose one or the other based on different parameters such as how fast or whether the other computer network connection is down.

The RDBM manages the copies in very consistent ways, the same problem I just mentioned about user names. If the RDBM is asked to update the user name, it has to update all the versions (all copies). The good thing is it does not have to do it at the time you do the INSERT or UPDATE, it can delay the update on the copy computer. So... the implementers of the database do exactly the opposite of what they were told and make duplicates of the data! (which is probably the main source of confusion in this realm.)

You may want to read about Cassandra for fun things in that respect. Cassandra is the type of database used by Google which update data in a ring of computers with possibly heavy redundancy.

(3) Even More Duplication

Since you asked, I'll also let you know that RDBMs make use of what we call Indexes... And Indexes duplicate your data further. To continue with the user example, the name of the user could be used in an index. The Index would then look like this, for example:

Alexis
Henri
Margarette
Phyllis
...

When you do an UPDATE of the users table, the RDBM needs to also update its index and move the name to the new position, and all of that with maintaining consistency (SQL warrants that the data is always 100% consistent...)

So, renaming Alexis as Tristan would give a new index:

Henri
Margarette
Phyllis
Tristan
...

And here we see that the duplication is actually necessary. And if you see how you can handle that properly, without ever losing any existing data, you understand why duplication is difficult to deal with.


Why does removing all copies of a letter preserve regularity?

Given an NFA or a DFA (like in your proof, if you want), we replace each arc with letter $a$ by $\varepsilon$. We obtain an NFA for $P(a,L)$. So, $P(a,L)$ must be regular.

In details, each trace in the newly constructed NFA can be transformed back to $a$-full instance of $L$ .


The optimal way to reverse engineer a binary classification problem

Your problem is tackled in Vaishampayan, Query Matrices for Retrieving Binary Vectors Based on the Hamming Distance Oracle. Vaishampayan relates this problem to one considered in Lev and Yuster, On the size of dissociated bases, and the upshot (if I understand things correctly) is that a random test set of size $O(N/\log N)$ (for an appropriate hidden constant) would do if you don't care about carrying the decoding procedure efficiently. Vaishampayan describes a more structured solution using $o(N)$ tests which can be implemented efficiently.


Shortest traverse path in a matrix given the start point $(i,j)$

If either $m=1$ or $n=1$, the starting position will determine how many elements will need to be revisited - head to the nearest end and the back to the other. The following cases consider $m,n>1$.
If either $m$ or $n$ is even, there is a simple traverse starting from any element (and which will conclude on an adjacent element), without revisiting any element.
Consider a $2\times n$ matrix. Then there is a loop traverse that runs one way along one row and back along the other row:

Now for a $2k\times n$ matrix you can stack these loops and jump from loop to loop as required:

(there is no requirement to stagger the loop jumps - that is purely choice). The same idea applies if it is $n$ rather than $m$ that is even.
When $m$ and $n$ are both odd, you do not have a convenient loop path. If for your starting square, $i$ and $j$ are opposite parity - one odd, one even - you cannot avoid one revisit of a cell. A checkerboard colouring argument shows that easily. I believe that otherwise you can complete a path without a revisit, provided you avoiding leaving "dead end" elements until inevitable.


I have found a reduction from 3-SAT.

For every instance of variable $y$, I will put a new variable $y_i$ in its place. Suppose there were $K$ such instances then after replacing each instance of $y$, I will add clauses  $\bar y_1 \vee y_2, \bar y_2 \vee y_3, \ldots, \bar y_K \vee y_1$. This ensures that $y_1,\ldots,y_K$ will be assigned the same value.


If A is polynomial-time reducible to B and B is NP-Complete, can I say that A is NP-Complete as well?

You can indeed not guarantee that A is NP-complete.
Problem A: Given is a single number X ≥ 1. Is X equal to 1? Clearly in P, and in NP, but of course not NP-complete.
Problem B: Given n items of size $s_i$ ≥ 1, a bin size B ≥ 1, and an integer k ≥ 1, can the n items be put into k bins of size B? This one is NP complete.
A can be reduced to B in polynomial time: Just take 1 item of size X, let B = 1 and k = 1.


Solving "coin exchange" for coins of power values by greedy algorithm

For the coin values: 1, 3, 9, 27, suppose $16 = a_0 + 3a_1 + 9a_2 + 27a_3$ is the coin exchange with minimal number of coins. Note that $16\equiv a_0 \equiv 1(\operatorname{mod}3)$. If $a_0 \ge 3$, then we can subtract 3 from $a_0$ and add 1 to $a_1$ to obtain coin exchange with less number of coins. So, $a_0$ must be the remainder of 16 divided by 3. Hopefully, you can see where I am going.

All numbers or variables below are nonnegative integers. $(d_nd_{n-1}\cdots d_0)_a$ means the integer with those digits in base $a$, i.e., $(d_nd_{n-1}\cdots d_0)_a=\sum_{i=0}^{n}d_ia^i$ where $d_i\lt a $ for $i\le n$.

Here is the general theorem.

(Greedy algorithm works for power coins) Let $a\ge2$ and $n\ge0$. If $e_na^n+(e_{n-1}e_{n-2}\cdots e_0)_a=\sum_{i=0}^nc_ia^i$, then $ \sum_{i=0}^ne_i\le\sum_{i=0}^nc_i$.

Proof by mathematical induction on $n\ge0$.

The base case, when $n=0$ is trivial.

Suppose it is true for some $n\ge0$. Let us check the case of $n+1$. Suppose  $m=e_{n+1}a^{n+1}+(e_ne_{n-1}\cdots e_0)_a=\sum_{i=0}^{n+1}c_ia^i$. Note that $e_0$ is the remainder of $m$ divided by $a$.

If $c_{0}\ge a$, we can subtract $a$ from $c_0$ and add $1$ to $c_1$ to reduce sum $\sum_{i=0}^{n+1}c_i$. Without loss of generality we can assume $c_{0}\lt a$, i.e., $c_0$ is also the remainder of $m$ divided by $a$.

Now let $m'=(m-e_0)/a=(m-c_0)/a$. Then $m'=e_{n+1}a^{n}+(e_{n}e_{n-1}\cdots e_1)_a=\sum_{i=0}^{n}c_{i+1}a^i$. By induction hypothesis, we know $\sum_{i=0}^ne_{i+1}\le\sum_{i=0}^nc_{i+1}$. Adding $e_0=c_0$ to both sides, we obtained the wanted inequality for the case of $n+1$. Q.E.D.

What is left to be explained is that $\sum_{i=0}^ne_i$ does
come from the greedy algorithm. That easy task will be left for interested readers to verify.


Is the statement "Control unit controls overall operations of computer." true or false

Well true, sort of.

In simple terms: The control unit, regardless of how it is implemented, directs the activities of all of the other processor units.

However: It does so by decoding the instructions fetched from memory, the program.

So ultimately the program controls what gets done.


The statement of the corollary is extremely sloppy. Here is a correct statement and proof.

  Corollary 11.4

  Fix $c < 1$. Using universal hashing and collision resolution by chaining in an initially empty table with $m$ slots, it takes expected time $\Theta(N)$ to handle any sequence of $N$ Insert, Search, and Delete operations containing at most $cm$ Insert operations.

  Proof Since the number of insertions is at most $cm$, we have $n \leq cm$, where $n$ is the number of elements in the table, and so the load factor satisfies $\alpha \leq c$. The Insert and Delete operations take constant time and, by Theorem 11.3, the expected time for each Search operation is $O(1)$. By linearity of expectation, therefore, the expected time for the entire sequence of  $N$ operations is $O(N)$. Since each operation takes $\Omega(1)$ time, the $\Theta(N)$ bound follows. $\quad\blacksquare$

Roughly speaking, there are two problems with the book version:

The variable $n$ is used both for the number of elements in the table and for the number of operations.
The number of Insert operations should be $O(m)$, with a hidden constant bounded away from $1$.


The question of whether we can solve this problem without violating any rules is a set cover problem.

In particular, the universe is $U=\{1,2,\dots,30\}$, and each possible tuple $t_i$ that follows all the rules corresponds to a set $S_i \subseteq U$.  In this way, we get many sets $S_1,S_2,\dots,S_n$.  We want to know whether there is some 10 of these sets whose union is all of $U$.  That's the set cover problem.  There are well-known hardness results and approximation algorithms for the set cover problem.

Now let's introduce the opportunity to violate some of the rules.  Associate to each tuple $t_i$ a cost $c_i$.  If the tuple $t_i$ follows all the rules, there is no cost for using that tuple: $c_i=0$.  If the tuple $t_i$ violates some of the rules, we'll set $c_i$ to denote the cost of those violations (for instance, if each rule that is violated costs \$1, then $c_i$ can be set accordingly).  In this way we get a collection of sets $S_1,S_2,\dots,S_n$ with associated costs $c_1,c_2,\dots,c_n$ for each of them.

Now our goal is to find some 10 of those sets whose union is $U$, and where the sum of their costs is minimized.

This can be formulated as an integer linear program (ILP).  In particular, we'll introduce $n$ integer variables $x_i$; the intended meaning is that $x_i=1$ means that $S_i$ is one of the 10 sets that were selected, and $x_i=0$ means $S_i$ was not selected.  Now we want to minimize

$$\sum_i c_i x_i,$$

subject to the constraints

$$\sum_{j \in S_i} x_i \ge 1 \text{ for each $j=1,2,\dots,30$}$$

(where the sum is over all $i$ such that $j \in S_i$) and $0 \le x_i \le 1$.  Now you could throw any ILP solver at this problem and see what solution it turns up.


Assuming an infinite amount of computing resources, would the minmax algorithm always win in chess?

By definition, minmax chooses the move that results in the best possible outcome if the adversary plays optimally, but within the bounds of what the evaluation function takes into account. More precisely, minmax results in the best outcome that can be guaranteed no matter how the adversary plays, as long as the adversary's behavior is no worse than what the evaluation function predicts.

If minmax searches on the whole tree, then it never calls the evaluation function, and therefore it models the adversary perfectly. So in this case, minmax achieves the best guaranteed outcome that can be guaranteed against an arbitrary adversary. This is true regardless of the game.

For chess, there are three possible outcomes: win, draw, loss (from best to worst). We don't know what the best guaranteed outcome for each player is. But whatever it is, if you can run minmax on the whole tree, you'll get that outcome or better (the outcome can be better if the adversary plays suboptimally). Of course, this is only practical near the end of the game when there are few pieces remaining in play.


Recover permutation from prefix sums, using segment trees?

The segment tree is useful in this problem because you need to maintain an array of values where the supported operations are: 1) decrementing all elements in a range by the same amount and 2) querying a range for its (rightmost) minimum-value location.

In this problem, the values maintained in the array are the sums $s_i$, that have to be adjusted as described by the solution.

In your example, the subsequent contents of the array will be as follows:

0 1 1 1 10 # we query range (1, 5) and obtain position 1 (rightmost minimum)
∞ 1 1 1 10 # we remove the value at position 1, by setting it to INFINITY
∞ 0 0 0 9  # we subtract 1 from all values to its right (range (2, 5))
∞ 0 0 0 9  # we query range (1, 5) and obtain position 4 (rightmost minimum)
∞ 0 0 ∞ 9  # we remove the value at position 4
∞ 0 0 ∞ 7  # we subtract 2 from all values to its right (range (5, 5))
∞ 0 0 ∞ 7  # we query range (1, 5) and obtain position 3 (rightmost minimum)
∞ 0 ∞ ∞ 7  # we remove the value at position 3
∞ 0 ∞ ∞ 4  # we subtract 3 from all values to its right
∞ 0 ∞ ∞ 4  # we query range (1, 5) and obtain position 2 (rightmost minimum)
∞ ∞ ∞ ∞ 4  # we remove the value at position 2
∞ ∞ ∞ ∞ 0  # we subtract 4 from all values to its right
∞ ∞ ∞ ∞ 0  # we query range (1, 5) and obtain position 5 (rightmost minimum)
∞ ∞ ∞ ∞ ∞  # we remove the value at position 5 and stop.

Since the sequence of minimum positions was P = [1, 4, 3, 2, 5], it means that in the hidden permutation number 1 is at position 1, number 2 is at position 4, and so on. Hence the hidden permutation is [1, 4, 3, 2, 5], the inverse of P (although in this case it's the same).


The function $n^{1/\log \log n}$ tends to infinity, since
$$
n^{1/\log\log n} = e^{\log n/\log\log n},
$$
and $\log n/\log \log n \longrightarrow \infty$.


Data structure to query intersection of a line and a set of line segments

HERE is the solution I did in the homework but it still lose three points on:
(3 points) Construct the O(n^2) faces with proper intersection counts of each faces.


Runtime of various versions of binary search

Instead of cutting the interval in half, it's cut in to a piece 1/3 of the length and it's cut in to a piece 2/3 of the length. If you are lucky enough that the item you're searching for is in the left half, then you've done a better job than regular binary search. If you're unlucky and it ends up in the right half, then you do slightly worse than regular binary search.

What happens if the algorithm has "bad luck" twice in a row. The interval gets cut to 2/3rds and then to 2/3rds again, meaning it gets cut to 4/9ths which means it is now slightly shorter than 1/2. This means that in the worst case (bad luck every time) this version of binary search will take only 2x more steps than regular binary search.

On the other hand, if the algorithm is lucky the interval is cut to 1/3rd. If we look at regular binary search, after two steps the algorithm has been cut in half two times, meaning it has been cut to 1/4th - slightly shorter than a 1/3rd. So in the best case, the algorithm takes at least half as many steps as regular binary search.


You should not confuse median-of-median algorithm with median-of-3 trick.

The former is $O(n{\rm log}n)$ worst-case time.

Ans. to 1. The latter is still $O(n^2)$ worst-case time but faster in practice due to the low frequency of bad patterns seen in practice. This can be seen by the fact that randomized quicksort is $O(n{\rm log}n)$ expected time.

Ans. to 2. It is $O(n)$. The comparison work is $O(1)$ since there are only $3$ elements involving. After, determine the value of the median of three, you need to partition the array around this value. This takes $O(n)$ time.


Finding most likely tree over a semilattice

The maximum spanning tree is about summing weights; maximizing the probability is about multiplying weights.  To convert multiplication to sums, take the logarithm.

Hopefully that's enough for you to work out an algorithm for this task.


Show that if $SAT \in P/klog(n)$ then $SAT \in P$

You need to combine two ideas here:

There are only polynomially many possible advice strings.
If you can solve the decision version of SAT, then you can solve the search version of SAT.

There is a slight annoyance that you need the search-to-decision reduction to involve only constantly many different input lengths. Assuming for simplicity that you can perform everything using a single input length $n$, here is what you do: you go over all possible advices for length $n$, and for each one, either determine that the SAT instance is unsatisfiable, or attempt to find a satisfying assignment. If you find a satisfying assignment, then the SAT instance is satisfiable, otherwise it isn't.
I'll let you fill in the details.


Lower bound time complexity for obtaining an arbitrary entry in a hashtable

We usually assume that a reasonable proportion of entries in a hash table are used, or we would be wasting memory. If we know that a hash table is at least 20% full then we can just visit random locations until we find a used one , five or so in this case (starting with a random entry and checking consecutive entries wouldn’t work with badly distributed hash keys). You could do this if you re-hash the table with fewer slots if it gets to empty, or if you know that you never delete any hash entry.

You could have a bitmap of unused entries which would make the search faster by a large constant factor. You could create a linked list of the used slots if less than 20% of slots are used and maintain it until usage exceeds 50%, instead of re-hashing.


How does cycling happen in the simplex method?

Cycling happens in a different scenario: when $cx_{k+1} = cx_k$. This happens when the current solution is degenerate, that is, when the set $C_k$ is not unique.

For a worked out example, see Cycling in linear programming problems or The simplest examples where the simplex method cycles and conditions where EXPAND fails to prevent cycling. There are many other resources which are available online.


I wrote a paper on this. The short answer is that there is no optimal encoding, nor even an optimal sequence of better and better encodings.

Kraft's inequality states that there is a prefix code with word lengths $k_0,k_1,\ldots$ if and only if
$$
\sum_{n=0}^\infty 2^{-k_i} \leq 1.
$$
This gives a positive answer to your question. Concretely, Elias gamma coding has code word length $O(\log n)$. The idea is simple: first you encode the bit-length of the integer using your method (using roughly $\log_2 n + 1$ bits), then you encode the number itself (using another roughly $\log_2 n$ bits), for a total of roughly $2\log_2n + 1$ bits.


Does the term "continuity" have a different meaning in maths and in CS?

If we were to use the decimal expansion to represent real numbers, your reasoning would work. But that gives us a very badly behaved notion of computability:
Proposition: Multiplication by 3 is not computable relative to the decimal representation.
Proof: Assume the input starts 0.3333333... At some point, our computation needs to start outputting something. The best choices are 0. and 1.. In the first case, we have screwed up if our input has a 4 as next digit we hadn't looked at; in the second case a 2 makes us wrong. Thus, we cannot output a guaranteed prefix of the solution.
Using a different base would yield a different notion of computability, but none of them are suitable. Some ways that all yield the same good notion of computability are:

Code a real $x$ as a sequence of rationals $(q_n)_{n \in \mathbb{N}}$ such that $|x - q_n| < 2^{-n}$.
Code a real via a signed digit representation, using $\{-1,0,1\}$.
Code a real $x$ as a sequence of rational intervals $(I_n)_{n \in \mathbb{N}}$ with $\bigcap_{n \in \mathbb{N}} I_n = \{x\}$

When we speak about computability of a function on the reals without specifying what kind of representation we are using, we mean one of these (or another equivalent one). This is just like we don't always point out using the Euclidean topology on the reals if we do, that is just the standard case. We can now state:
Theorem: The functions on the reals which are computable (wrt the standard representation) relative to some oracle are exactly the continuous functions (wrt the Euclidean topology).
Coming back to rounding, this shows that perfectly exact rounding cannot work. However, we can circumvene this by not restricting ourselves to functions. For example, the following task is computable:
Given a real number $x \in [0,1]$, output either $0$ or $1$. If $x < 0.501$, then $0$ is an acceptable solution and if $x > 0.499$, then $1$ is an acceptable solution.
If the input to the task above is from $[0.499,0.501]$, then the answer we get does not only depend on the real we are looking at, but on the particular code for that real that our algorithm reads. That can make reasoning about algorithms slightly more cumbersome, but we really can't avoid that.


Is it possible to create a NFA that accepts only n*"a" or n*"b" inputs?

Yes it is.
Considering regular expression and NFA have the same power (source here), your question amounts to asking if there is such a regular expression.
So the regular expression would be /a*|b*/.
As for a NFA doing such a thing, here is an article describing how to go from regex to NFA.
In the article about regex to NFA, there is a section at the end explaining about metacharacter \$ for end of string. An actual regex for your problem would then be /^(a*|b*)$/ .


LaTex Text Justification badness penalty

The optimization function is designed in a way to find a solution that:

uses a small number of lines
is balanced (the number of extra spaces at the end of each line should be about the same length)

Lets look first at the linear optimization function, i.e. the sum of all extra spaces.

It is very clear, that the optimal solution under that function is one that uses the minimum number of lines.
However it will not fulfill the second goal.
The number of extra spaces is equal in each solution that uses the same number of lines.

For instance if you want to split the string a.bb.ccc at line-width 6.
The unbalanced solution

a.....
bb.ccc

has the same penalty 5 (number of extra spaces) as the balanced solution

a.bb..
ccc...

. So if you only optimize with a linear function, then you might end up with an unbalanced solution.

Now lets look at the the sum of squares.

The intuition is, that having lines with a lot of extra spaces will get penalized a lot more than lines with less extra spaces.

Using the same example. The unbalanced solution

a.....
bb.ccc

will get a bigger penalty $5^2 + 0^2 = 25$ than

a.bb..
ccc...

which has only a penalty of $2^2 + 3^2 = 13$.

You can actually partially prove that this will give us a balanced solution.

If you fixate the number of lines, than also the number of necessary extra spaces is fixed. Let's assume than we need $n$ lines with $m$ extra spaces. I'll denote $a_i$ for the number of extra spaces in line $i$.

We want to optimize $$\sum_{i = 1}^n a_i^2$$
We know (using the QM-AM inequality), that

$$\sum_{i = 1}^n a_i^2 \ge \frac{(\sum_{i=1}^n a_i)^2}{n} = \frac{m^2}{n} = \text{const}$$

and that we reach equality for $a_i = \frac{m}{n}$ for all $i$.

So the minimum of the optimization function is reached, when every lines has exactly the same number of extra spaces.

Notice, that usually this is not possible (because of the different word lengths in the string).

But the result supports the argument, that this optimization function ends up with a solution that we human would call "balanced".

The cubic function, and many other ones, will work in exactly the same way. Unbalanced solutions will end up with a higher penalty than balanced solutions.

Btw, $\LaTeX$ uses the sum of squares as penalty. At least Wikipedia claims so.


Big O understanding given different input sizes

No, this isn't correct, for a number of reasons.

$O(\cdot)$ only gives upper bounds. Being told that $f(n)=O(n\log n)$ doesn't exclude the possibility that $f(n)=n$, $f(n)=1$, etc.
The bounds only apply to sufficiently large $n$. Perhaps your measurements were for values of $n$ that are too small to exhibit the asymptotic behaviour.
Even if $n$ was large enough, consider the algorithm "If my input has odd length, return immediately; otherwise, perform some calculation that takes exactly $n^2$ steps." This has running time $O(n^2)$, so you'd expect an input twice as big to take four times as long. But an odd-length input will take about $n$ steps, whereas $2n$ is even, so an input of that length would take time at least $(2n)^2$, which is much more than four times as much.
The actual running time of the code on an actual computer will depend on all kinds of factors that aren't included in the theoretical analysis. You could be careful to exclude things such as interruptions by other processes, but consider something like disc access. Suppose that your input of size $n$ takes up a quarter of a disc block. Most of the running time of your algorithm might be waiting for that one block to be transferred; the input of length $2n$ will also fit in one block, so you do the same amount of disc I/O and doubling the input takes only a small fraction longer to run. On the other hand, if your length-$n$ input is a whole block, then reading two blocks will take twice the time. Except that the OS will probably cache the second block for you, so probably it won't. Similar effects apply to memory accesses and their interaction with the cache.
Your arithmetic is off. Consider the three functions $f(n)=n$, $g(n)=n^2$ and $h(n)=n\log_2 n$.  Then
$$f(2n)=2n=2f(n)\\
g(2n)=(2n)^2=4n^2=4g(n)\\
h(2n)=2n\log_2 2n = 2n(\log_2 n+\log_2 2) = 2h(n)+2n\,.$$


L = {w belongs to {0, 1} * ∣ w has at most three 0’s}. Why is this regular language?

As the other answers have said, the key is in the statement of the pumping lemma.

The key to understanding how to apply the pumping (and how not to as well) is paying close attention to the quantifiers ("for all" and "there exists") and the order they come in:

  The Pumping Lemma for Regular Languages

  If the language $L \subseteq \Sigma^{\ast}$ is regular, then there exists a constant $p \geq 1$ such that for every string $s \in L$ where $|s| \geq p$, there exists a division of $s = xyz$ such that:

  $|xy| \leq p$,
  $|y| \geq 1$, and
  for all $i \in \mathbb{N}$, $s' = xy^{i}z \in L$.

So if you wanted to show that a language obeyed the pumping lemma (note that is would not prove that it's regular, there are non-regular languages that can also be pumped), you have to first determine the pumping length $p$, then look at every string $s \in L$ and show that there is some way that $s$ can be broken down so that it can be pumped according to the conditions.

So in your case, if we ignore that you don't know $p$, the mistake is showing that one way of breaking it up doesn't work. So assuming that the pumping length is at least $4$ (it is, but why...?), then the breakdown $x = 000$, $y = 1$, $z = 1^{n-1}$ can quite happily be pumped.

When this has settled in, it also shows how the proofs of non-regularity via the pumping lemma work. You just have to find one string, but you have to show that there is no workable breakdown for that string.


Why arrival process of packets at a switch is not a Poisson Process?

"new flow arrivals" means "arrivals of new flows".  A flow is a TCP connection (roughly); each individual TCP connection is a separate "flow".  So, this is talking about new TCP connections, and the rate/time at which the server receives new TCP connections.

Contrarily to the statement you quoted, web requests won't necessarily be Poisson.  There are many factors that can cause web requests to be other-than-Poisson-distributed.  For instance, the Olympics web site receives a lot more traffic when the Olympics events are happening than when they aren't.  Many web sites receive more traffic during the time of day when their primary user population is awake than when they're not.  In addition, visiting one page on a site typically triggers many requests for other related resources (e.g., images that are loaded on that page).

However, during any sufficiently short time period, if their user base is sufficiently large, the arrival process for a particular type of web request might well be approximately Poisson.

See, e.g., https://en.wikipedia.org/wiki/Poisson_distribution#Occurrence.


Stable marriage problem with more people then priorizations

In general, you won't be able to marry all but one of the men and all but one of the women. For example, suppose that all of the men want to marry the same four women: you'll get exactly four marriages and an arbitrarily large number of bachelors and spinsters.


Find a regular language that becomes non-regular if you cut away the middle third of all words

Hint: Let $A = a^+ b^+ c^+$ and consider $A' \cap a^+c^+$.


Turning a simple polygon with holes into exterior-bounded only

The closest vertices between the inner and outer polygons do not necessarily produce a valid solution as shown in the following figure:

You just need to find a pair of vertices between the inner and outer polygons whose corresponding edge does not intersect either polygon.
Search for vertices $u$ and $v$ from the inner and outer polygons such that the edge $(u,v)$ does not cross any other edge (some care needs to be taken that you don't
slip between two edges as shown on the right above -- choosing the closer vertex avoids this problem).

A straight forward approach would scan all such $u,$ $v,$ and all edges
resulting in $O(n^3)$ time in the worst case -- in practice you'll find a solution fairly quickly. This can be sped up by placing all the vertices in a BSP tree whose half-spaces are defined by the polygon edges -- then you only considering vertices $v$ in the same half-space as $u.$


How to cover maximum points with a fixed length line segment?

You haven't explained how to implement how many there is point in the range r. You do this operation N times, so unless it takes $O(1)$, your algorithm won't be $O(N)$.

There is a simple algorithm that runs in time $O(N\log N)$:

Sort the input points.
Go over all the points in order, maintaining a data structure keeping track of the points at distance at most $L$ from the current point.

You can implement each iteration of the second step in amortized $O(\log N)$ using a balanced binary search tree.

Can we do it asymptotically faster? In many restriction computation model, the problem of element uniqueness (given a list of integers, determine whether they are all unique) requires $\Omega(N\log N)$ operations. Since element uniqueness reduces to your problem, in these models your problem requires $\Omega(N\log N)$, so the algorithm broadly outlined above is asymptotically optimal.

Of course, in practice you might benefit from algorithms which are more sensitive to the input distributions. In fact, assuming the answer is $M$, the algorithm outlined above runs in time $O(N\log M)$. If you expect $M$ to be very small, it might be worthwhile to use a list rather than a balanced binary search tree.


How this proof of fractional knapsack works?

The following condition is implicitly included in the question.

$$\dfrac{v_1}{w_1}, \dfrac{v_2}{w_2}, \cdots, \dfrac{v_n}{w_n} \text{ is in the descending order.}$$

Let $W$ be the total weight to be filled. The greedy algorithm for fractional knapsack problem is the following procedure.

Let $k$ loop through $1, 2, ..., n$ in that order.

Set $$x_k = \dfrac{W- \sum_{1\le i\lt k} x_i}{w_i}$$
If $x_k<1$, set $x_l=0$ for all $l>k$. Break the loop.

$$\dfrac{v_i}{w_i}(x_i-y_i)\ge\dfrac{v_j}{w_j}(x_i-y_i),\tag{????}$$

There are three cases for $i$.

The case when i < j, i.e., $\dfrac{v_i}{w_i}\ge\dfrac{v_j}{w_j}$. Since $j$ is the first index s.t. $x_j<1$, $x_i=1$, i.e., $x_i-y_i\ge0$.
The case when i = j. Both sides are 0.
The case when i > j, i.e., $\dfrac{v_i}{w_i}\le\dfrac{v_j}{w_j}$. Since $j$ is the first index s.t. $x_j<1$, according to the definition of the greedy algorithm, $x_i=0$. That means $x_i-y_i\le0$.


What's the time complexity of this algorithm? And Why?

The only two arguments relevant to asymptotic analysis are $d$ and $p$. These arguments (virtually) satisfy $d,p \geq 0$ and $d \leq p$ (we need to shuffle the logic in the function slightly to get this). At each point in the execution, you take the current pair $(d,p)$ and then recursively call the function with the pairs $(d-1,p),(d,p-1)$, avoiding pairs which invalidate the constraints stated above.

We can picture the resulting call tree as a path starting at $(0,0)$. Each time you decrease $p$, add a / step. Each time you decrease $d$, add a \ step. The condition $d \leq p$ guarantees that you never go below the X axis. Moreover, you have a "budget" of $n$ of each step. The total number of leaves in this call tree is exactly the Catalan number $\binom{2n}{n}/(n+1) = \Theta(4^n/n^{3/2})$, and this gives us a lower bound on the running time of the function.

To get an upper bound, note that on the way to each leaf we pass through $2n$ nodes, and this gives an upper bound $2n$ larger than the lower bound, i.e., $\Theta(4^n/\sqrt{n})$.

We have a lower bound of $\Omega(4^n/n^{3/2})$ and an upper bound on $O(4^n/\sqrt{n})$. What are the exact asymptotics? They grow like the total number of paths not crossing the X axis which have at most $n$ steps in each direction. Using Bertrand's ballot theorem we can get an exact expression for this:
$$
\sum_{0 \leq d \leq p \leq n} \frac{p-d+1}{p+1} \binom{p+d}{p}.
$$
It thus remains to estimate this sum asymptotically:
$$
\sum_{0 \leq d \leq p \leq n} \binom{p+d}{p} - \sum_{0 \leq d \leq p \leq n} \frac{d}{p+1} \binom{p+d}{d} = \\
\sum_{0 \leq d \leq p \leq n} \binom{p+d}{p} - \sum_{0 \leq d \leq p \leq n} \binom{p+d}{p+1} = \\
\sum_{p=0}^n \binom{2p+1}{p+1} - \sum_{p=0}^n \binom{2p+1}{p+2} = \\
\sum_{p=0}^n \frac{1}{p+1} \binom{2p+2}{p} =
\Theta\left(\sum_{p=0}^n \frac{4^p}{p^{3/2}}\right) =
\Theta\left(\frac{4^n}{n^{3/2}}\right).
$$


What if there is a polynomial-time algorithm to minimize NFA?

If any PSPACE-complete problem is proved to be in P, then that proves that P = PSPACE, i.e., every problem in PSPACE can be solved in polynomial time.

Why?  Suppose we have a polynomial time algorithm for NFA minimization.  Since NFA minimization is PSPACE-complete, any other problem in PSPACE can be solved by reducing the problem to NFA minimization, then applying the polynomial-time algorithm for NFA minimization.  The definition of PSPACE-complete ensures that the reduction step will complete in polynomial time, so solving that problem can be done in polynomial time.


I would try to train a Recurrent Neural Network for this problem, the LSTM architecture is particularly interesting for time series prediction.

Sources:

karpathy.github.io/2015/05/21/rnn-effectiveness/
colah.github.io/posts/2015-08-Understanding-LSTMs/

You would of course need a training dataset consisting of a sequence of events. Let's say $x$ and $y$ coordinates for every timestamp $t$, (possibly $z$ as well to predict a jumping puppy).

Both the network input layer and the output layer would consist of 2 units.
Then you would train your model to predict $(x_{t+1}, y_{t+1})$ given $(x_{t}, y_{t})$. Once the network is trained, you can predict the position of the dog at any point in the future.

Let $M$ be our trained model and let's say you want to predict the position of the dog at time $k$ and you know the current position of the dog at time $t$.

$M(x_{t}, y_{t}) = (x_{t+1}, y_{t+1})$

$t = t+1$

$M(x_{t}, y_{t}) = (x_{t+1}, y_{t+1})$

$...$ increment $t$ and keep predicting until $t+1 = k-1$

$M(x_{t+1}, y_{t+1}) = (x_{k}, y_{k})$

Put in pictures this corresponds to:
 (picture from Udacity lecture about Deep Learning)


How can the max-flow and min-cut problems, if dual to one another, both have unbounded optimal value?

Here is an example of this anomaly in linear programs:

$$
\begin{align*}
& \max x & & \min \infty y \\
s.t.\; & x \leq \infty & s.t.\; & y \geq 1 \\
& x \geq 0 & & y \geq 0
\end{align*}
$$

The solution to both programs is $\infty$. What goes wrong?

The duality theorem only works when all coefficients are finite. If you go through a proof of the duality theorem you'll see exactly where it fails, and this is a nice exercise.

I should also stress that $\infty$ isn't usually regarded as a legitimate number in these contexts. If we assume all coefficients are real numbers, then $\infty$ is nothing else than a type mismatch.


Machine learning algorithm for predicting binary decisions on a large, underrepresented dataset

When you have many more "No" samples than "Yes" samples, this is known as the "class imbalance" problem.  Dealing with class imbalance is challenging: many machine learning algorithms don't work as well in this situation.

There are many techniques for dealing with class imbalance, including using class weights, oversampling the "No" samples, or undersampling the "Yes" samples.  I suggest doing a little bit of reading about techniques for dealing with class imbalance on Stats.SE, then trying them to see if they help.  Their effectiveness may depend on the data set and on which type of classifier you use.


Is there a way to find path length to a node from root in a binary tree?

The worst case scenario for the algorithm is when you pick two nodes, N1 and N2 that have the longest path to the root node. In your example, two nodes whose common ancestor is J.
Say the length of the path of N1 and N2 is n and m.
Then the first while is O(n), the second one O(m) and finally the nested loop is O(nm).
So O(n) + O(m) + O(nm) = O(n*m).


Closure of regular languages under deleting a 1 from each even run of 1s

Below you can find solutions for the similar problem in which we want to delete a single 1 from each odd length run of 1s. I'll let you adapt them to your question.

First, let me explain how to solve it using closure properties. We start with your language $R$. We then apply a regular substitution that optionally "marks" every 1, i.e. changes it into $\mathbf 1$. We intersect the resulting language with $0^*((11)^*(\mathbf{1}+\epsilon)0^+)^*((11)^*(\mathbf1+\epsilon)+\epsilon)$ – this has the effect of marking the final 1 out of each odd run. Finally, we apply a homomorphism that deletes all marked 1s.

Second, let me explain how to explicitly construct an NFA for the new language given an NFA for $R$. Let the NFA for $R$ be $\langle Q, \{0,1\}, \delta, q_0, F \rangle$. The new states will be $(Q \times \{0,1\}) \cup \{q_f\}$, and the new initial state will be $\langle q_0, 0 \rangle$; the second entry is the parity of the current run of 1s. The new accepting states are $(F \times \{0\}) \cup \{q_f\}$ (note that in the new language, all runs of 1s must have even length). It remains to define the new transition function:

If there is a transition $q_1 \stackrel 0 \to q_2$, then we add a transition $\langle q_1, 0 \rangle \stackrel 0 \to \langle q_2, 0 \rangle$; that is, we allow the transition only if the parity of the current run of 1s is even.
If there is a transition $q_1 \stackrel 1 \to q_2$, then we add the following transitions:

$\langle q_1, 0 \rangle \stackrel 1 \to \langle q_2, 1 \rangle$ and $\langle q_1, 1 \rangle \stackrel 1 \to \langle q_2, 0 \rangle$; these just maintain the parity of the length of the run.
If $q_2 \in F$: $\langle q_1, 0 \rangle \stackrel \epsilon \to q_f$. This handles odd runs of 1s at the very end of input.

If there are transitions $q_1 \stackrel 1 \to q_2 \stackrel 0 \to q_3$, then we add the transition $\langle q_1, 0 \rangle \stackrel 0 \to \langle q_3, 0 \rangle$. This corresponds to deleting a 1 from the end of an odd run.


if (λ x . x x) has a type, then is the type system inconsistent?

Certainly, assigning a type to $\lambda x. x\ x$ is not enough for inconsistency: in system $F$, we can derive
$$ \lambda x.x\ x:(\forall X.X)\rightarrow (\forall X.X)$$

in a pretty straightforward way (this is a good exercise!). However, $(\lambda x.x\ x)(\lambda x.x\ x)$ cannot be well typed in this system, assuming $\omega$-consistency of 2nd order arithmetic, as this implies that all such well-typed terms are normalizing.

Furthermore, system $F$ is consistent. This follows from either normalization, as one can show that any term of type $\forall X.X$ cannot have a normal form, or a much simpler argument, in which each type is assigned a set, either $\varnothing$ or $\{\varnothing\}$ and it can be shown that all derivable types are assigned $\{\varnothing\}$, and $\forall X.X$ is assigned $\varnothing$ (and is therefore not derivable).

The latter argument can be carried out in first-order arithmetic. The fact that $\lambda x.x\ x$ can be well-typed in a consistent system can be seen as somewhat disturbing, and is a consequence of the systems' impredicativity. It shouldn't come as a surprise that some people question the trustworthiness of impredicative systems of logic. However, no inconsistencies have been found so far in such systems.

On the other hand, to be able to make the more general assertion that $(\lambda x.x\ x)(\lambda x.x\ x)$ cannot be well-typed in a consistent system, you need to have enough "logical structure" in your type system to be able to clearly define consistency. Then you need to show that a term without a head normal form (like the one above) can have any type, which is also not obvious!

More details can be found in my answer to a related question: https://cstheory.stackexchange.com/a/31321/3984


Problems that are hard in the best case?

To answer the question, one must first define what is meant by "best case".

One possible definition of "best case" complexity is, what is the running time for the best input?  In other words, take the minimum over all instances, of the running time for that instance.

With that definition, there are no decision problems (problems with a yes/no answer) that are hard in the best case.  That's because I could write a stupid algorithm that knows how to solve one particular problem instance efficiently (it has the solution for that instance hardcoded) and is slow on all else -- in the best case, this would be efficient.

For instance, consider 3-colorability problem, where given a graph we have to determine whether it is 3-colorable.  Let's fix a single graph $G_0$ that we know is 3-colorable.  Now consider the following algorithm:

Algorithm:
Input: a graph $G$
 1. If $G=G_0$, output "Yes".
 2. Otherwise, do something very slow to try to test whether $G$ is 3-colorable.

This algorithm is very slow in the worst case (and typical case), but it is fast in the best case: when the input is $G_0$, it immediately outputs the correct answer.  The existence of such an algorithm shows that 3-colorability is easy in the best case.

There was nothing special about 3-colorability that I used there.  You can apply the same reasoning to any decision problem (or any problem where the output size is not too long).

In retrospect, that was probably the wrong definition.  A better definition would be: for a fixed algorithm, let $T(n)$ denote the minimum over all instances of size $n$, of the running time of that instance.  Then, the function $T(\cdot)$ is the best-case complexity of that algorithm (and of course we want to know the minimum over all algorithms, or a suitable lower bound that holds for all algorithms).  This prevents hardcoding a single instance, because there will be a different best instance for each $n$.  I don't know whether there are any problems that are hard, for this best-case complexity measure.

It's more interesting to look at average-case hardness.  While many problems are hard in the worst case but easy on the average case, there are some problems that are both hard on the worst case and hard on the average case.  One tool used to prove average-case hardness is random self-reducibility.  For instance, the discrete log problem is believed to be hard on the average case.  In particular, it is believed to be hard on the worst case, and we can prove that if it is worst-case hard, then it is average-case hard, too, using a random self-reduction.


Definition of 2-CNF (a.k.a Krom) formula

A unit clause of the form $p$ is the same as the clause $p \lor p$, and so corresponds to the arrow $\lnot p \to p$.

As an example, consider the unsatisfiable CNF
$$ p \land (\lnot p \lor q) \land \lnot q. $$
The implication graph contains the following edges:
$$
\lnot p \to p \\
p \to q,
\lnot q \to \lnot p \\
q \to \lnot q
$$
These can be arranged in a cycle:
$$
\lnot p \to p \to q \to \lnot q \to \lnot p
$$
This cycle contains both $p$ and $\lnot p$ (and also both $q$ and $\lnot q$), showing that the formula is unsatisfiable.


When pure CDCL solvers (such as MiniSAT, I believe) are run on unsatisfiable instances, their transcript can be converted to a Resolution refutation of the instance. In particular, the running time of the solver is lower bounded by the length of the smallest Resolution refutation of the instance. There are instances which are known to take exponential length to refute in Resolution, for example the Pigeonhole Principle on $n+1$ pigeons and $n$ holes. Such instances will take exponential time to refute on any pure CDCL solver.


How is an Assembly Language Processed by a CPU's Circuitry?

An assembler is a program that reads assembly language commands and translates then into a sequence of binary instructions, addresses and data values that is called machine code. The machine code is stored in the computer's memory and can be executed by the computer at some later time. Machine code is read and "understood" directly by the CPU.

So a command such as "load the value 10 into register A" might be written in assembly language as "LDA 10" and then stored in machine code as one byte 00101010. The first four bits of the machine code instruction 0010 represent the LDA instruction and the second four bits 1010 represent the value that is to be loaded.

Note that the assembler makes life easier for the programmer by translating the "LDA" instruction and translating the value 10 from decimal to binary. It will also do other stuff like allowing the programmer to use labels, which it then translates into specific memory addresses.

In the simplest CPU architecture, when the CPU executes the instruction 00101010 it actually runs a sequence of low level microinstructions which will be something like this:

Add 1 to the register that tells the CPU where the next instruction is stored in memory
Set a control line to take control of the data bus.
Load the lowest four bits of the machine code instruction onto the data bus.
Release control of the data bus.
Set a control line to tell Register A to read and store the value on the data bus.
Read the next instruction from memory.

In the very simplest/oldest CPU architecture this final translation from machine code to microinstructions is hard wired in logic gates.

A good guide to this sort of stuff for beginners is "But How Do It Know".

Bonus question: If an assembler is a program that creates other executable programs, how is the assembler created in the first place ?


If $A \le _m B$, then $A$ decidable $\not\Rightarrow B$ decidable

Consider $A = \Sigma^*$ and $B \subset\Gamma^*$ undecidable. If you know any $b \in B$, the constant mapping $\Sigma^* \to \Gamma^*, w \mapsto b$ provides a counterexample.

To be a bit more specific: Let $\Gamma = \{\texttt<, \texttt>, \texttt[, \texttt] \texttt+, \texttt-\}$ be the set of symbols for Brainfuck without I/O. As BF is Turing complete, we know that the subset $B \subset \Gamma^*$ of all terminating BF programs is undecidable (via the Halting problem). It turns out that $\texttt{+} \in B$.

Thus we have $A \leq_m B$ for all languages $A \subseteq \Sigma^*$ via the mapping $f\colon \Sigma^* \to \Gamma^*$ given by $f(w) = \texttt+$.


The formula you state follows from summing a geometric series:
$$
1 + b + b^2 + \cdots + b^d = \frac{b^{d+1}-1}{b-1}.
$$
When $b=1$, the series sums to $d+1$, which is also the limit of the expression above as $b\to1$.

As you mention, the formula is only meaningful when $b \neq 1$, though the correct value can still be recovered by taking a limit. This is perhaps the simplest example of a curious phenomenon in combinatorics, that of the "field with one element". Consider the following two quantities:

The number of subsets of size $k$ of a set of size $n$. These are counted by binomial coefficients $\binom{n}{k}$.
The number of $k$-dimensional subspaces of an $n$-dimensional vector space over the finite field with $q$ elements. These are counted by Gaussian binomial coefficients $\binom{n}{k}_q$, which are rational functions (ratios of two polynomials) in $q$.

The curious thing is that if we substitute $q=1$ in the expression for $\binom{n}{k}_q$, we get back $\binom{n}{k}$ in the limit. (Just as in your case, when $q=1$ the denominator vanishes.) So a set is similar to a vector space over "the field with one element".

More generally, there are other formulas involving "$q$-analogs" (sets replaced with vector spaces over the field with $q$ elements) which degenerate to the correct values when taking the limit $q\to1$. There are some explanations for this phenomenon but it is still somewhat mysterious.


Literature on network-flow (optimization) approximation algorithms

In his FOCS2013 (Best Paper award) work, Aleksander Mądry gives a $\widetilde O(m^{\frac{10}{7}})$-time for exact max-flow and gives a nice survey on the existing techniques (including near-linear time for $(1+\epsilon)$-approximation in undirected graphs).


How to determine the carry vector of an integer addition

The generation of the carry vector is a recursive process where the results of lower bits factor into the current carry output.

In general:

$$
Carry_{n} = (A_{n} \bullet B_{n}) + ((A_{n} \oplus B_{n}) \bullet Carry_{n-1})
$$
Note the $$ Carry_{n-1} $$ term. The presence of this term means that carry data ripples through the adder chain.

This is the reason that so much effort was devoted in older computer implementation technologies to speeding up this process. This was done by brute force computing the carry for groups of bits in a process called carry look-ahead. Let's see this for two bits:

$$
Carry_{n} = (A_{n} \bullet B_{n}) + ((A_{n} \oplus B_{n}) \bullet ((A_{n-1} \bullet B_{n-1}) + ((A_{n-1} \oplus B_{n-1}) \bullet Carry_{n-2})))
$$

As bits get added, this gets messy in a hurry.

The classic 74181 ALU used this method for the 4 bits handled by the chip and was often paired with the 74182 Carry Look Ahead chip to speed carry propagation by performing the same between up to four chips. If more that 16 bits needed to be processed, another layer of 74182 was employed to speed up carry propagation in the lower layer. Thus an ALU with 16 74181s, 4 74182s, and one top level 74182 could process 64 bits with a delay of roughly 3 times the four bit ALU delay, instead of 16 times.

It is noteworthy though, that there is no easy solution to the problem. Each added bit of look ahead, increases the complexity of the carry generator.


Probably the best way to explain how such an algorithm works is via diagrams showing it step by step for some examples, examples selected to exercise your code more or less fully (need not cover all left/right symmetric cases, for example).

If you use LaTeX, look for a package to typeset algorithms, like algorithm2e, and check out TikZ and it's facilities to draw trees. It's documentation is quite forbidding, search for tutorials or targeted explanations.

Place yourself in the shoes of your gentle reader: What would you like to see? What points of the algorithm are thorny? Any corner cases that need explaining? Any strange/surprising/seemingly useless lines?


A number of points on a line, with initial positions and speeds - find a minimum time that any two points meet

I'm assuming we're given an ordered list $(y_0,y_1,...,y_{n-1})$ of initial point positions together with a list $(s_0,s_1,...,s_{n-1})$ of their speeds.

You can visualize moving points on a Cartesian plane with "position" and "time" coordinate axes - so the point $P_i$ trace will be a ray $R_i$, beginning at the point $(0,y_i)$ and consisting of points $(t, y_i+s_it)$ for $t\ge0$. If points $P_i$ and $P_j$ meet at some time $t$ then their corresponding rays $R_i$ and $R_j$ will intersect, and their intersection point will be $(t,y)$ - we'll call this time $t$ a meeting time.

Observation. If an intersection point $(t,y)$ for two rays $R_i$ and $R_j$ has a minimal meeting time $t$ among all the pairs $(i,j)$ where $i\lt j$, then $i=j-1$ (in other words - points $P_i$ and $P_j$ were initially neighbor ones - try to prove that).

So, it means that you can look for minimal meeting time among pairs of neighbor points only - their total number is $O(n)$, and the algorithm time is also linear. If the original list of points is not ordered by their coordinates, then the algorithm time will include sorting, which is $O(n\log(n))$.


Best and worse case inputs for heap sort and quick sort?

heap- Since the best and worst case are the same does it not matter the input order? The number of comparisons and assignments will always be the same? I imagine in a heap sort it may be the same since the real work is done in the insertion, but the sorting only uses the removal of the max/min heap? Is that why?

The number of comparisons made actually can depend on the order in which the values are given. The fact that the best and worst case are each Θ(n log n) - assuming all elements are distinct - only means that asymptotically there's no difference between the two, though they can differ by a constant factor. I don't have any simple examples of this off the top of my head, but I believe that you can construct inputs where the number of comparisons differs by a constant factor between the two approaches. Since big-O notation ignores constants, though, this isn't reflected in the best-case and worst-case analysis.

  quick sort- This one I don't know for sure. I'm not sure what the best case and worst case situations are for this. If its a already sorted list of 10 strings for example wouldn't we always have to choose the same amount of pivots to get complete the recursive algorithm? Any help on this explanation would really help.

The number of pivots chosen is indeed the same regardless of the execution of the algorithm. However, the work done per pivot can vary based on what sort of splits you get. In the best case, the pivot chosen at each step ends up being the median element of the array. When this happens, there are (roughly) n comparisons done at the top layer of the recursion, then (roughly) n at the next layer because there are two subarrays of size n / 2, then there are (roughly) n at the next layer because there are four subarrays of size n / 4, etc. Since there are Θ(log n) layers and each layer does Θ(n) work, the total work done is Θ(n log n). On the other hand, consider choosing the absolute minimum of each array as a pivot. Then (roughly) n compares are done at the top layer, then (roughly) n - 1 in the next layer, then (roughly) n - 2 in the next, etc. The sum 1 + 2 + 3 + ... + n is Θ(n2), hence the worst case.

Hope this helps!


Questions about class of problems that can be solved with unlimited computational power, but access to only logarithmically many bits of the input?

It is contained in $P/Poly$

Let $M$ be a logarithmic time superoracle machine which decides some language $L$ in your class. We can define it by adding a special tape in which we can specify our desired language by writing some real number. Upon querying the oracle it will determine the membership of the given string to the specified language.

With polynomial length advice, you could provide the choice tree that determines what bits are read from a length $n$ input (if the first bit is x then go read y...). The questions to the oracles are determined by the bits read, and I can ask only a logarithmic number of questions (would work for polynomial too).

In the advice i could also hardcode a table which links any possible logarithmic input to the answers from the desired oracles. Given such advice and some input $x$, read the required bits using the choice tree, and simulate the special machine with the oracle answers given in the advice.


You test the function in the same way you test anything else: you identify some example inputs and the desired outputs, and you run the function on those inputs and see if it gives you the desired output.  You can still do that despite "not falling on a byte boundary".

In this case the function bits is a stateful interface, so you have to deal with that, but the same techniques for testing stateful interfaces should work fine here.  In particular, the "input" is a sequence of operations on the data structure / API, and the "output" is the sequence of results from those operations.  For instance, the first operation might be to set the contents of the underlying byte stream, and the second operation might be to invoke bits().

I'm not sure where you're getting $512 \times 2^{32}$ from (presumably you mean $32 \times 2^{32}$), and those aren't permutations; but in any case that doesn't change anything.  Testing almost never exhaustively tries all combinations.  I don't see why this would be any different.  Instead, the idea behind testing is that we try a small fraction of the possibilities, and if there is a bug, we hope that one of the test cases we try will expose it.  This doesn't provide any guarantees, since there could always be a bug that only triggers on one of the test cases we didn't try -- testing is not verification, and does not prove correctness -- but it is useful nonetheless.

So, nothing prevents you from testing this function.  Standard methods work fine.


Scoring metric for machine learning method

There are at least two possible interpretations of uncertainty: (a) uncertainty/confidence in the label that the network predicts; (b) uncertainty in the probability/confidence score that the network outputs for the predicted label.  (There might be others as well.)  Let me explain both of those.

Confidence scores: uncertainty in the label

Standard deep learning methods already provide a confidence score for their prediction.  They output not a single label, but a probability distribution on labels (through a final softmax layer).  Then a cross-entropy loss function is used to measure how well the predicted distribution matches the known labels, on the training set.

Once you have this, you can easily measure uncertainty.  When applied to a test instance $x$, the output will be a probability distribution on labels.  If the label $\ell$ has the highest probability (in this distribution), say probability $p$, then $p$ is a measure of the network's uncertainty/confidence: the smaller $p$ is, the more uncertain (the less confident) the network is in its prediction.

For example, suppose we have a neural network whose input is an image of a stoplight, and classifies whether it is showing a red light, i.e., the two labels are "red" or "not red".  Such a neural network (if it ends with a softmax layer) actually outputs a vector $(p_\text{red},p_\text{not red})$ where we interpret $p_\text{red}$ as the network's estimate of the probability that the light is red.  Thus, the network classifies the image as "red" if $p_\text{red} \ge p_\text{not red}$ and "not red" otherwise, and the confidence score is the probability score associated with that label.

This provides a notion of uncertainty.  For instance, suppose the network outputs the vector $(0.8,0.2)$.  Then we'll classify the image as "red", and the confidence score indicates that the network thinks there is a 80% chance that the image is red, so that is a notion of how certain it is that the image is "red".  This confidence score is also known as a "posterior probability", in a Bayesian framework, and it can be treated as measuring one kind of confidence.

Uncertainty in the confidence score

Alternatively, perhaps what we want to measure is not uncertainty in the predicted label, but uncertainty in the confidence score associated with that label.  For instance, if the output vector is $(0.8,0.2)$, then we'll classify the image as "red", with 80% confidence; perhaps what we care about is, how certain/uncertain are we, in the number "80%"?

That can be measured by the variance of this score.  We can construct 1000 different neural networks for this task.  Each one will output an output vector, and in particular, a confidence score that the image is red.  If we want our best estimate of the posterior probability that the image is red, we take the average of those 1000 scores. If we want to know the uncertainty in that estimate, we take the variance (standard deviation) of those 1000 scores.  Thus, this might let us say "we classify the image as 80% likely to be 'red', with standard deviation of 5% around the 80%".  That variance (or standard deviation) can be taken as a measure of our uncertainty in the number 80%.

This is what Nicolas Mancuso's excellent answer is explaining, in mathematical terms.  I've tried to explain it in non-mathematical terms, to help understand the idea.

Why 1000 networks?  The number 1000 is arbitrary.  A smaller number will be faster.  A larger number will provide a more precise measure of the standard deviation.

How do you train 1000 random networks?  There are several possibilities.  One is to use bagging.  Another is to train on the same training set, but use different random values when creating the network (e.g., initialize each network randomly and independently; use dropout, and use different randomization for each network's dropout, and maybe enable dropout at test time too).


About the turing machine's non-deterministic branches

I guess, with branches you mean the computation branches (the sequence of the konfigurations M has in its computation) of $M$. Then in general a NTM $M$ will accept an input x, if there exists one computation branch in the computation tree, which leads to accept x, no matter, where other branches may lead to (even if there infinite long). So, Machine 1 and 3 will accept.

I am definitely not sure about the following: I guess, the question, what Machine 2 will do is not decidable (please correct me, if I am wrong)


Doubt regarding Maximum Bipartite Matching

Here's one possible hint:

$$\gcd(u,v,w,x) = \gcd(\gcd(u,v),\gcd(w,x)).$$

I expect your problem can also be solved using the techniques in the following paper:

Daniel J. Bernstein. Factoring into coprimes in essentially linear time. Journal of Algorithms 54 (2005), 1--30.

A maximal matching doesn't seem like the right approach.  The maximal matching algorithm you list will never choose two 4-tuples $(u,v,w,x),(u',v',w',x')$ such that $(u,v)=(u',v')$.  Thus, it won't produce the correct answer to the problem: it won't output the maximum number of different 4-tuples.


Your problem is known as the unweighted one-dimensional $k$-center problem. See for example a recent paper by Chen, Li and Wang.


Is there a Data Structure like Binary Decision Diagrams for Non-Binary Functions

Yup.  A BDD is just an acyclic finite-state automaton (DFA) that accepts a language $L \subseteq \{0,1\}^n$.  It represents the function $f(x)= 1$ if $x \in L$ or $f(x)=0$ if $x \notin L$.

You can generalize this to allow an acyclic finite-state automaton over a language over a different alphabet, or indeed, a language $L \subseteq \Sigma_1 \times \cdots \times \Sigma_n$ where $\Sigma_i$ is the set of valid values for $x_i$.  Everything carries over.


I ended up settling for Sparse Slot Map. I was wrong to say that slot maps don't do versioning - that depends on the implementation.


Proving that an $n$-element heap has at most $\lceil \frac{n}{2^{h+1}-1} \rceil$ nodes

Probably, you mean this:
A heap of size $n$ has at most $\lceil \frac{n}{2^{h+1}} \rceil$ nodes with height $h$.

Proof can be found for example here:
http://www.cs.sfu.ca/CourseCentral/307/petra/2009/SLN_2.pdf


Relation between "syntax" and "grammar" in CS

Your quote has the following operational meaning for syntax in the context of programming languages:

  The syntax of a programming language is the set of all syntactically valid programs.

The syntax only describes what the valid programs look like; semantics gives them meaning – tells you how to execute them.

The set of all valid programs is an example of a formal language; a formal language is just a collection of strings. There are many ways of describing formal languages. One of them is through formal grammars, which you can think of as a type of formula that describes a formal language. Context-free grammars are a restricted type of formal grammars. As such, they cannot describe all formal languages, but only context-free languages. (General grammars also describe only some of the formal languages; this is due to the fact that there are countably many grammars but uncountably many formal languages.) Summarizing:

  A grammar is one way to specify a formal language.

Finally, let me mention that the set of syntactically valid Java programs actually cannot be described by a context-free grammar; only some features can be described. Context-free grammars cannot enforce, for example, that a variable not be defined twice in the same context. However, once we abstract away such details (for example, by replacing variable names with generic placeholders), the resulting set of syntactically valid Java programs does lend itself (perhaps) to being captured by a context-free grammar.

Parsing (in our context) is the process of reading the source code of a Java program and constructing its parse tree, which is its structure as seen from the perspective of the context-free grammar. The parse tree captures the semantics of the program in a form amenable to further manipulation in the compilation process. Abstracting away details such as variable names and values of constants relegates this information into the form of parameters, but doesn't obstruct the control structure of the program.


A canonical form of a graph is a mapping $C$ from the set of graphs to the set of graphs such that $C(G)$ is isomorphic to $G$, and $C(G) = C(H)$ iff $G$ is isomorphic to $H$. Your function doesn't map graphs to graphs, so it's not a canonical form.

A more relevant notion is a (complete) invariant. This is a mapping $I$ from the set of graphs to some other set such that $I(G) = I(H)$ iff $G$ is isomorphic to $H$. Your mapping, as stated, is not a graph invariant. For example, consider the graph consisting of a triangle plus an isolated vertex. Consider the graph $G$ in which the triangle vertices are $1,2,3$, and the graph $H$ in which the triangle vertices are $1,2,4$. The two graphs are isomorphic, but the vector $\mathit{Triangle}(\cdot)$ is different.

We can try to fix this problem by sorting the vector. This will ensure that the vectors corresponding to $G,H$ above are the same. However, consider $H'$, which consists of a triangle connected by an edge to a vertex. The graphs $H$ and $H'$ have the same sorted triangle vector, but are not isomorphic. So your suggestion is not even a complete invariant.

Finally, you ask how easy it is to calculate your function. There is a trivial $O(n^3)$ algorithm which goes over all triples of vertices, and this can be improved to $O(n^\omega)$ using fast matrix multiplication: if $A$ is the adjacency matrix of the graph, then $(A^3/2)_{vv}$ is the number of triangles containing $v$.


Contrast Enhancement For An Image Using A Gaussian Function

Convolution is a relatively simple operation to perform, but to make it fast involves a little extra work (Wikipedia article on convolution theorem). In general, if you convolve a discretized function F by a different discretized function G, you are simply performing the following operation:

$$(F\otimes G)(x) = \displaystyle\sum_{i=0}^NF(x-i)*G(i)$$

Where N is the number of discrete values of G. Notice this is effectively just summing the product of F and G "centered" around $x$.

In 2D (which is what an image is), this looks like:

$$(F\otimes G)(x,y) = \displaystyle\sum_{i=0}^N\displaystyle\sum_{j=0}^MF(x-i,y-j)*G(i,j)$$

The paper you're reading tells you that F is the V channel of the image in HSV space, and G is a 2D gaussian function. Code-wise, the above form should translate very simply into a double-nested for loop.

The paper should also tell you what the mean/variance of the gaussian function is as well as the number of samples it contains, but sometimes that information is omitted.


$\mathsf{RegExpEq_*} \in \mathsf{coNPC}$ but why isn't in $\mathsf{P}$

By toggling the accepting states of $M$ we can construct an NFA which accepts $\overline{L(R)}$.

Well, that's not true. You won't get $\overline{L(R)}$. That would have happened if $M$ was a DFA, rather than a NFA. So you have to first convert $M$ to $M'$ which is a DFA, but then you would have to spend an exponential time there.


Conway's Game of Life: Is it really P-complete?

Your misunderstanding is the meaning of parallelize.
In this context, an algorithm can be parallelized if using polynomially many processors, you can compute the answer (in this case, the value of some cell) in polylogarithmic time.
Simulating the Game of Life naively takes time proportional to the number of steps. P-completeness of the Game of Life means that you cannot improve this to time polylogarithmic in the number of steps (unless $\mathsf{P}=\mathsf{NC}$).


The VC dimension when the samples are fixed

Suppose were in the realizable model, i.e. we want to learn some $f^*\in\mathcal{H}\subseteq 2^\mathcal{X}$ where $VCdim(\mathcal{H})=d$.

Let $M(\epsilon,\delta)$ be the minimal number of samples required to obtain an error of at most $\epsilon$ with probability at least $1-\delta$. Since the bound you mentioned on $M(\epsilon, \delta)$ holds for any distribution $\mathcal{D}$ over the sample space $\mathcal{X}$, we can treat this case as a uniform distribution with finite support $S=\left\{a_1,...,a_n\right\}$ (picked by the adversary). The learner picks a  set $T\subseteq S$ of $n/2$ samples (chosen uniformly at random), and chooses any consistent hypothesis $h$ (relative to $T$).

There are two issues which prevent us from directly using the known bounds on $err(h)$.

The first is that we are only interested in the error on the set $S\setminus T$, i.e. the training and test samples are not independent. This will add an extra $2$ factor to the bounds on $err(h)$, since:

$err(h)=\Pr_{x\sim\mathcal{D}}\left(h(x)\neq f^*(x)\right)=
\Pr\left(h(x)\neq f^*(x) | x\in T\right)\Pr(x\in T)+\Pr\left(h(x)\neq f^*(x) | x\notin T\right)\Pr(x\notin T)$.

In this case we have $\Pr(x\in T)=\Pr(x\notin T)=\frac{1}{2}$, and $\Pr\left(h(x)\neq f^*(x) | x\in T\right)=0$ ($h$ is consistent with $T$). So we get $err(h)=\frac{1}{2}\Pr\left(h(x)\neq f^*(x) | x\notin T\right)$, or equivalently $\Pr\left(h(x)\neq f^*(x) | x\notin T\right)=2err(h)$, where the left hand side is the probability that we wish to bound.

The second issue is caused by the fact that we don't allow repetitions while picking $T$ (the usual model treats each training sample as chosen independently from the distribution $\mathcal{D}$). To avoid this issue, the learner could choose $T$ by taking $m$ independent samples form $\mathcal{D}$, such that with high probability we see at least $\frac{|S|}{2}$ samples. This can be easily done by picking $m\approx |S|$, and conditioning on the event that we saw at least half of $S$, we can use the regular bounds on $err(h)$ for sample size $\ge|S|/2$.


Maximum set of equalities, subject to some inequalities

Using your graph theoretic formulation, this problem can be restated as the multi-cut problem.

  Given a graph $G = (V, E)$ and a set of pairs $(s_i, t_i) \in I$ find a  set of edges $E' \subseteq E$ such that there is no path $s_i \leadsto t_i$ in the resulting graph $G' = (V, E \setminus E')$ for each $i$.

Since each inequality is unweighted you need to find a minimum size multi-cut.

This problem is NP-hard in general however there exist reasonable approximation algorithms that solve an LP. However a simple strategy might be to just take the union of each $(s_i, t_i)$ cut.


The reason that no program can compute $S(n)$ is that if you knew what $S(n)$ is you could decide the halting problem - you'd know when to stop waiting. On the other hand, for each $m$ there is a program that computes $S(n)$ for all $n \leq m$ - it just uses a table.

If it were possible to prove the value of $S(n)$ for all $n$ (that is, for all $n$ we could prove $S(n) = \alpha$ for some $\alpha$) then we could compute $S(n)$ by searching through all proofs (this assumes that our proof system is valid). So for each proof system there is a minimal value of $n$ for which you cannot prove that $S(n) = \alpha$ for any $\alpha$.

Finally, the reason that we know $S(4)$ is probably because $4$ is a really small number. The number $5$ is slightly bigger, and so things get more complicated. There's no deep reason why we know $S(4)$ but not $S(5)$, just like there is no deep reason why we know the Ramsey number $R(4)$ but not $R(5)$ (though Ramsey numbers are of course computable).


Initially, node F is violating the heap invariant. Its priority is too small, and it needs to be moved up the treap. The only operation needed is a single rotation. If you are not already familiar, please read this Wikipedia entry. Here are some illustrative diagrams:

https://upload.wikimedia.org/wikipedia/commons/2/23/Tree_rotation.png
https://upload.wikimedia.org/wikipedia/commons/3/31/Tree_rotation_animation_250x250.gif

I've drawn snapshots of the rotation process below. In each diagram, I've marked where the rotation is about to happen with stars (e.g. *E:14*). The direction of rotation should be obvious: the goal is to get F up the tree! Notice that as long as F is violating the heap invariant, we're rotating the parent of F.

       G:3
      /   \
    B:6   K:8
   /   \     \
A:11   D:9   L:12
      /   \
    C:16  *E:14*
             \
             F:2

       G:3
      /   \
    B:6   K:8
   /   \     \
A:11  *D:9*  L:12
      /   \
    C:16  F:2
          /
        E:14

       G:3
      /   \
   *B:6*  K:8
   /   \     \
A:11   F:2   L:12
      /
    D:9
   /   \
 C:16  E:14

       *G:3*
       /   \
     F:2    K:8
     /        \
   B:6         L:12
  /   \
A:11   D:9
      /   \
    C:16  E:14

      F:2
     /   \
   B:6    G:3
  /   \     \
A:11   D:9   K:8
      /   \    \
    C:16  E:14  L:12

There are some really nice properties of rotations which make this work. Obviously rotations preserve the in-order traversal of the tree. But also notice that, whenever a subtree is detached/reattached during a rotation, there is never a priority inversion (i.e. you never attach a subtree as a child of a node with a larger priority).


Eliminating $\varepsilon$-productions during elimination of left recursion

The idea of the algorithm is to first find out which non-terminals can produce $\epsilon$, and then eliminate them in all possible ways.

Finding out which non-terminals produce $\epsilon$. The idea here is to start with the set $X^{(0)}$ of non-terminals which have an $\epsilon$ production. We then construct the set $X^{(1)}$ which includes $X^{(0)}$ and all other non-terminals having productions in $X^{(0)*}$ (that is, have productions in which the right-hand side consists of non-terminals in $X^{(0)}$ only). Continue this way until the process stops. The final set $X$ consists of all non-terminals which could produce $\epsilon$.

For example, in your case $X = X^{(0)} = \{A\}$. If there was a production $S \to A$, then you would have $X^{(0)} = \{A\}$ and $X = X^{(1)} = \{A,S\}$.

Eliminating non-terminals which could produce $\epsilon$. Now we simply take all productions containing non-terminals in $X$, and eliminate these non-terminals in all possible ways. That is, for each production containing terminals in $X$, you add additional productions resulting from deleting some of the non-terminals in $X$, in all possible ways. If you get $\epsilon$ productions this way, you just remove them (unless it's the possibly allowed $S\to\epsilon$).

For example, in your case the affected productions are $S \to Aa$ and $A \to Ac$. Handling the first, you add the production $S \to a$, and handling the second, you add the production $A \to c$.


First of all, I seriously doubt that anyone would have a working quantum computer capable of doing anything useful in the foreseeable future (let's say 10 years). Even if someone does construct a "quantum computer", it will probably be quite useless, and it will take several years more until it can be used to, say, crack codes.

The quantum speedup for breaking symmetric encryption is quadratic: if a single decryption takes time $T$ and there are $N$ bits in the key (usually $N\geq128$ nowadays, unless you're using DES which has $N=56$), then a classical computer will take $2^NT_{\text{classic}}$ time while a quantum computer will take $O(2^{N/2}T_{\text{quantum}})$ time using Grover's algorithm (as far as I understand). In terms of real-world time, we expect $T_{\text{quantum}}$ to be several orders of magnitude larger than $T_{\text{classic}}$, at least at first. Decrypting $2^{64}$ blocks in "quantum speed" will take a lot of time, so quantum computing doesn't seem to break symmetric encryption, barring any weaknesses which enable one to use a smarter algorithm than the naive one.

The story is different for public-key encryption, though again, quantum computers capable of doing anything interesting are still far into the future. Shor's algorithm can be used to factor integers, thus breaking RSA. The algorithm also applies for the discrete log problem, even on elliptic curves. This is problematic for other public-key cryptosystems. You can check out this survey for some quantum-resistant protocols.