Prove that it is undecidable whether a given LBA accepts a regular set I know for an LBA the emptiness problem is undecidable. However I am not clear on how to reduce the halting problem of Turing machines to this as LBAs are strictly computationally less powerful than Turing machines. Or should I approach with reductions using computational histories of a Turing machine on an input.

Thanks to @YuvalFilmus I managed to reduce the Halting problem to the given problem. We design an LBA B, that given an instance of the Halting problem, $\langle M,x\rangle$, accepts the valid computation histories of M on x. If M doesn't halt on x, $L(B)=\phi$ which is regular. However, if M does halt $L(B)=VAL-COMPS(M,x)$ which is not regular(not even CFL). Techinically, I have reduced the complement of the Halting problem, but as we know that it is also not decidable, so it's fine.


Type inference + overloading I'm looking for a type inference algorithm for a language I'm developing, but I couldn't find one that suits my needs because they usually are either:

à la Haskell, with polymorphism but no ad-hoc overloading
à la C++ (auto) in which you have ad-hoc overloading but functions are monomorphic

In particular my type system is (simplifying) (I'm using Haskellish syntax but this is language agnostic):

data Type = Int | Double | Matrix Type | Function Type Type

And I've got an operator * which has got quite some overloads:

Int -> Int -> Int
(Function Int Int) -> Int -> Int
Int -> (Function Int Int) -> (Function Int Int)
(Function Int Int) -> (Function Int Int) -> (Function Int Int)
Int -> Matrix Int -> Matrix Int
Matrix Int -> Matrix Int -> Matrix Int
(Function (Matrix Int) (Matrix Int)) -> Matrix Int -> Matrix Int

Etc...

And I want to infer possible types for

(2*(x => 2*x))*6
(2*(x => 2*x))*{{1,2},{3,4}}

The first is Int, the second Matrix Int.

Example (that doesn't work):

{-# LANGUAGE OverlappingInstances, MultiParamTypeClasses,
  FunctionalDependencies, FlexibleContexts,
  FlexibleInstances, UndecidableInstances #-}

import qualified Prelude
import Prelude hiding ((+), (*))
import qualified Prelude

newtype WInt = WInt { unwrap :: Int }

liftW f a b = WInt $ f (unwrap a) (unwrap b)

class Times a b c | a b -> c where
(*) :: a -> b -> c

instance Times WInt WInt WInt where
(*) = liftW (Prelude.*)

instance (Times a b c) => Times a (r -> b) (r -> c) where
x * g = \v -> x * g v

instance Times (a -> b) a b where
f * y = f y

two = WInt 2
six = WInt 6

test :: WInt
test = (two*(\x -> two*x))*six

main = undefined

I would suggest looking at Geoffrey Seward Smith's dissertation

As you probably already know, the way the common type inference algorithms work is that they traverse the syntax tree and for every subexpression they generate a type constraint. Then, they take this constraints, assume conjunction between them, and solve them (typically looking for a most general solution).

When you also have overloading, when analyzing an overloaded operator you generate several type constraints, instead of one, and assume disjunction between them, if the overloading is bounded. Because you are essentially saying that the operator can have ``either this, or this, or that type." If it is unbounded, one needs to resort to universal quantification, just as with polymorphic types, but with additional constraints that constrain the actual overloading types. The paper I reference covers these topics in more depth.


Document definition in information retrieval Is there common formal definition of Document in information retrieval field? In many researches authors don't define the term Document(maybe because it is evident for them). Wikipedia says "text file, document (computer science) a computer file that contains text" but it doesn't seem as common formal definition.

Do you know the common formal definition of Document, or, if not, do you know any researches where that term was defined?

For a formal definition of document in the Information Retrieval context, you can look at IR glossaries.

A common definition is:

Document:  Specific unit of retrieval (usually text). It can be a web page, an article, a book, a section or chapter.

(see for example the Glossary of the book Modern Information Retrieval by
Ricardo Baeza-Yates and Berthier Ribeiro-Neto)


How do I apply the Pumping Lemma to prove that this language is not regular? I am trying to teach myself Automata theory. I have hard time with the Pumping Lemma, so I am trying to work through examples. I stumbled upon this example, but it doesn't have steps how to solve it.
I would appreciate a clear explanation of how I would use the Pumping Lemma to prove that this language S is not regular:
$$
S = \{va^{7|v|}\text{ | }v \in \{a,b\}^*\}
$$
|v| = length of v
How do I use the Pumping Lemma to show that S is not regular?
Thanks.

Assume S is regular.
The pumping lemma says: There is a pumping length n. And if you take any string w in S with length > n, then w contains a non-empty substring in the first n symbols that can be repeated 0, 2, 3, 4, ... times, and the result is in the language. (Why is that? A regular language has a finite state machine. If that state machine has n states, then while you are processing the first n symbols, you must enter one state twice, say the state X. So you could take the symbols that took you from X back to X, and remove them, or duplicate them, or repeat them a million times, and your string would still be in the language). So w = xyz, xy has length ≤ n, y has length ≥ 1, and xz, xyz, xyyyyyyyyyz etc. are all in the language.
Take any string v with length k > n which doesn't end in a. The string w = v a^(7k) is in the language. When we split w into xyz, since the length of xy must be at most n, but v has a length k > n, we actually split into $w = xyz a^{7k}$.
The pumping lemma says that $xy^mz a^{7k}$ is in the language for every y. But for m ≠ 1, 7k is not seven times the length of $xy^mz$ so it is not in the language, therefore S is not regular.


Converting indirect recursion to direct one I want to remove left recursion in grammar:

$G = ({S, A,B,C,D}, {a,b,c},P,S)$

$S → A$

$A → Aa | Bc$

$B → B a |CD$

$C →C b | ε$

$D → Bb | a$

We see that this grammar contains direct recursion ( $A → Aa$ ) and indirect recursion ( $B → CD → D → Bb$ ). We need to remove indirect recursion and convert it into direct recursion.

The problem in this grammar is $C →  ε$ rule , so we remove epsilon rules , after that we are left with

$B → B a |CD |D$ which is another indirect recursion so we remove simple rules.

Then we can remove left recursion step by step by alghoritm.

My question is , having large grammar , finding indirect recursion may be difficult. Is there any universal way how to convert indirect recursion to direct recursion? Thanks for answers

$S\to A$

$A\to aA'|EP$

$B\to CDB'$

$B'\to AB'|EP$

$C\to bC|EP$

$D\to aD'|bC'DB'bD'$

$D'\to B'bD'|EP$

There is a standard algorithm to remove indirect left recursion check here https://en.wikipedia.org/wiki/Left_recursion#Indirect_left_recursion


For every undirected unweighted graph is every MST also a SPT I have a feeling this might be wrong an I'm looking for a counter example, however, I couldn't find one yet.. can anyone guide me in the right direction?

Counter example: V={a,b,c,d}, E={(a,b), (a,c), (a,d), (b,c)}.
A MST of this graph, rooted at a, could be: {(a,b), (a,d), (b,c)}. But this is not a SPT because the path a->c is of length 2 instead of 1 (a and c are directly connected in the original graph).


What is the depth of a complete binary tree with $N$ nodes? This question uses the following definition of a complete binary tree†:

  A binary tree $T$ with $N$ levels is complete if all levels except possibly the last are completely full, and the last level has all its nodes to the left side.

The following is an excerpt from Algorithms:

  It ($\log N$) is also the depth of a complete binary tree with $N$ nodes. (More precisely: $⌊\log N⌋$.)

Why is the above excerpt true?

† Originally defined here

Consider how a complete binary tree of height $h$ is constructed, one vertex at the root level, two at the first level below the root, four at the second level below, and so on, until  the $h^{th}$ level, which has at least one vertex, but at most twice as many as the previous level. Note that the number of vertices at each level is a power of two (excluding the last, which is a special case). Then we have:
$$
1+\sum_{i=0}^{h-1}2^{i} \leq n \leq \sum_{i=0}^{h}2^{i}
$$
Using the identity that the sum of the first $k$ powers of two is $2^{k+1}-1$ we get:
$$
1+2^{h}-1 \leq n \leq 2^{h+1}-1\\
2^{h} \leq n \leq 2^{h+1}-1
$$
and hence
$$
2^{h} \leq n < 2^{h+1}
$$

Taking the base 2 logarithm:
$$
h \leq \log n < h+1
$$
So we can conclude
$$h = \lfloor\log n\rfloor$$
As $\log n$ is bigger than $h$, but less than the next integer $h+1$.


Conditions for bipartite graph to be planar with no edges going around the vertices A bipartite graph is planar iff it has no $K_{3, 3}$ or $K_5$ minors.

I am looking for a necessary or/and sufficient conditions to allow planar drawings with no edges "going around" sets of vertices. These are drawings satisfying:

All vertices of one part are drawn on a single vertical line. Vertices of the other part are drawn on a parallel verticle line.
Edges do not intersect except at vertices.
Edges are all in the infinite strip between the two vertical lines in point 1.

For example, all drawings here except the bottom right are non-examples. The bottom-left graph can be re-drawn to satisfy the conditions by swapping the positions of Q and R. The tops two graphs cannot be redrawn to satisfy the conditions.

The top two graphs are the only obstructions I could find. My questions are:

Does this problem have a name?
Any other obstructions that I missed?
Any hints on how I can prove that these two obstructions (along with anything I missed), as minors of course, are necessary and sufficient.

Note that this is not the same as being outer-planar, $K_{2, 2}$ is outer-planar (can be drawn as a square) but it cannot be drawn to satisfy the conditions I mention above.

Your graphs are exactly the graphs of path-width $1$ or, equivalently, the forests each of whose components is a caterpillar.  Caterpillars have two relevant characterizations:

they're the trees in which there is a single path containing every vertex of degree more than $1$;
they're the trees in which every vertex has at most two non-leaf neighbours.

Lemma 1. Every caterpillar is in your class.

Proof. Let $G$ be a caterpillar and let $P=x_1\dots x_\ell$ be a longest path containing every vertex of degree $2$ or more.  Note that, by maximality, $d(x_1)=d(x_\ell)=1$. We can produce a drawing of $G$ by first drawing $P$ as a zig-zag and then adding the degree-$1$ vertices adjacent to $x_i$ between $x_{i-1}$ and $x_{i+1}$. $\Box$

Lemma 2. Every graph $G$ in your class is acyclic.

Proof. Suppose $G$ contains the cycle $x_1y_1x_2y_2\dots x_ky_kx_1$ and suppose it has a drawing of the required form. W.l.o.g., $x_2$ is above $x_1$. But then we must have $y_2$ above $y_1$ since, otherwise, the lines $x_1y_1$ and $x_2y_2$ would cross. By induction, $x_{i+1}$ is above $x_i$ for all $i\in\{1, \dots, k-1\}$ and likewise for the $y$'s. But then any line $y_kx_1$ must either leave the region between the two columns of vertices or cross every other edge in the cycle. This contradicts our assumption that the graph has a proper drawing. $\Box$

Lemma 3. Every connected non-caterpillar is not in your class.

Proof. Let $G$ be a connected graph that is not a caterpillar. If it contains a cycle, it is not in your class by Lemma $2$, so we may assume it is a tree.  If it is not a caterpillar, it must contain a vertex $x$ with distinct neighbours $y_1$, $y_2$ and $y_3$, each of which has degree at least  $2$.

Suppose we have a drawing of $G$ with the required properties.  W.l.o.g., $y_2$ is above $y_1$ and $y_3$ is above $y_2$.  Let $z\neq x$ be a neighbour of $y_2$.  The edge $y_2z$ must cross $xy_1$ or $xy_3$, contradicting our assumption that the graph has a drawing of the required form. $\Box$

Theorem. Your class of graphs is exactly the class of forests each of whose components is a caterpillar.

Proof. Let $G$ be a graph.  Clearly, $G$ is in your class if, and only if, every component is: if any component cannot be drawn as required, the whole graph cannot; if every component can be drawn as required, then the whole graph can be drawn by arranging the components one above the other.  The result now follows by Lemmas $1$ and $3$. $\Box$

Corollary. Your class of graphs is the class of graphs that do not have $K_3$ or the subdivision of $K_{1,3}$ as a minor.

Proof. These are the obstructions for path-width $1$. $\Box$

These are essentially the obstructions you found: you need $K_3$ rather than $K_4$ because the latter would admit $K_3$ into the class; the subdivision of $K_{1,3}$ is exactly your second obstruction.


When should I move beyond k nearest neighbour For many machine learning projects that we do, we start with the k Nearest Neighbour classifier. This is an ideal starting classifier as we usually have sufficient time to calculate all distances and the number of parameters is limited (k, distance metric and weighting)

However, this has often the effect that we stick with the knn classifier as later in the project there is no room for switching to another classifier. What would be good reason to try a new classifier. Obvious ones are memory and time restraints, but are there cases when another classifier can actually improve the accuracy?

kNN is useful for large data samples

However it's disadvantages are:

Biased by value of k.
Computation Complexity
Memory Limitation
Being a supervised learning lazy algorithm
Easily fooled by irrelevant attributes.
Prediction accuracy can quickly degrade when number of attributes increase.

It's usually only effective if the training data is large, and training is very fast.


Finite State Automata Within A Compiler I've read up on Finite State Automata in a lot of different books on compiler construction (two of which are actually called Compiler Construction) and I'm kind of at a loss. I understand the idea of moving from state to state and having a state that is accepted. What I don't understand is why in the world this theory is regurgitated in such an obscenely convoluted way?

If you were to tell me that the point of FSA within a compiler is for Lexical Analysis and that its purpose therein is just to go character by character and determine whether or not a word is an identifier, keyword, or other token, I would be completely confident in my understanding. Problem is that in every chapter of finite state automata I have to go over 50 pages of rigorous notation, differences between non-deterministic and deterministic finite state automata (including separate notation where Epsilon is three different things based on its styling) and a dozen or more of these graphs:

My question is this: Do I need to understand more than this to write a Compiler? Is there something unique about FSA that I'm just completely missing? Or is this just an over complication of a simple concept in regards to creating a compiler?

What you have asked: "Do I  need to understand more than this to write a compiler?" then answer is basically, No - but it does depend on the compiler!

You need to know a lot of theory about a lot of other things, and you could eventually ask about them too. For example, when you get to parsing you might ask "Do I need to know about top-down and bottom-up parsing". Do I need to know the difference between LL, LR, LALR parsing? Do I need to know about Chomsky Level 1 Grammars? Does it matter who Noam Chomsky actually is? Do I need to be able to know how to parse ambiguous languages? Do I need to know about data-flow in optimisation, do I need to know about flow-graphs? Do I need to know about machine architecture? Do I need to know about both register based machine code and stack based machine code?

Just so many things that one could question the need for!

You can write some kind of compiler without knowing any of this, but you wouldn't be fully equipped with all the background knowledge to be able to write any compiler!

If your task was to write a very straightforward compiler for a straight forward language then you can get away without knowing a lot of the background theory. There are some class exercises like that. If your jobs was as a compiler writer then you might be expected to be able to do a bit more.

The next part of your question to address are the textbooks you have used. Most of the textbooks are written for use on undergraduate Computer Science courses. In many/most those courses the background theory behind the practice of writing compilers is included because that is what most course curricula need. This then permits the students to use their wider knowledge to implement compilers for the as-yet-to-be-specified languages to solve the problems of the future. If you could only tackle the simple subset problems from introductory classes that did not require thinking outside the box you knowledge would be rather useless; or rather only useful for class credit, but not much beyond.

I hope that gives the view of a compiler writer and computer scientist. My students sometimes ask the same questions.


The optimized numbers of variables and clauses to encode a graph coloring problem in CNF Problem Statement

Given a finite graph $G = \langle V, E\rangle$, consisting of vertice set $V$ and edge set $E$, and a finite set of colors $C$, a problem instance of graph coloring is to assign each vertex $v \in V$ a $\text{color} (v) \in C$ such that $\forall \langle v, w\rangle \in E, \text{color}(v) \not= \text{color}(w)$. Now we encode an instance of graph coloring problem into a CNF (conjunctive normal formula) $F$.

  Note: The word "encode" means that we'll know a graph coloring problem if a CNF is given, and also will know a CNF if a graph coloring problem is given.

What is the minimal number of propositional variables in $F$?
What is the minimal number of clauses in $F$?

Original Version

A solution to a graph coloring problem is an assignment of colors to vertices such that no two adjacent vertices have the same color. Formally, a finite graph $G = \langle V, E\rangle$ consists of vertices $V = \{v_1, \cdots, v_n\}$ and edges $E = \{ \langle v_{i_1} , w_{i_1} \rangle , \cdots , \langle v_{i_k} , w_{i_k} \rangle \}$. The finite set of colors is given by $C = \{c_1, \cdots , c_m \}$. A problem instance is given by a graph and a set of colors: the problem is to assign each vertex $v \in V$ a $\text{color}(v) \in C$ such that for every edge $\langle v, w\rangle \in E$, $\text{color}(v) \not= \text{color}(w)$. Clearly, not all instances have solutions.

Show how to encode an instance of a graph coloring problem into a PL formula $F$. $F$ should be satisfiable iff a graph coloring exists.

Describe a set of constraints in PL asserting that every vertex is colored.
Since the sets of vertices, edges, and colors are all finite, use notation such
as “$\text{color}(v) = c$” to indicate that vertex $v$ has color $c$. Realize that such an assertion is encodeable as a single propositional variable $P^c_v$.
Describe a set of constraints in PL asserting that every vertex has at most
one color.
Describe a set of constraints in PL asserting that no two connected vertices
have the same color.
Identify a significant optimization in this encoding. Hint: Can any constraints be dropped? Why?
If the constraints are not already in CNF, specify them in CNF now. For
$N$ vertices, $K$ edges, and $M$ colors, how many variables does the optimized
encoding require? How many clauses?

As suggested by @D.W.♦, I copy the original problem here (above is the version simplified by me). This original version is Exercise 1.6 from:

  Bradley, A. and Manna, Z. (2007). The Calculus of Computation. Dordrecht: Springer, p.34.

My Analysis

The optimized CNF within my ability is to use propositional variable $P_v^c$ to indicate that $\text{color}(v) = c$. Here we can only use at most $|V|$ colors of all colors, i.e., the number of colors in our design of propositional variables is $|V|\min (|V|, |C|)$. Then we can build a CNF: $$F_0 = \bigwedge_{v \in V} (\bigvee_{c \in C} P_v^c) \wedge \bigwedge_{v \in V} (\bigvee_{c_1 \not= c_2 \in C} (\neg P_v^{c_1} \vee \neg P_v^{c_2})) \land \bigwedge_{c \in C \\ \langle v, w\rangle \in E} (\neg P_v^c \vee \neg P_w^c)$$

In this variable, there're $|V| \min (|V|, |C|)$ propositional variables and $2|V| + |C||E|$ clauses.

I failed to prove $F_0$ is the CNF with neither the least propositional variables nor the least clauses. Is there an another CNF $F'$ with less propostional variables or less clauses? How to find the minimal number of propositional variables and clauses of legal CNFs?

The problem statement needs to be specified more precisely to be meaningful.

If I'm being pedantic, I would say that the minimum number of propositional variables is zero: you can solve the graph coloring problem (taking exponential time if necessary), then either use the formula $\text{True}$ or $\text{False}$ according to whether the graph is $C$-colorable or not.  I suspect this isn't what you're looking for, so you probably need to define the problem statement more carefully to be able to answer the question in a useful way.  For instance, perhaps you need to specify exactly what properties you want $F$ to have.


In most locality sensitive hashing implemensions of SimHash, why is the cosine distance used and not the euclidean distance? In Chapter 3 of Mining of Massive Datasets, the basis of locality sensitive hashing is explained. They notably mention simhash for the cosine distance, where random hyperplanes are generated, and for each hyperplane, the projection of the vector to be hashed onto the hyperplane's normal is used for hashing the vector. They highlight that to instead measure euclidean distance, one can involve the use of a value $a$ as a segment length, used to split all hyperplane normals into some number of $a$-length segments. For each hyperplane, the segment into which the vector's projection falls into is used as its hash output. Hence the concatenation of this operation on each hyperplane generates a hash.

Yet a number of implementations, including what seems to be one of the most authoritative (falconn), do not use segments at all, and instead simply do a binary output depending on which side of the hyperplane the projection falls into. Why is this ? Why are segments not used ? What does the cosine distance have over the euclidean distance ?

Cosine distance is common in Information Retrieval and other text-based scenarios because text is most easily represented as high dimensional sparse vectors in the word space. A few specific advantages of cosine distance over Euclidean distance are:

it is fast and simple - particularly, since vectors are sparse, only dimensions present in both vectors need be considered (if the vectors are pre-normalized);
it works well for vectors with moderate overlap in support, whereas in Euclidean distance coordinates outside of the support of one vector dominate;
it tends to work well with a wide variety of techniques - for example, in your question, LSH for cosine distance is simpler than LSH for Euclidean distance;
the magnitude of a vector, which usually corresponds to the length of the document, is not useful - note that cosine distance ignores length but Euclidean distance doesn't;
it is well-studied so it has momentum.


General Intelligence Utility Function I was watching the AI Stop Button Problem from Computerphile, and was very confused on the difference between two approaches.

Background: there is a barebones general intelligence running in the form of some robotic device. The device acts in accordance to optimize some utility function. The GI is asked to make tea, and this is the dilemma of how it will choose to press its stop button rather than make tea if the two are given the same reward, as pressing its stop button is easier and yields the same reward as making tea for the programmer.

One approach to try and get the GI to not care about the stop button is to set the reward function of pressing the button equal to what it's trying to achieve (let's say it gets 100 reward to make tea and 100 reward if the button is pressed).  Then, he explains how this will cause the robot to hit its own button immediately, because it's the same reward but easier than making tea  (explained 5 minutes in). If we tried making the button something only us humans can hit, then it would try to slap us immediately, threatening us into hitting the button, as slapping us to hit the button would also be easier and give us the same reward as getting the tea (explained 9 minutes in).

Then, at 10:00, it says that another, better approach is to define the utility function is set with an adjustment term to make the value of utility of the button being pressed and not being pressed would be, theoretically, exactly equal, so that it would be indifferent to the button being pressed.

I don't see how this second approach is different than the first approach. If, in the second approach, the utility function is defined so that the button being pressed and not pressed is equal, isn't that the same thing as giving 100 reward to make tea and 100 reward if the button is pressed? Wouldn't this supposedly better solution still cause the robot to either press its own button if possible, or slap you to threaten you to press its button? Because they both yield the same utility, but slapping or hitting its own button is easier than what it wants to achieve in life.

The difference he is making is between long-term and short-term goals. Both need to be definable, and there is obviously a mutual dependency between these two sets of goals, so you can think of pressing the red button as something that will also have to be treated within this framework. You can then imagine that if pressing the button has the same utility of your present long-term goal, that would cause the button to be pressed imediately, whereas if it had the same utility of any of your immediate and cheaper short-term goals (because it would be normalized that way), it could ideally go unnoticed, meaning that it would be made uninteresting as an action, but not as a result. He then immediately addresses the need to consider the existence of the button in long-term goal scenarios, so there's no free lunch here.

This is evidently an oversimplification made for didactic purposes. The idea is not to show exactly how difficult is the problem, but that it is more complicated than common sense would conceive.


Karp-Rabin - what is the input for the worst case time complexity? I'm trying to determine the input for the worst case time complexity of Karb-Rabin regardless of the used hash function. However, I'm seeing both of these answers on the Internet:

String "AAAAAAAA" and pattern "AAA"
String "AAAAAAAB" and pattern "AAB"

Which of these inputs would have the worst running time in Karp-Rabin? Or are they both providing the worst case running time? Thanks!

It all depends on what hash function you are using for your strings. The worst case for Rabin-Karp would be a case in which every single substring of the text has an equal hash to the pattern, therefore every single substring would be compared and the algorithm is equivalent to brute force.

The first example would be an example of this since the pattern matches in every case, therefore the algorithm would have to individually compare every substring (Assuming you are looking for every match and don't break out on the first one).

The second example would only be an example of a worst case if the hash of "AAB" matches the hash of "AAA," which is unlikely unless you have a really bad hash function. The algorithm would compare the hash of each substring of "AAA" and "AAB" and determine them to be non equal and bypass them until reaching the end where it hits "AAB" and finds and equal hash, comparing the substrings and determining them to be equal.


Show that the SAT Problem for CNF formulas with at most two occurences of each variable can be solved in polynomial time Assuming, I have an arbitrary CNF Formula in which each variable has at most two occurences, how can I proof/show that this can be solved in polynomial time?

My first thoughts so far:

because each variable has at most two occurences, the formula contains at most 2*n literals, where n is the amount of different variables, and so the amount of clauses are also at most 2*n.

Not much, that's all I have so far :/

Consider a variable $x_i$. If it appears once, or if it appears twice but in the same polarity (i.e., both times as a positive literal or both times as a negative literal), then we can set it accordingly and satisfy all the clauses that contain it (more formally, any satisfying assignment can be converted into a satisfying assignment in which $x_i$ has this value).

The remaining case is the in which $x_i$ appears once positively and once negatively, that is, there are clauses $x_i \lor C$ and $\lnot x_i \lor D$. These two clauses are logically equivalent to the single clause $C \lor D$, which no longer contains $x_i$.

In this way, we keep eliminating the variables one by one, until we either eliminate all of them (in which case the formula is satisfiable), or we reach an empty clause (in which case the formula is unsatisfiable), which happens when both $C$ and $D$ are empty in the second case.


Simple Definition of a Simple Grammar (with confusing example) This is the definition of simple grammar that I got from the book "Formal Languages and Automata" by Peter Linz.

There is a homework question that asks for a simple grammar for the language L(aaa*b + b).
This is the answer that I found.

I don't see how this could be right, or much less how there could be any answer to this question. If you go S -> aA -> aaBC -> aaaBC ... then you will get infinite a's. The B->aB rule has no possibility of terminating. Is there something I am missing or is the answer to this question just wrong? If it is wrong then is there a possible answer and what is it?

You're right, the grammar is wrong. Everything would be fine, though, if you were able to eventually eliminate the $B$. Here's a way to do that:
$$
S\rightarrow b\mid aA\\
A\rightarrow aB\\
B\rightarrow aB\mid b
$$
The first production generates a singleton $b$ or the first $a$, the second generates the second $a$ and the third eventually generates an arbitrary number of $a$s followed by a $b$.


Conflict Driven Clause Learning backtracking clarification On the wikipedia page here it describes pretty well the CDCL algorithm (and it seems the pictures were taken from slides created by Sharad Malik at Princeton). However when describing how to backtrack all it says is "to the appropriate point". MiniSAT also uses a variant of the CDCL algorithm so I read this paper. What they seem to say is that you should backtrack until the learned clause is a unit clause. That is certainly clarification but it doesn't make sense to me. The last assignment is definitely going to be part of the learned conflict clause as far as I can tell (perhaps I am wrong here?) so when you backtrack one step you will immediately make the learned clause unit, the last assigned value will flip, and the algorithm will proceed exactly as DPLL without ever backtracking sufficiently far. Additionally the wikipedia page doesn't follow this rule, it backtracks much further as seems desirable.

How far is one supposed to backtrack?

Here's the relevant paragraph from the MiniSAT paper:

  The decision phase will continue until either all variables have been assigned, in which case we have a model, or a conflict has occurred.  On conflicts, the learning procedure will be invoked and a conflict clause producted.  The trail will be used to undo decision, one level at a time, until precisely one of the literals of the learnt clause becomes unbound (they are all $False$ at the point of conflict).  By construction, the conflict clause cannot go directly from conflict to a clause with two or more unbound literals.  If the clause remains unit for several decision levels, it is advantageous to chose [sic] the lowest level (referred to as backjumping or non-chronological backtracking).

A point you seem to have missed is that once the learned clause becomes unit due to undone assignments (backtracking), the solver doesn't stop there.  There could be other assignments before this one that have no bearing on the current conflict and experimentally it has been shown that it is better to undo these unrelated assignments also.  So the solver continues to undo assignments until the next undo would make the learned clause non-unit, i.e. it would contain more than one unassigned variable.  The solver stops here, runs unit propagation to satisfy the unit clause and then resumes the search, assigning variables normally.

Note also that the current decision variable may not be present in the learned clause.  A common strategy for a CDCL solver is to find the first unique implication point and use that variable in the learned clause.  In some cases the first UIP is the decision variable, but often it is not.


Can Real-Time Strategy games be ever solved? With the advent of BWAPI, many AI enthusiasts have been making amazing AIs that can compete against top players in Starcraft. This led me to wonder if RTS (Real-Time Strategy) games can ever be solved theoretically.

One of my colleague argues no, because RTS games are non-deterministic and stochastic. What does this mean exactly? For instance, in Starcraft you have a set of defined and limited moves (I.E: Units, buildings, economy) you can make in the game, so I don't see what can be so stochastic about the game.

It looks like there are elements of (pseudo)randomness in StarCraft.

Of course, this does not seem like a major property and you can ask for solving the game without this feature. Then you end up with a very deep game tree that probably does not have any nice mathematical property or symmetry that would help you to effectively handle it. This is where it differs from the trees that arise from mathematical games.

You can use game theory to play StarCraft well (Monte Carlo, maybe?), but unless there is some strong form of rush that would quickly cut complexity of the tree, I am skeptical about solving it.


Modification of Dijkstra's algorithm How to modify Dijkstra's algorithm, for wheel chair users, to take into account the road quality?

There are three levels of quality: $1$ for pure concrete, $2$ for partly concrete and $3$ for rough road.
Taking this into account, if there are roads $p1$: the short distance with road quality $3$ and $p2$: the long distance with quality $1$, the longer path $p2$ is chosen due to easier road difficulty.

The quality of the road is more important than the distance. If there are roads of equal quality the shorter one is chosen.

You seem to have chosen a strange metric, in that your wheelchair user apparently prefers travelling 1000km over concrete to even 1cm over gravel.

However, in general, the way to proceed is to combine your two metrics into a single metric in such a way that even the best possible score on the secondary metric can't make the algorithm prefer a path that does worse on the primary metric.

So, I'm going to assume that each edge $e$ has a quality $q_e$ and a length $\ell_e$.  The quality will be a nonnegative integer; the length can be a nonnegative real (or integer – it doesn't matter). Because Dijkstra likes to minimize, I'll take $q=0$ to be the best possible quality (in the question, you take it to be the worst, but this makes no real difference).

Any path between two vertices can't possibly have length more than $L = \sum_{e\in E} \ell_e$.  This means that, for any path of total length $\ell$, $\ell/(L+1)<1$.  We'll take the weight of the edge $e$ to be $w_e = q_e + \ell_e/(L+1)$, and use these values $w_e$ to run Disjkstra's algorithm. The point is that if a path has total quality $Q$, then it has total weight $W$ with $Q\leq W<Q+1$.  Therefore, the least-weight path is guaranteed to be one of the  best quality paths (smallest $q$-values) and, among those, it's the one of least total length.


Prove: if $\delta_D(q0, w) = p$ then $\delta_N(q0, w) = {p}$ In my textbook, it presents the theorem, "A language L is accepted by some DFA if and only if l is accepted by some NFA". My textbook explains that the "if" portion of the proof is given by the subset construction and theorem if $D=(Q_D, \sigma, \delta_D, {q0}, F_D)$ is the DFA constructed from NFA $N=(Q_N, \sigma, \delta_N, {q0}, F_N)$ by the subset construction, then L(N) = L(D).

However, it leaves it up to the reader to prove the "only if" portion - essentitally, if $\hat\delta_D(q,a) = p$ then $\hat\delta_N(q,a) = {p}$. It suggests that we mu prove this by induction on $|w|$.

I understand how to complete the basis part of this inductive proof, I think.

If w is the empty string, then
$$\delta_D(q,\epsilon) = q$$ and
$$\delta_N(q,\epsilon) = {q}$$
by definition of the extended transition function.

However, I'm lost as to how to finish the proof. I've come up the starts of something, but I don't know if I'm even in the right direction:

Assume the statement is true for strings shorter than y and break y into $xa$ where $a$ is last symbol of $y$ and x is the string of symbols before a.

$\delta_N(q_0, y) = \bigcup\limits_{i=1}\delta_n(p_i, a)$

$\delta_D(q_0, y) = \delta(\hat\delta(q_), x), a)$

For the full proof we should give the definition of the automata: $N = (Q, \Sigma, \delta_N, q_0, F)$ is the original NFA. We yield a DFA via subset or powerset construction: $D = (2^Q, \Sigma, \delta_D, \{q_0\}, \{P \subseteq Q \mid F \cap P \neq \varnothing\})$, with $\delta_D(P, a) = \{q \in Q \mid \exists p \in P. q \in \delta_N(p, a)\}$.

Now for the induction:
Base case: $\hat{\delta}_D(\{q_0\}, \varepsilon) = \{q_0\}$ by definition and $\hat{\delta}_N(\{q_0\}, \varepsilon) = \{q_0\}$.
Induction step: Let the statement be true for all $w \in \Sigma^n$, i.e. we land in some set $P \subseteq Q$ (which is a state in $D$). Consider some word $wa \in \Sigma^{n+1}$: $\hat{\delta}_D(\{q_0\}, wa) = \delta_D(\hat{\delta}_D(\{q_0\}, w), a) = \delta_D(P, a) = P^\prime$ with $P^\prime$ as given in powerset construction. By induction hypothesis we have that $\hat{\delta}_N(\{q_0\}, w) = P$ and $\hat{\delta}_N(\{q_0\}, wa) = \{q \in Q \mid \exists p \in P. q \in \delta_N(p, a)\} = P^\prime$.

Original answer for the other direction of the proof

I think you are overcomplicating things here. What you want to show is that if there is a language $L$ recognized by some DFA $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$, then there is an equivalent NFA. From your post I assume, your textbook defines NFAs with transition functions $\delta^\prime\colon Q \times \Sigma \to 2^Q$ (an other possible way would be transitions relations $\Delta \subseteq Q \times \Sigma \times Q$).

So, given DFA $\mathcal{A}$, you can just define the NFA $\mathcal{A}^\prime = (Q, \Sigma, \delta^\prime, q_0, F)$ with $\delta^\prime(p, a) = \{\delta(p, a)\}$ for all $p \in Q, a \in \Sigma$, i.e. always map to the singleton with the only possible state that the DFA would reach (i.e. the transition graph is the same). It is obvious that $\mathcal{A}^\prime$ recognizes the same language as $\mathcal{A}$.

In summary, you may say that DFAs are just NFAs where the transition function maps each state and symbol to a singleton (or rephrasing for transition relations: DFAs are just NFAs where the transition relation ist total and functional).


What's the point of Subnet Masks? I'm having trouble understanding the point of Subnet Masks.

I was reading a nice article on Tech-FAQ on the topic, but it has left me a bit confused.

When I first heard about Subnets, it was explained to me that these are small independent networks connected to the main internet at one point. For example in an office building there would be a subnet for the thousand computers there, instead of wasting a thousand regular IP addresses.

However, from this article it seems a subnet is a collection of computers with similar IP addresses and a subnet mask is used to describe which bits are the ones in range of your subnetwork.

Example from the article:

So what's the point of this? We still don't save IP addresses and if I want to contact Dave at Company X and Bill at the same Company X I still have to send messages to 105.23.44.89 and 105.23.44.90.

How do subnets make life any easier or contribute anything?

The main benefit is in the size of routing tables. Instead of having to store an entry for every machine on the network, you only need to store an entry for the particular subnet.

For example ISP might have X.Y.Z.W/16 and anyone sending a packet from the outside to any machine in this subnet only needs to know the route to their border. Their border router has a more fine grained view of the subnet (which is probably further split into many more subnets) and then knows which router on their network to send the packet to based on which smaller subnet it belongs to. Thus, subnets provides a level of abstraction to the OUTSIDE. Not the INSIDE which you seemed to have expected.

EDIT: Here's a simplified example. Assume that some large ISP has the network 1.0.0.0/8. Within this large network there are two smaller networks 1.0.1.0/24 and 1.0.2.0/24. To reach a system on either of the two smaller networks a system outside of 1.0.0.0/8 only needs to know the address of the border router of 1.0.0.0/8. Once the packet reaches the router managing 1.0.0.0/8, that router will know how to get to 1.0.1.0/24 or 1.0.2.0/24. Finally, your home router does not even need to know the address of the router of 1.0.0.0/8. It will just blindly send all your packets to a router on your home ISP assuming that this larger router will know how to get to 1.0.0.0/8 (this is what's typically called the default route/gw).

Here's a way to think about this. Think about being on a train station and having to get from city A to B. When you look at the map at the train station in city A it will tell you what trains to take to get to city B. However, that map will not tell you how to get you to your final destination in city B. However, in city B you can probably find a more detailed map that will tell you how to get you to your final destination within city B, but you don't need to have access to that map while still in city A.


how to prove the following is a bijection? I have a translation function which translates $\lambda$-terms to another representation let me call it $G_\lambda$, as follows.

$\chi(x)$               $=$    $ X^2$       if  $ x \notin \Gamma$

$\chi(x)$               $=$    $X$        if $ x:X \in \Gamma $

$\chi(\lambda x.t_1)$   $=$    $abs(X^1,\chi(t_1))$ and do $\Gamma,x:X^1$

$\chi(t_1 \, t_2)$      $=$    $app(\chi(t_1),\chi(t_2))$

where to translate $\chi(\lambda x.t_1)$, it creates a distinct $X^1$ and add a pair $x:X$ to set $\Gamma$.

$\chi(x)$ look $x$ in $\Gamma$, so we can use already added $X^1$ as bound variable or create a distinct $X^2$ for the free variable $x$.

so, a $\lambda$-term $\lambda x.yx$ will be $abs(X^1.app(Y^2,X^1))$.

I think $\chi$ is a bijection. It is obvious that function $\chi$ maps one $\lambda$-term to one $G_\lambda$ representation, so it is injective.

My problem is that since $X^1$ and $X^2$ are created fresh, if you translate a $\lambda$-term $\lambda x.yx$  twice, then you will have two representation such as $abs(X^1.app(Y^2,X^1))$ and $abs(A^1.app(B^2,A^1))$, which are equal terms but not syntactically same.

But how can i prove from $G_\lambda$ to $\lambda$-term is a surjective?

One option could be adding more parameters to $\chi$ so to make both $\Gamma$ and a fresh name source $\phi \in {\sf Names}^\infty$ explicit:

$$
\begin{array}{l}
\chi(\Gamma, x, X;\phi) = X \mbox{ if } x \not\in\Gamma
\\
\chi(\Gamma, x, \phi) = X \mbox{ if } x:X \in\Gamma
\\
\chi(\Gamma, \lambda x. t, X;\phi) = abs(X, \chi(\Gamma;x:X, t, \phi))
\\
\chi(\Gamma, t_1 t_2, \phi) = app(\chi(\Gamma, t_1, \phi^1),\chi(\Gamma, t_2, \phi^2))
\\
\qquad \mbox{where } \phi = \phi^1_0 \phi^2_0 \phi^1_1 \phi^2_1 \phi^1_2 \phi^2_2 \ldots
\end{array}
$$

You can then state a form of injectivity as
$$
\chi(\Gamma, t_1, \phi) = \chi(\Gamma, t_2, \phi) \implies t_1 = t_2
$$
and surjectivity as
$$
\forall T.\ \exists \Gamma, t, \phi.\ \chi(\Gamma, t, \phi) = T
$$

Note that some stronger forms of injectivity do not hold. E.g.
$$
\chi(\Gamma_1, t_1, \phi) = \chi(\Gamma_2, t_2, \phi) \implies \Gamma_1 = \Gamma_2 \land t_1 = t_2
$$
is false since
$$
\chi(x:X,x, \phi) = \chi(y:X,y, \phi) \land x:X \neq y:X
$$
Similarly, this does not hold:
$$
\chi(\Gamma, t, \phi_1) = \chi(\Gamma, t, \phi_2) \implies \phi_1 = \phi_2
$$
since only a finite portion on $\phi$ is needed by $\chi$.


Remove elements that appear m times I need to come up with an algorithm that iterates through an array and if any element appears m times, then the array needs to be modified so that it only appears min(2, m) times. For example, if A = [2, 2, 2, 3, 4, 4, 5, 5, 5] and m = 3, A = [2, 2, 3, 4, 4, 5, 5]. It is easy to do with extra space or nonlinear time but I want to know how to do it in O(n) time and space. The array is already sorted.

It is apparently a variant of the "remove all duplicates of a sorted array" problem, but the O(n) algo for that works because it finds all distinct elements and inserts them one by one. In the problem above, you can't do that because you need to check how many times the particular element occurred.

I've tried the following algorithm:

def variant2(arr, m):
    vacant = 1
    for i in range(1, len(arr)):
        if not arr[i] == arr[vacant - 1]:
            if i - vacant + 1 == m:
                vacant += min(2, m) - 1
                arr[vacant] = arr[i]
                vacant += 1

    temp = arr[:vacant][:]
    return temp

but this doesn't work as the overwriting of the "vacant" index will cause an element that wasn't duplicated before to be duplicated. For example, A = [2, 2, 2, 3, 4, ...] with m = 3 will become A = [2, 2, 3, 3, 4....].

I don't really understand your problem, so here is how you can solve a similar problem: instead of removing duplicated, we want each element to appear at most twice. In other words, if an element appears in a run of length $\ell$, we replace it with a run of length $\min(\ell,2)$. Suppose that the array is $A_1,\ldots,A_n$.

Assign $\mathrm{curr} \gets A_1$. This variable will store the value being repeated in the current run.
Assign $\ell \gets 1$. This is the length of the current run.
Assign $\nu \gets 1$. This is the length of the "new" array.
Loop over the values $2 \leq i \leq n$:

If $A_i = \mathrm{curr}$, increase $\ell$ by 1.
If $A_i \neq \mathrm{curr}$, let $\mathrm{curr} \gets A_i$, and set $\ell \gets 1$.
If $\ell \leq 2$, insert the new element: increase $\nu$ by 1, and assign $A_\nu \gets \mathrm{curr}$.

Return $A_1,\ldots,A_\nu$.

You can prove by induction that $\nu \leq i$, and so information is erased only after it is read.

A more challenging task is: "If an element appears in a run of length $\ell \geq m$, replace it with a run of length $2$". In other words, we replace a run of length $\ell$ with a run of length $2$ whenever $\ell \geq m$ (assuming $m \geq 2$). We can accomplish this using a similar strategy:

Assign $\mathrm{curr} \gets A_1$. This variable will store the value being repeated in the current run.
Assign $\ell \gets 1$. This is the length of the current run.
Assign $\nu \gets 1$. This is the length of the "new" array.
Loop over the values $2 \leq i \leq n$:

If $A_i = \mathrm{curr}$, increase $\ell$ by 1.
If $A_i \neq \mathrm{curr}$, let $\mathrm{curr} \gets A_i$, and set $\ell \gets 1$.
If $\ell < m$, insert the new element: increase $\nu$ by 1, and assign $A_\nu \gets \mathrm{curr}$.
If $\ell = m$, remove $m-2$ occurrences of $\mathrm{curr}$: decrease $\nu$ by $m-2$.

Return $A_1,\ldots,A_\nu$.


Proving $a^{2+n}a^{n}$ is regular using the Pumping Lemma So I'm trying to practice (and learn, clearly) use of the Pumping Lemma, and this is my current equation. It's clearly regular- it can be simplified:

$a^{2+n}a^{n} = a^{2+2n}$ and from there it's fairly easy to derive the regular language $aa(aa)*$

However, I'm trying to explicitly solve this through the Pumping Lemma- but clearly doing something wrong. This is my process (assuming language $A$, string $s$ in $A$, pumping length $p$):

First take $s = aaaa$ for $n = 1$ (simple case).

Take $p = 2$, and so $xy$ must equal $aa$ to fit $|xy| \leq p$ and $|y| \gt 0$ , giving $x = a, y = a, z = aa$.

Finally insert into the equation $xy^{i}z \in A$ with a trivial value of $i \geq 1$ - $xy^{2}z$. This gives a result of $aaaaa$.

And that's the problem. $aaaaa$ is not a member of the language  $a^{2+n}a^{n}$. Is there a step I'm missing here or a wrong assumption?

Thanks. And apologies for yet another pumping-lemma question.

Noooooo!

Usage of the pumping lemma to prove regularity is remarkably rare, and certainly won't happen with a direct application.

Let's review the formal statement, with particular emphasis on the quantifiers:

$$\forall \ L \subseteq \Sigma^* ( \ L \ \text{is regular} \Rightarrow  \exists \ p \ge 1 \ \ \forall \ w \dots \ \ \exists \ x, y, z \dots \ \ \forall \ i \dots \ )$$

Two notable observations are that being regular is part of the hypotheses and that nothing is said about the converse, which is in fact false (a number of classical counterexamples can be found in literature).

In other words, even if you managed to somehow prove the $\exists \forall \exists \forall$ block, it still wouldn't say anything about the regularity of $L$. The way the pumping lemma is normally used is in its contrapositive form. You may recall from basic logic that $(p \rightarrow q) \rightarrow (\neg q \rightarrow \neg p)$. Using that principle, we can derive the following logical consequence:

$$\forall \ L \subseteq \Sigma^* ( \ \forall \ p \ge 1 \ \ \exists \ w \dots \ \ \forall \ x, y, z \dots \ \ \exists \ i \dots \Rightarrow L \ \text{is }\textbf{not }\text{regular} \ )$$

Notice how this is a tool to prove non-regularity, and that, even there, nothing can be said about the converse.

I'm afraid your attempt of proof is just entirely misguided.


Lemma R of section 3.2 (The Art of Computer Programming) In "The Art of Computer Programming" by Donald Knuth, the proof of lemma R starts with the assumption that $\lambda = p^e$ which means:
$$\left({a^{p^e}-1\over a-1}\right)\equiv 0\pmod{p^e}$$
The above condition leads to:
$$a\equiv1\pmod{p^e}\quad(1)$$
Knuth also considers the case when $p=2$ and $a\equiv3\;(\operatorname{mod} 4)$.We then have:
$$(a^{2^{e-1}}-1)/(a-1)\equiv 0\pmod{2^e}$$
Or:
$$a^{2^{e-1}}\equiv a^{2^e}\pmod{2^e}$$
He then writes:

  These arguments show that it is necessary in general to have
  $a=1+qp^f$,where $p^f>2$ and $q$ is not a multiple of $p$, whenever $\lambda=p^e$

I have two questions here:

Why would we need to consider the case when $p=2$ and $a\equiv3\pmod4$?
What proves $a=qp^f+1$?

In "The Art of Computer Programming" by Donald Knuth, the proof of lemma R starts with the assumption that $\lambda = p^e$ which means:
  $$\left({a^{p^e}-1\over a-1}\right)\equiv 0\pmod{p^e}$$
  The above condition leads to:
  $$a\equiv1\pmod{p^e}\tag 1$$

If you read more carefully, that condition does not lead to formula (1). It only leads to
$$a\equiv1\pmod{p}\tag{2 }$$
In the case of $p=2$, the above condition is $$a\equiv1\pmod{2}\tag{3 }$$
which falls short of $$a\equiv1\pmod{4}\tag{4 }$$
That is why Knuth has to exclude the case of $a\equiv3\pmod{4}$ before asserting the formula (4).

  What proves $a=qp^f+1$, where $p^f > 2$?

Formula (2) implies $a=qp^1+1$ for all $p>2$, where $p^1=p>2$ in.  Formula (4) implies $a=q4+1$ when $p = 2$, where $4=2^2>2$.


Checking whether a digraph on $n$ vertices contains exactly $10\sqrt{n}$ strongly connected components in NL I am studying now for a test in my complexity course. When I solved previous exams I saw the following question: Prove that the language $L$ of all directed graphs on $n$ vertices that contain exactly $10\sqrt{n}$ strongly connected components is in $NL$.

We saw in class that checking whether a directed graph contains exactly $C$ strongly connected components is in $NL$ for any fixed $C$, but I thought about this question the whole day and I absolutely have no idea how to do it in $NL$ when then number of SCC required is $10\sqrt{n}$. In the test this question was worth 20 points, so it shouldn't be too hard so I thought that maybe I am missing something important.

Hint: Suppose $C_1,\ldots,C_\ell$ are the connected components and $v_i$ is the minimal vertex in $C_i$. Suppose further that $v_1 < v_2 < \cdots < v_\ell$. Show how to certify the fact that this data is correct in NL by keeping at most two of these indices at a time.

Here are some more details for a slightly simpler problem: verifying whether an undirected graph contains exactly $10\sqrt{n}$ connected components. We keep a counter $k$ of vertices accounted for. Suppose the vertices are numbered $1$ to $n$, and for $t$ going from $1$ to $10\sqrt{n}$, do the following:

Guess a vertex $v_t > v_{t-1}$ (where $v_0 = 0$).
For all $v < v_t$, verify that $v$ is not connected to $v_t$.
For each $v \geq v_t$, guess whether $v$ is connected to $v_t$ or not, and verify the guess; for each vertex connected to $v_t$, increase $k$.

If at the end $k = n$ then all vertices are accounted for, and the graph contains exactly $10\sqrt{n}$ connected components.

I leave the straightforward modification that solves the actual problem to the reader.


Longest path in a strongly connected component So if we assume that we have some strongly connected component G with n vertices. I would like to find the length of the longest path in that component.
My idea is: In a strongly connected component we can get from one vertex to every other vertex.
If we start at some vertex u then we can visit each of the remaining n-1 vertices by going from the vertex we are currently on to some adjacent vertex, setting the vertex we reach as the current one and repeating until we have no unvisited vertices left. As such the longest path always has length n-1.
Another idea is that we can run depth first search on the connected component and the highest level found will be the length of the longest path.
Intuitively these ideas make sense to me but not sure how to structure them formally or even if they are right. Could I get some guidance on this?

You won't be able to find any efficient algorithm for your problem, unless $\mathsf{P}=\mathsf{NP}$.
Consider an instance of Hamiltonian path: given a graph $H=(V,E)$ on $n$ vertices decide whether it contains a simple path of length $n-1$. This is a well-known $\mathsf{NP}$-hard problem.
Construct $G$ from $H$ by adding two vertices $x$ and $y$, the edges $(x,y)$ and $(y,x)$, and all the edges $(y,v)$ and $(v,y)$ for $v \in V$. Notice that the only strongly connected component of $G$ is $G$ itself.
There is a simple path of length $n+1$ in $G$  if and only if there is a path of length $n-1$ in $H$.
Indeed, if $P = \langle v_1, v_2, \dots, v_n \rangle$ is a path of length $n-1$ in $H$, then $\langle x, y, v_1, v_2, \dots, v_n \rangle$ is a path of length $n+1$ in $G$.
Conversely, if $P$ is a path of length $n+1$ in $G$, $P$ must have $x$ as one if its endpoints (as otherwise $x$ would have one in-neighbor and one out-neighbor in $P$, but the only in/out neighbor of $x$ is $y$, contradicting the hypothesis that $P$ is simple). Then $P$ is of the form $\langle x, y, v_1, v_2, \dots, v_n \rangle$ and $\langle v_1, v_2, \dots, v_n \rangle$ is a path of length $n-1$ in $H$.


Are there algorithms with non-convex and non-concave computational complexity? If I am not mistaken, an algorithm that runs in time $\Theta(f(n))$ also runs in $\Theta(f(n) + a\sin(bn))$ where $a,b$ are conveniently chosen constants. Therefore I believe that the computational complexity of each algorithm can be described using a function that is neither convex nor concave.

However, this seems like a made-up case. Are there some algorithms, whose complexity in $\Theta$ notation can be described only using a non-convex non-concave function, or can each complexity be conveniently transformed to a convex or concave function?

Yes, there are algorithms whose complexity in $\Theta$ can only be described using a non-convex, non-concave function. Here's one such algorithm (that serves no practical purpose, but still).

Read the length of the input $n$
If $n$ is even, halt
If $n$ is odd, loop for $n^2$ steps, then halt.

Suppose the complexity $T(n)$ of this algorithm is $\Theta(f(n))$, then there are $c,k$ so that for sufficiently large $n$, $cf(n)\leq T(n)\leq kf(n)$. Suppose (for contradiction) that $f$ is convex.

Let $n$ be odd and sufficiently large, we have that $2f(n)\leq f(n-1)+ f(n+1)$ (by concavity) and thus $\frac{2}{k}T(n)\leq\frac{1}{c}(T(n-1)+T(n+1))$. Substituting the original run time:

$$\frac{2}{k}(n+n^2)\leq\frac{2}{c}n$$

In other words, we have (up to some constants) $n^2\leq n$ which is a contradiction. So $f$ can not be convex, and by a similar argument can not be concave either.


Is it possible to implement a Neural Network using a graph data structure? I'm trying to implement a feedforward neural network using a graph.
The thing is: I haven't found any example in which is used a graph data structure.
So far the examples I've found used arrays.

Can anyone please point me in the direction of some literature on the topic or some tutorial?

Many implementations you can find out in the web are done on matrices (MATLAB for instance) since it provides a compact notation. Haykin's textbook on neural networks takes this approach. Matrices also provide a simple translation to hardware design (FPGA, ASIC, etc.). They are also more often implemented on the FPU.

If you implement a neural network in an object oriented manner, you are effectively doing what your question asks: implementing a neural network on a graph. Your neurons are then objects that have relations with each others. There are a few books that take that approach. One I can think of is an undergrad level book by Renard called Réseaux de neurones (sorry, only in French).


Principles of Programming Languages: Understanding Judgements I am taking a principles of programming languages class right now and am trying to understand the following judgement form.

n' = -toNumber(v)
------------------
-v --> n'

(Sorry, I can't post pictures yet. And Stack doesn't take LaTeX.) I think it means "n' = -v implies that -v maps to n' " or something along those lines.  I guess I really just don't know what the --> means.  In math it can either mean "maps to" or "implies" and "maps to" just made more sense.

The --> is the relation that the judgement rules are defining. It's usually pronounced "steps to" or "reduces to". You can think of this relation as the analogue of "showing your work" in algebra:

(1 + 2) * 3 --> 3 * 3 --> 9

It's used as a way of specifying the semantics of a programming language through a binary relation on programs. These kinds of semantics are called small-step semantics. Within small-step semantics, there are approaches include reduction semantics and structural operational semantics. If the program is augmented first to a "configuration" that includes extra components like environments and stores, and the relation is on these configurations instead of just plain program terms, then it's called an abstract machine semantics.

Note: Sometimes you define multiple relations and build up more complicated relations out of them, so you have different arrows.

There are other kinds of operational semantics (eg big-step semantics) and there are other kinds of semantics besides operational semantics.


What should I do if I think I wrote an algorithm that is _generally_ faster than Atkin Sieve? I've been having some fun with prime numbers. A few months ago I sat down to see if I could write something that could compete with Atkin Sieve and ended up with an algorithm that, on my local tests on my RAM-restricted computer provide results where my algorithm is either close to Atkin or it can be way faster (depending on the number of prime numbers that are being discovered).

I set up a repo with the "basic" algorithm and then another version that uses BigIntegers with an expanding array so that memory could expand as much as necessary (trying not to go on RAM-hungry implementations using Collections of BigInteger and such).

This is waaaay out of my area of expertise... let's say, I'm just having fun while learning so I think I need people that have more experience on the field of performance testing and also guidance from people with research background to guide my steps if it's worthy.

So.... how about you take a look at the code and run some local tests? Perhaps offer ideas to improve performance? Or how to know if I should turn this into a serious research project?

Branches

Master has a basic implementation that works on boolean arrays.
bigint has basically the same implementation using BigInteger (and Collections)
bigint-selfgrowing: bigint implementation using an enormous boolean array (grows as needed)
bigint-selfgrowing-lessmemory: because of the nature of the data that my algorithm handles, for every 6 numbers, only 2 of them have to be kept so I modified the arrays to not care for the other 4 numbers (which allows for a theoretical 66% memory reduction but with a noticeable performance hit... plus Atkin is still using the original Enormous Boolean Array so it's not comparing oranges to oranges anymore... still, worth a look)

All branches have 3 classes that can be used to easily run tests of the pattern sieve (my sieve) against atkin. They can get 1, 2 or 3 parameters:

Single parameter: run single test with so many numbers
Two parameters: run tests starting from first parameter up to second parameter increasing number of primes by the first parameter each run
Three parameters: Run tests from first parameter up to second parameter increasing primes by the the third parameter each run.

For each test, it will report how many ms/ns/us it took to run (depending on the java class that was called) in csv format (and will also provide a little human-readable output on stderr, just in case).

https://github.com/eantoranz/patternsieve

Thanks in advance.

PS I used an implementation of Atkin that I found on internet (credits provided on commit, code and on stderr when running) so it might not be the best out there... if you know of a better implementation, let me know.

Your PatternSieve is what is called a wheel sieve, or the wheel optimization for the SoE and is mentioned at the SoE Wikipedia page.  It's well known and used in all fast SoE implementations.  See Wheel factorization at Wikipedia for example.  Pritchard wrote some articles about it in the early 1980s (e.g. A sublinear additive sieve for finding prime numbers and Explaining the wheel sieve).  Sorenson has also written a number of good summary papers over the last 30 years (a recent paper that includes a number of references: Two compact imcremental prime sieves).  I found Quesada and van Pelt's 1996 paper A Note on the Extensions of Erathosthenes' Sieve to be useful, though I believe Sorenson's are better as a whole.

The very basic skip-evens is the first form of this, and is almost always used.  Doing mod-6 (skipping 2 and 3) is oft-used because it's simple, as seen in Robert William Hank's Python examples.  Mod-30 (skipping 2, 3, and 5) is especially popular in high performance implementations because the 8 candidates fit perfectly in one byte.  Going further is less common because of decreasing gains for quite a bit more complexity but mod-210 isn't too bad and primesieve uses that in some cases.  The modulo is the small primorial (e.g. $5\# = 30 \rm{\ and\ } 7\# = 210$), while the number of remaining numbers is $\phi(n)$ (Euler's totient), e.g. $\phi(30) = 8 \rm{\ and\ } \phi(210) = 48$.

You are looking at empirical performance.  This is certainly interesting, but Java is definitely not the best language here, and you would be best served by using properly fast comparisons.  It's fairly well known that properly optimized segmented SoE implementations are faster than the segmented SoA.  E.g. GordonBGood's long analysis.  The SoA you're using is certainly simple and easy to follow, but it's straight from the Wikipedia pseudocode which indicates it skips lots of optimizations.  Even Bernstein's convoluted but fast C implementation is slower than the fastest SoE implementations (though it is optimized enough to beat the simple ones).


Does a context switch happen when a process has terminated? I know this might sound like a newbie question but let's say we have a priority based scheduling algorithm (non-preemptive) where all processes arrive at time 0 and based on priority the order is P1, P2, P3 ...

The processes will run P1, P2, P3 without having to block one to let another one run, each processes will run until it is finished.

I am not sure here: when switching from process P1 to P2 is a context switch necessary? I know that : In computing, a context switch is the process of storing and restoring the state (more specifically, the execution context) of a process or thread so that execution can be resumed from the same point at a later time.
But since we don't save P1's state do we still need a context switch? I tend to say we do since a context switch also happens when you start up a new process from scratch which will have its own context, right?

I just want to make sure I get these things straight! Any tip would be greatly appreciated!

Yes, a context switch happens. After P1 ends the state of P2 must be loaded. The only difference with a regular context switch is that the state  of P1 does not need to be saved as it is not needed for a later restore.

Whether the OS actually applies this optimization or simply performs a regular context switch and then later discards the saved context for P1 depends on the implementation.


Parallel vs Distributed Algorithms Let me clear first that I am not asking about parallel (data/task) or distributed computing architecture. A lot had been discussed here. I am just asking a plain theoretical question. What is core principal difference between Parallel and Distributed Algorithms? Below are my under standings:

In parallel algorithms (task parallelism), A big task is divided into two or more sub tasks and each sub task is executed by one processing element (PE) parallely. All sub tasks are depended on each other. What I further understand, a parallel algorithm can be coded using OpenMP which runs on multiprocessors as well as can be coded using MPI which runs on message passing systems. on the other hand, in distributed algorithm, every processing element or node executes the same copy of algorithm. They are totally independent and exchange messages to achieve the common goal. I think distributed algorithms are designed only for multi-computer systems.

It is requested to provide parallel and distributed algorithm for a same example problem for better understanding.

An algorithm is parallel if there are several processes (tasks, threads, processors) working on it at the same time. Often the tasks run in the same address space, and can communicate/reference results by others freely (low cost).

An algorithm is distributed if it is parallel and the tasks run on separate machines (separate address spaces), one task has no direct access to the work of the others. It has to request needed data, or just wait until it is sent to it.

Yes, it is a fuzzy distinction.


What's the difference between strong consistency and sequential consistency? How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs

  ... the result of any execution is the same as if the operations of all
  the processors were executed in some sequential order, and the
  operations of each individual processor appear in this sequence in the
  order specified by its program. A multiprocessor satisfying this
  condition will be called sequentially consistent.

Spanner docs:

  Strong Consistency    All accesses are seen by all parallel processes (or
  nodes, processors, etc.) in the same order (sequentially)5 In some
  definitions, a replication protocol exhibits "strong consistency" if
  the replicated objects are linearizable.

The 5 in that doc is a link to the wikipedia page, which apparently hasn't ever cited any sources. I can't seem to find any original source for it. The "some definitions" mentioned seem to be nowhere to find online.

What's the difference between strong and sequential consistency?

In the case of the Spanner doc: it appears to be more strict than linearizability due to transactions. The difference between linearizability and sequential consistency is that latter doesn't need to preserve the real time ordering of requests.
https://jepsen.io/consistency/models/linearizable
The combination of linearizability and transactions is called strict serializability:
https://jepsen.io/consistency/models/strict-serializable
I'm not sure if spanner is supporting strict serializability.


What is a cache write miss? I'm reading Computer Organization and Design MIPS Edition 5th Edition The Hardware/Software Interface on how memory cache works. I came across the following paragraph on page 393;

The other key aspect of writes is what occurs on a write miss. We
first fetch the words of the block from memory. After the block is
fetched and placed into the cache, we can overwrite the word that
caused the miss into the cache block. We also write the word to main
memory using the full address.

I understand what a cache read miss is i.e. when the required word isn't present in the cache, but I'm having trouble understanding what a write miss is(how can we miss to write data?) and hence the subsequent paragraphs.

My understanding is that a write-miss occurs when we want to write data to a location in main memory whose data is not currently in its corresponding cache block.
This is similar to a read miss: if the cache block that a memory location is mapped to does not contain the data of that memory location (indicated by differing tags), then some other memory location also mapped to that same cache block is currently present, and a miss occurs.
Similarly, we "miss" on a write if the memory location we want to write to isn't currently "in" its corresponding cache block, but rather, some other memory location's data currently occupies it.
The important question that follows a write-miss is "do we update the cache block corresponding to the memory location we just updated with that new data, or leave the old?" Perhaps the memory-location's data already occupying that cache block is more useful or being used more frequently than what we just wrote.


quicksort invariant 3 conditions with loop invariant in studying Quicksort using the book "Introduction to Algorithms"  by Cormen, Leiserson, Rivest and Stein, they describe in order to show correctness, an invariant must hold for the 3 stages of the loop, the initialization, the maintenance and termination of the loop.

Based on the following algorithm, I don't understand properties 1 and 2 below:

Here is the algorithm I'm referencing:

Might someone help me understand conditions

1) if $p \leq k \leq i$ then $A[k] \leq x$

In the algorithm when for example, $p$ is $1$, won't $i$ be $0$.... How would this hold, since before the for loop we have i = p-1

2) if   $i + 1 \leq k \leq j - 1 $ then $A[k] > x$

In the algorithm for example, when we first enter the for loop, and j = 1, then $i$ would be 0.... I don't see how this works.

Thanks

If $p \leq k \leq i$ then $A[k] \leq x.$
  In the algorithm when for example, $p$ is $1$, won't $i$ be $0$.... How would this hold, since before the for loop we have i = p-1

Although, as you have observed, $i$ is always smaller than $p$ at the start of the loop, it might become bigger because the statement "$i=i+1$" in the loop could be executed. Once $i$ has been increased, for at least $k=p$, we have $p\le k\le i$.

Note that when $p\le i$ does not hold, i.e., when there is no $k$ such that $p\le k\le i$, the condition "if $p \leq k \leq i$ then $A[k] \leq x$" holds automatically. (Recall that the proposition "if false, then anything can happen" is always true.) To falsify that condition, we have to find an instance of $(p,k,i)$ such that $p \leq k \leq i$ but $A[k]\gt x$.

You should be able to figure out the case of the second loop invariant now.


Show that there are $(n-1)!/2$ distinct tours for a Euclidean traveling salesman problem on $n$ points? The question is to show that there are $(n-1)!/2$ distinct tours for a Euclidean traveling salesman problem (ETSP) on $n$ points.

My attempt was using induction. So I start by:

If $n=3$, then we have a triangle and there is only one tour.
Assume that there are $(n-1)!/2$ distinct tours for a ETSP on $n$ points. Prove that there are $n!/2$ distinct tours for a ETSP on $n+1$ points?

Here I proceed like this:

for each tour $t$ from the $(n-1)!/2$ distinct tours do: add one point $n+1$.
for each edge $e=\{v_i, v_j\}$ in $t$ do: remove $e$ and create two edges $e_1=\{n+1,v_i\}$ and $e_2=\{n+1, v_j\}$. We have a new tour and in total we can create $n$ distinct tours.

Since there are $(n-1)!/2$ distinct tours, we will have $n(n-1)!/2=n!/2$ distinct tours.

This gives the desired result but somehow long and complicated.

We may reason in a combinatorial way.

There are $n!$ permutations of $n$ nodes, but that overcounts the number of tours in two different ways. Since tours are closed, we may start indifferently on any of the $n$ nodes, and we may choose the direction in $2$ ways. Therefore, each tour was counted a total of $2n$ times.

This yields the desired result.


Complexity of determining spanning bipartite graph A procedure by induction to get maximum spanning bipartite graph (same vertex set as $G$ and the maximum possible number of edges) from given graph $G$:

Given a planar graph $G$, we need two disjoint sets $V_1$ and $V_2$. We define $V_2=V \setminus V_1$ where $V = V(G)$. In the following, $H$ is the bipartite subgraph with  $V(H)=V_1 \sqcup V_2$ and $E(H) = K_{V_1,V_2} \cap E(G)$ where $K_{V_1,V_2}$ is the complete bipartite graph on $V_1$, $V_2$.

Start with first $i$ vertices of $V$ in vertex set $V_{01} \subseteq V$ and then $V_{02} = V \setminus V_{01}$
In iteration $i$, let our current chosen vertex set be $V_{i1}$
If $\exists x \in V_{i1}$ such that $d_{H}(x) \lt \frac12 d_{G}(x)$, then consider the bipartite spanning graph $H'$ with $V(H') = V_{i1}' \sqcup V_{i2}'$ where $V_{i1}' = V_{i1} \setminus x$, $V_{i2}'= V_{i2} \sqcup x$, $E(H') = K_{V_{i1}',V_{i2}'} \cap E(G) $ This makes $\vert E(H') \geq E(H) \vert$. We are basically moving vertex $x$ which satisfies above property from $V_{i1}$ to $V_{i2}$.
Similarly do for $ V_{i2}$. If $\exists x \in V_{i2}$ such that  $d_{H}(x) < \frac{1}{2} d_{G}(x) $, move vertex $x$ to $V_{i1}$. Go to step 2.
Repeat until $(\forall x \in V(H))\, d_{H}(x) \geq \frac{1}{2} d_{G}(x)$
After this $V_1 = V_{i1}$ and $V_2 = V_{i2}$. We are using the property that a spanning bipartite subgraph $H$ from $G$ is maximal in terms of the total number of edges only when $H$ with $V(H) = V_{1} \sqcup V_{2}$ satisfies the property that $$(\forall x \in V(G))\, d_{H}(x) \geq \frac{1}{2} d_{G}(x)$$

Analysis of this procedure:

Could somebody help me analyze this algorithm?
Can I assume I know the degrees of the vertices in the bipartite graph $H$, in the intermediate steps?

2.1. If I can assume so, then each induction iteration has $2n$ steps. And, in the worst case, could there be $n!$ permutations of induction iteration (Any permutation of $i$ vertices is possible for the first vertex set). Is the worst-case upperbound $O(n!\times n)$?

In answer to your comment:

  By maximum spanning bipartite graph I mean same vertex set as given graph and the maximum number of edges possible. Is the complexity $O(n^3)$ correct for this algorithm? If so it would solvable in P time.

No, that problem, also known as Bipartite Edge Deletion, or Edge Bipartization, is:

  Given a graph $G = (V, E)$ and an integer $k$, is it possible to delete at most $k$ edges $E'$ such that $G' = (V, E \setminus E')$ is bipartite,

which is NP-complete.

It happens to be "equivalent" to the "vertex deletion" version of the problem, which is also known as Odd Cycle Transversal.


Clarification on "clause learning" in DPLL algorithm I am struggling to understand the idea of conflict-driven clause learning, in particular, I can not understand why the clause we 'learned' is a substantially new (i.e. the clause database does not already contain it, neither any subset of it). Here is what Knuth in his book says:

A conflict clause $c$ on decision level $d$ has the form $\overline{l} \lor \overline{a}_1 \lor ··· \lor \overline{a}_k$, where $l$ and all the $a$’s belong to the trail; furthermore $l$ and at least one $a_i$ belong to level $d$. We can assume that $l$ is rightmost in the trail, of all the literals in $c$. Hence $l$ cannot be the $d$th decision; and it has a reason, say $l \lor \overline{a}′_1 \lor ··· \lor \overline{a}′_k$.  Resolving $c$ with this reason gives the clause $c′ = \overline{a}_1 \lor ··· \lor \overline{a}_k \lor \overline{a}′_1 \lor ··· \lor \overline{a}′_k$, which includes at least one literal belonging to level $d$. If more than one such literal is present, then $c′$ is itself a conflict clause; we can set $c \leftarrow c′$ and repeat the process. Eventually we are bound to obtain a new clause $c′$ of the form $\overline{l}′ \lor \overline{b}_1 \lor ··· \lor \overline{b}_r$, where $l′$ is on level $d$ and where $b_1$ through $b_r$ are on lower levels.
Such a $c′$ is learnable, as desired, because it can’t contain any existing clauses. (Every subclause of $c′$, including $c′$ itself, would otherwise have given us something to force at a lower level.)

I can understand why the clause database has no subset of $c'$ that contains $\overline{l'}$ (because $\overline{l'}$ would have been forced (i.e. unit-propagated) at level lower than $d$), but what contradicts to the existence of clause, let's say, $\overline{b_1}\lor\overline{b_2}$?

All the literals in a conflict clause are set false by definition, else there would be no conflict.  So if the clause $\overline{b_1}\lor\overline{b_2}$ existed, one of those false literals would have caused that clause to go unit before we reached the current level, which in turn would have forced one of the $\overline{b_1}$ or $\overline{b_2}$ literals true.  But we already know that those literals must be false, so we have a contradiction.  This contradiction shows that the clause $\overline{b_1}\lor\overline{b_2}$ cannot exist.  The reasoning is the same for all clauses that are subsets of the conflict clause.


How do compilers assure stability? Suppose you need a c compiler. It would be preferable to write that compiler in a c-like language, given the complexity of a compiler of that degree. At best, the c compiler would be written in c, but that would require a c compiler to begin with. If a mistake is made in the making of one of the early iterations of compilers, it could propagate. How do compilers make sure that this doesn't happen? Obviously, no code is flawless, not even the processor is, but if you haven't somehow measured the stability, you don't even know if your compiler is stable. What assumptions are made and how is it justified? I would imagine it would be architecture-dependent too.
Edit: By stability, I mean that the code runs as intended.

It happens that compilers contain subtle errors. No blatant errors, because blatant errors would be detected and fixed.
A compiler that is itself compiled by a compiler with subtle errors will tend to have blatant errors. They will be easy to detect because they are so blatant. They will be hard to fix because these blatant errors will be produced by perfectly fine source code, so whoever wants to fix it will have a hard time finding the real problem.
The solution will be to make a compiler of sufficient quality that bugs are very rare, and extremely rare within the compiler. We also expect compiler bugs to affect very complicated code more, so the compiler writer should write code that is simple and follows common coding patterns.


Does there exist context-free grammar with words of length n^2 or n^3? Does there exist context-free grammar with words of length $n^2$ or $n^3$? I can't see any, we can produce all grammar with words of length $n$ ($S \to Se$), but then it seems to be impossible to substitute each $S$ with sequence of $S$'s of length $n$.

For a language $L$, let $N(L) = \{|w| : w \in L\}$, and let $U(L) = \{1^n : n \in N(L)\}$. Parikh's theorem shows that if $L$ is context-free then $U(L)$ is regular. In particular, since $\{1^{n^2} : n \geq 0 \}$ is not regular, no context-free language $L$ satisfies $N(L) = \{n^2 : n \geq 0\}$. In fact, no infinite context-free language $L$ even satisfies $N(L) \subseteq \{n^2 : n \geq 0\}$ (exercise).


What is difference between Hidden Markov Model and Non-deterministic Finite-State Machine? As the question implies, can you mention any difference between Hidden Markov Model and Non-deterministic Finite-State Machine? Are they different or the same?

Deterministic Finite State Machines have at most one trace for a given input. Nondeterministic Finite State Machines may have many traces for a given input. A Hidden Markov Model in some sense fits "in between" these extremes as the traces are probabilistic. With a Hidden Markov Model we do not have complete freedom to choose which trace to follow as we are governed by probabilities. A Hidden Markov Model is essentially a transducer-style Finite State Machine having outputs & transitions governed by a random process; the outputs generated at states are per a random variable model of what happens at that state, e.g., "if the weather is cloudy then 20% it will turn rainy / 80% it will turn sunny".


Regular Expressions to accept strings where every two successive 0s are followed by a 1 How do I define a Regular Expression for the language L = {w|every two successive 0s are followed by a 1} ?

I don't have any idea on how to even approach this problem, primarily because it says "every two 0s".

Take either 1, or 01, or 001 and repeat any number of times. Plus there can be a single 0 at the end.


Finding a solution to a satisfiable formula I know that it is as hard to find a solution to a SAT formula, as it is to decide it has a solution at all. See the answer to:
Is finding a solution of a satisfiability problem harder than deciding satisfiability?

Are there also families of formulas for which it is guaranteed that there is a solution, but it is hard to find one?

Absolutely, a hash function is a prime example of a function (which can be modelled by a very complex binary formula of its inputs) where it is easy to find the output given an input, but finding an input which matches an output is very hard.

But since we generated the original output we know that there must be a solution.

This construction requires the ability to forget information (the original input) however.


Are there any useful deterministic quantum algorithms for decision problems? The vast majority of known interesting quantum algorithms are probabilistic.  The only deterministic quantum algorithms that I know of (which aren't trivially equivalent to a classical algorithm) are (a) Deutsch's algorithm, in which the quantum speedup is pretty trivial, (b) the Deutsch-Josza algorithm, which solves a promise problem rather than a decision problem, and (c) this algorithm (which I found by Googling): http://arxiv.org/abs/1108.5848, which also doesn't solve a decision problem.  Are there other known examples of "interesting"/"useful" deterministic quantum algorithms, especially for decision problems?

I know that this question isn't particularly well-formulated, because which algorithms you can use depends on which set of quantum gates you have available.  Are there any interesting algorithms that use only a "realistic" set of quantum gates?  (Say, only the quantum gates that can be currently purchased on Amazon for under $10 :-) .)

There are some query complexity results that mention exact quantum algorithms. See this blog post about the paper "Separations in Query Complexity Based on Pointer Functions":

  a total boolean function $g$ on $n$ variables that has [...] exact quantum query complexity [...] $Q_E(g) = \tilde O(\sqrt n)$.

More generally, the complexity class you're looking for is called EQP: Exact Quantum Polynomial-Time.

EQP is not a very "nice" complexity class, especially compared to BQP. There's two big reasons for that:

Theoretical-side, there's no universal set of gates. EQP circuits may require a gate with irrational coefficients such as $\begin{bmatrix} \cos(10^\circ) & -\sin(10^\circ)\\ \sin(10^\circ) & \cos(10^\circ)\end{bmatrix}$, and approximations via other gates aren't allowed. So you end up with a bunch of different $\text{EQP}_{my\_favorite\_gate\_set}$s instead of a nice unified one.
Practical-side, there's no possibility of error correction. EQP lives in a world without errors, because otherwise it wouldn't be exact. Error correction is expected to be a necessity in practice, so if you care about actual implementation then you don't care much about EQP.


Term for a matching which is perfect on one side only What is a standard term for a matching in a bipartite graph, in which one part has less vertices than the other part, and the part with less vertices is fully matched (but the other part is, obviously, not fully matched)?

It is not exactly perfect, but it is "one-sided perfect", or "as perfect as it could be". What is a short term to use for this kind of matching?

Such a matching is said to saturate one of the sides.  More specifically, if $M$ is a matching of a graph $G$ and $v$ is incident to one of the edges of $M$, we say that $M$ saturates $v$.  If $A$ is a set of vertices, then we say that $M$ saturates $A$ if every vertex in $A$ is saturated by $M$.

Specifically for your case, the matching saturates the smaller of the two sides of the bipartition.


Number of Independent Sets in a tree (I've been stuck on this homework assignment for far too long)

I need to find the number of independent sets in a tree.

For example, say the set of nodes in a tree is {A, B, C, D, E}. B and C are children of A and D, E are children of B. This tree has 14 independent sets.

I assume that the algorithm will be recursive and I think that I should make each level of a tree into a linked list, so B->C and D->E, but more than that I'm stumped.

Would grealy appreciate help.

Hint: Compute recursively the number of independent sets (a) containing the root, (b) not containing the root.


Why do low fitness individuals have a chance to survive to the next generation? I am currently reading and watching about genetic algorithm and I find it very interesting (I haven't had the chance to study it while I was at the university).

I understand that mutations are based on probability (randomness is the root of evolution) but I don't get why survival is.

From what I understand, an individual $I$ having a fitness $F(i)$ such as for another individual $J$ having a fitness $F(j)$ we have $F(i) > F(j)$, then $I$ has a better probability than $J$ to survive to the next generation.

Probability implies that $J$ may survive and $I$ may not (with "bad luck"). I don't understand why this is good at all? If $I$ would always survive the selection, what would go wrong in the algorithm? My guess is that the algorithm would be similar to a greedy algorithm but I am not sure.

The main idea is that by allowing suboptimal individuals to survive, you can switch from one "peak" in the evolutionary landscape to another through a sequence of small incremental mutations. On the other hand, if you only are allowed to go uphill it requires a gigantic and massively unlikely mutation to switch peaks.

Here is a diagram showing the difference:

Practically, this globalization property is the main sellling point of evolutionary algorithms - if you just want to find a local maxima there exist more efficient specialized techniques. (eg., L-BFGS with finite difference gradient and line search)

In the real world of biological evolution, allowing suboptimal individuals to survive creates robustness when the evolutionary landscape changes. If everyone is concentrated at a peak, then if that peak becomes a valley the whole population dies (eg., dinosaurs were the most fit species until there was an asteroid strike and the evolutionary landscape changed). On the other hand, if there is some diversity in the population then when the landscape changes some will survive.


How to deal with arrays during Hoare-style correctness proofs In the discussion around this question, Gilles mentions correctly that any correctness proof of an algorithm that uses arrays has to prove that there are no out-of-bounds array accesses; depending on the runtime model, this would cause a runtime error or access to non-array elements.

One common technique to perform such correctness proofs (at least in undergrad studies and probably in automated verification) is by using Hoare logic. I am not aware that the standard set of rules containes anything relating to arrays; they seem to be restricted to monadic variables.

I can imagine adding axioms of the form

$\qquad \displaystyle \frac{}{\{0 \leq i \lt A.\mathrm{length} \land {P[A[i]/E]} \}\ A[i] := E;\ \{P\}}$

However, it is not clear to me how you would deal with an array access on the right hand side, i.e. if it is part of a complex expression $E$ in some statement $x := E$.

  How can arrays accesses be modelled in Hoare logic so that the absence of invalid accesses can and has to be proven for program correctness?

Answers may assume that we disallow array elements to be used in statements other than $A[i] := E$ or as part of some $E$ in $x := E$ as this does not restrict expressiveness; we can always assign a temporary variable the desired value, i.e. write $t := A[i];\ \mathtt{if} ( t > 0 ) \dots$ instead of $\mathtt{if} ( A[i] > 0 )\dots$.

Your axiom is not really an axiom, it's missing hypotheses. Simple presentations of Hoare logic manipulate formulas of the form $\{P\} C \{P'\}$ where $P$ and $P'$ are logical formulas and $C$ is a command. You do need to ensure that $C$ is well-formed. In simple languages such as the ones often used for a first introduction to Hoare logic, well-formedness is syntactic: it's typically a matter of checking that $C$ conforms to a context-free grammar, and possibly that the free variables are within a permitted set. If the language includes constructs that have a semantic correctness, such as accesses to array elements, you need to add hypotheses to express this semantic correctness.

Formally, you can add judgements to express the correction of expressions and commands. If expressions have no side effects, they need no postconditions, only preconditions. For example, you can write well-formedness rules such as
$$
\dfrac{\{P\} \;\; E \text{ wf}}
      {\{P \wedge 0 \le E < \mathrm{length}(A)\} \;\; A[E] \text{ wf}}
\qquad
\dfrac{\{P\} \;\; E_1 \text{ wf} \qquad \{P\} \;\; E_2 \text{ wf}}
      {\{P\} \;\; E_1 + E_2 \text{ wf}}
$$
and only allow well-formed expressions in commands:
$$
\dfrac{\{P[x\leftarrow E]\} \;\; E \text{ wf}}
      {\{P[x\leftarrow E]\} \;\; x := E \{P\}}
$$

A different approach is to treat all expressions as well-formed, but to make any expression involving an ill-formed calculation have a special value $\mathbf{error}$. In languages with run-time bounds checking, $\mathbf{error}$ means “this program raised a fatal exception”. You would then keep track of whether a program errored out through a logical predicate $\mathbf{Error}$; a program is only valid if you can prove that its postcondition implies $\neg\mathbf{Error}$.
$$
\dfrac{}
      {\{P[x\leftarrow E]\} \;\; x := E \;\; \{P \vee \mathbf{Error}\}}
\qquad
\dfrac{P[x\leftarrow E] \implies E \not\rightarrow \mathbf{error}}
      {\{P[x\leftarrow E]\} \;\; x := E \;\; \{P\}}
$$

Yet another approach is to consider a Hoare triple to hold only if the program terminates correctly. This is the usualy approach for nonterminating programs: the postcondition holds when the command terminates, which might not always happen. If you treat run-time errors as non-termination, you sweep all correctness issues under the hood. You will still need to prove the correctness of the program somehow, but it need not be in Hoare logic if you prefer some other formalism for that task.

By the way, note that expressing what happens when a compound variable such as an array is modified is more involved that what you wrote. Suppose $P$ was, say, $\mathrm{IsSorted}(A)$: the substitution $A[i]\leftarrow E$ would not change $P$, yet the assignment $A[i] \leftarrow P$ might invalidate $P$. Even if you restrict the syntax of predicates to only talk about atoms, consider the assignment $A[A[0]-1] := A[0]$ under the precondition $A[0] = 2 \wedge A[1] = 3$: you cannot make a simple substitution to obtain the correct postcondition $A[0] = 1 \wedge A[1] = 1$, you need to evaluate $A[0]$ (which can be difficult in general, since the precondition might not specify a single possible value for $A[0]$). You need to perform the substitution on the array itself: $A \leftarrow A[i\leftarrow E]$. Mike Gordon's lecture notes have a good presentation Hoare logic with arrays (but without error checking).


The most frequent integer value from set of intervals What is the fastest way to get one of the value from set of intervals which occurs most frequently?

For example if I have interval (0, 3) and (2, 4) the most frequent value can be 2 or 3.

It seems to me that the answer to your question will have a technique similar to this - https://stackoverflow.com/a/9676296/477522


Converting Moore to Mealy When first Node has Output This is a homework question, which I am able to do, except my teacher failed to mention what to do when the very first node has a 1 output. I've looked through online examples, and I'm sure this has a very simple answer, but I cannot figure out what the convention would be.
On the left, we have a Moore Machine. It's first node outputs 1. Ok, no problem.
But when I convert this to a Mealy, the only time q1 outputs 1, is when being traversed from q2.

But if it's the first node, it should be outputting when the whole thing begins (on lambda) AND when being traversed from q2.
I had two theories, one-- I make a new beginning node, or, I actually put λ/1 on the entry arrow/line (which I have not seen done in any example). But I'd rather not guess my way through this otherwise simple operation.

Answering my own question like a silly person:
Ok, I learned what I was missing. A Mealy Machine cannot handle a lambda as I thought it could. As a result, my question has no real answer. Things do NOT output at the first node. Only the first traversal after the first node has any real meaning.


Is reduction symmetric? I was watch this lecture https://youtu.be/moPtwq_cVH8?t=2895, and at this point he says a lot about reductions, take a problem and reduce to another problem. From what I could understand this is a symmetric relation, if I can reduce A to B, then I can reduce B to A. This seems pretty intuitive to me but I don't have a formal proof, is there any (for beginners would be better) material on this proof?
Still on this lecture, from what I could understand we have problems that are known to be NP-hard, if I have a problem that I don't know what is but I can reduce to NP-hard problem then it must be NP-hard.
Another question, supposing that reduction is symmetric if any NP problem can be reduced to P problem that would prove that P = NP. Or in reverse, if I have a known NP problem and I prove it can't be reduced to a P problem then this would prove that P ≠ NP.
Is my reasoning right? I'm not trying to prove anything just want to make sure that I understand the reduction implications because this seem powerful tool for day reasoning on solving problems in general.

Reduction is not symmetric. Intuitively, if $A$ reduces to $B$, then $B$ is at least as hard as $A$. Just as the usual comparison is not symmetric — for example $3 > 2$ but $2 \not> 3$ — reduction, which is a (partial) order of hardness, isn't symmetric.
For example, SAT reduces to the halting problem, but the halting problem doesn't reduce to SAT.


"Batch" partial sorting algorithm I'm looking for an existing algorithm that would ensure that the first k elements after sorting are the top k elements but not necessarily in the right order.
To put it differently, I would like an algorithm that acts like C++ std::partial_sort but takes advantage of the fact that I don't need the first elements ordered.
If there's no such thing yet, I'm planning on studying again existing algorithms and try to find out which one would be the best candidate to tweak. Any lead would be welcome.

What I was looking for is a selection algorithm that will select the k-th element.
As mentioned in comment, running then a simple partition algorithm if needed will then provide the expected result.
The reference seems to be the quick select algorithm while the reference implementation points to introselect as implemented in Numpy's partition function or C++ nth_element function.