Symmetric protocols for consensus All the consensus algorithms that I've seen always depend on having a leader elected with all queries directed at the leader (assuming that we're not OK with getting back stale data). Are there any efficient algorithms that are completely symmetric, i.e. which do not elect a leader and therefore allows querying any server in the cluster?

Since a given server doesn't crash very often, from an engineering perspective it would seem like electing a leader is simpler because you can worry separately about what to do when the leader goes down, which would seem to allow for more modular protocol design. On the other hand, if all the queries are directed at one sever, then this server will get hammered, since in addition to all queries, it will have to send updates to all other servers in the cluster.

My questions can be phrased as follows: is dependence on a leader seen as a problem? Are there some fundamental issues with this approach in addition to problems with load? Do we have some fundamental problems when running a leaderless protocol? Do we know if there exists efficient leaderless protocols?

This paper [1] provides a consensus algorithm in a model where, in each round, each node can query 2 randomly chosen nodes and update its own value accordingly. As this is essentially a balls-into-bins scenario, the load balancing will be very good. It is shown that this "converges" to a consensus within $O(\log n)$ rounds even if an omniscient adversary corrupts up to $O(\sqrt{n})$ values of the nodes in each round.

I would say the main reason why many protocols have a leader is for having a coordinator that orchestrates the progress of the protocol. Note that most classic work on consensus focuses on achieving the best possible fault-tolerance, whereas load balancing as not always a primary concern.

[1] Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, Christian Scheideler: Stabilizing consensus with the power of two choices. SPAA 2011: 149-158
http://www.cs.ox.ac.uk/people/leslieann.goldberg/papers/SelfStabilizing.pdf


Operator overloading: Java vs. Python Why operator overloading was included in Python and not in Java?
How does one decide to include or exclude operator overloading in a programming language?

It is said here that operator overloading is excluded from Java
to make the language simpler
(for programmers, language and VM developers, etc.).

I don't understand why the same explanation doesn't work for excluding it in Python?

Operator overloading is an example of syntactic sugar — a notation that doesn't give any extra power but makes programming easier. I don't know the rationale for the decisions in Java and in Python, but see below. See also this answer on stackoverflow.

First, I would like to critique the page you were linking. Let's consider the points raised there one by one.

Simplicity and cleanliness: It is claimed that operator overloading slows down the compiler and the JVM (!). This is non-sense. It's plain wrong for the JVM, since this is just syntactic sugar so it wouldn't affect the generated code at all. As for the compiler, the compiler is already equipped to parse infix operators and to resolve virtual methods, so supporting operator overloading won't make it more complex. On the flip side, operator overloading makes the Java code simpler and cleaner: compare a.add(b) to a+b.
Avoid programming errors: It is claimed that non-standard semantics for operators might confuse programmers. Compare this to C++'s use of >> and << in streams. I think this point is valid but overstated. The same point could be made with regard to other conventions. It's up to the programmers to not abuse the capabilities of the language.
JVM complexity: It is claimed that operator overloading complicates the JVM. As stated above, at the JVM level there would be absolutely no difference.
Easy development of tools: It is claimed that operator overloading complicated the design of IDEs. The answer here is very similar to the answer to the first point. The only complication with operator overloading is that you have to figure out the type of the operands, but presumably if it makes any difference you would need to do it anyway since there are also several different number types, say integer and floating point.

A point which is not raised is that operator overloading might complicate optimization since certain algebraic identities hold for numbers but not in general. This criticism is wrong for the following reason: algebraic identities cannot in general be used even for floating-point computations, since order of operations makes a difference. So the compiler needs to determine the type of the operands anyway, and could easily abstain from optimizing user defined operators.

The Python philosophy is to supply the coders with the rope to hang themselves. If you're a good coder, you will use the rope for good, say for tying your bicycle in the train, rather than to hang yourself or anybody else. Python trusts programmers more than Java, by design. See the second point above.

Let me end this answer by quoting an excellent answer to the stackoverflow question mentioned above:

  I left out operator overloading as a fairly personal choice because I had seen too many people abuse it in C++.

James Gosling. Source: http://www.gotw.ca/publications/c_family_interview.htm

  Many C++ design decisions have their roots in my dislike for forcing people to do things in some particular way [...] Often, I was tempted to outlaw a feature I personally disliked, I refrained from doing so because I did not think I had the right to force my views on others.

Bjarne Stroustrup. Source: The Desing and Evolution of C++ (1.3 General Background)


If XOR of n distinct numbers is ANDed over one of the number, the result would be zero Say we Have n distinct numbers

x1,x2,....xn

And we xor the result

xoredResult = x1^x2...^xn

And if we AND(&) with one of the number say x2
We get Zero

xoredResult & x2 = 0

Can we always claim that if the ANDed result is zero that the number is repeated ?
Can this be used to find the first repeated element in a stream of numbers ?

It doesn't work, for example if x2 = 0 then xoredResult & x2 = 0 all the time no matter what else the set of numbers contains.

Or for an other example, the set { 1, 2, 3 } xors to zero (so it ANDed by any of its members, or even anything else, yields zero) but contains no repeated elements.


What algorithm can solve the conversion engine problem? I was once asked a question, given a series of units and their ratios, such as inch, cm, gram vs pound, and a lot of potentially cryptic units and ratios, such as A, B, C, D, ... if I am given n times to do the add() to the table, and m time to do lookup() to get the conversion, such as from "mile" to "inch" and to "cm" and to "meter" if that was the originally given ratio pairs, then what is the time complexity? (Big O). (I think this is the question -- can't remember every single detail. Probably not temperature F conversion to C, because 0°F is not 0°C, while all other conversions are like 0 inch = 0 cm, meaning they can be converted by multiplying by a k factor).

Does this problem actually belong to Union-Find, and therefore can be solved by Weighted Quick Union as described by Sedgewick?  Or does it belong to any other areas in CS?

In a union-find data structure, each item is either a root or points at a parent. For us, units will be items, and each pointer to a parent will be annotated with the appropriate conversion. You can maintain this annotation while running the usual operations on the union-find data structure.

Using this annotation union-find data structure, you can implement each add() using union and each lookup() using find, with only a constant factor overhead.


Reduction — Do they work for unrelated problems? I think I understand that a P class problem is reducible to an NP class problem (P≤NP).

I´d like to understand if I need to figure out a potential algorithm which could solve the NP class problem to know if it can be used as a subroutine for a P class problem.

So for example, if I ask you if the problem from class P —sum of integers— is reducible to a problem of class NP —Clique graph problem—, how would you reply to it?

Is this a valid reduction as the more complicated Clique problem is NP and the easier problem sum of integers is a P problem even though they deal with different math branches (one being algebra and the other one being graph theory)?

If you have a problem $X$ that is in P, then you can construct a polynomial time reduction to any problem $Y$ in NP (or in 'any' other class of problems*). This is possible, as our 'reduction' is allowed to spend polynomial time on the input of $X$, so it can simply determine whether a given input $I$ for $X$ is a 'yes'-input in polynomial time and map to a trivial input for $Y$ with the same truth-value.

*: To be precise, any decision problem such that we can find at least one 'yes'-instance and one 'no'-instance, which holds for pretty much any interesting decision problem.


Is there any compiler IR paradigms other than Three Address Code and Static Single Assignment (SSA) Form? Specifically, I have tried boiling down the operations of a VM into the smallest possible standardized units and arrived at this:
allocate_stack(size)
fetch(offset_from_stack_pointer)
store(offset_from_stack_pointer)
call(index)

So you might have:
allocate_stack 6
fetch -2
store 0
fetch -1
store 1
call 72

Basically, the allocate_stack would tell you how much space you are allocating for fields in the stack. Then the fetch would queue up something relative to the stack to be stored (or fetch_a would fetch an absolute address). Then store would store the fetched value in the space relative to the stack (or store_a for absolute position). And finally, call <index> would call that specific function.
So basically these are 2-address codes instead of 3-address codes. Does anything like this exist out there where they've expanded upon the idea to find compiler optimizations and such, like 3-address-code and SSA form? If not like this, does anything else exist outside of 3-address-code and SSA form?

This is an extremely common approach to designing abstract machines for non-imperative languages. See, for example, the G machine or the WAM (which uses the same technique for heap allocation).


What does a ball of center v and radius r with at most r hops away mean? I am trying to understand what that sentence means. Intuitively, its obvious a radius ball means in a $ \mathbb{R}^{n}$ with respect to some norm. Its just the following set:

$$ B(v, r) = \{ x \in \mathbb{R}^n : \| v - x\| \leq r\}$$

i.e. its just all the points that are distance $ \| v - x\|^2 $ away from the center with respect to some norm $ \| \cdot\|$. However, in graph theory, if we have a graph $G = (V,E)$ I seem to have a much harder time to rigorously understand what this set means. Can someone help me define this set rigorously so that there is no doubt in my mind what it means to have a radius ball with at most radius $r$ in a fixed known graph $G = (V,E)$? In particular this is the sentence I am having a hard time understanding rigorously:

  a ball with center v and radius r is the set of vertices at most r
  hops away from v

For example, if I have a path from v1 to v2 to v3, then it has 3 hops. But if v1 also has v4 as a neighbor and we want a ball radius 3, does it mean that v4 should also be part of the set of radius 3 with center v1?

In fact, is the radius ball defined as follow:

$$ B(v,r) = \{ x \in V : \exists path(v,x) s.t.| path(v,x)| \leq r \}$$

or maybe it should be defined with shortest paths $\delta(v, \cdot)$:

$$ B(v,r) = \{ x \in V : \delta(v,x) \leq r \}$$

i.e. if you can get to a node from v in less that $r$ hops then its part of the radius ball on the graph.

In particular, consider the example. If we have a bounded degree say $d$ and the graph is undirected, if we have the radius be some finite number, do we necessarily have to include everyone's neighbor i.e. consider all the nodes in the degree?

An undirected (possibly weighted) graph defines a metric space, in which the distance between two vertices $x$ and $y$ is the length of the shortest path between $x$ and $y$; here the length of the path is the sum of the weights on the edges (weights are assumed to be non-negative), or the number of edges if the graph is unweighted. Given a metric, a ball is defined according to your formula.

If the maximal degree is $d$, the number of vertices in a ball of radius $r$ is at most $1 + d(1+\cdots+(d-1)^{r-1})$, which is what you get for a $d$-regular graph.


Random Graph is a good expander If a (n,d) random graph is a n-vertex graph defined as :

Choose d random permutations $\pi_1 \ldots \pi_d $, from [n] to [n]. Take edge (u,v) if $v = \pi_i(u)$ for some i. I am trying to prove that, for every n and $d \geq 2$, a (n,d) random graph is a (n,2d,1/10) edge expander with probability 1 - o(1).

For a given S such that $|S| \leq n/2$, I have found the expected value of the number of edges |E(S,S')| between S and V\S. But since this random variable is the addition of random variables which are not independent, I cannot apply the Chernoff bound to say that, the probability of |E(S,S')| being far from its expected value is low.

Is there any other way to prove this ?

Try proving directly that with high probability, no set of size at most $n/2$ has a small edge neighborhood. See for example Ellis's writeup for the complete details.

Another possibility is to try and use a more sophisticated large deviation bound to analyze $|E(S,S')|$. For example, there are versions of Chernoff's bound for negatively dependent random variables, and there is Azuma's bound, which is a martingale version of Chernoff's bound. The classical example is concentration of the chromatic number, appearing in Chapter 7 of Alon & Spencer as well as many other places, such as Bukh's write-up.


The origin of list data structure Does anyone know when the list data structure was mentioned in computer programming/algorithms? Who gave birth to this list concept?

Knuth gives a good overview on the history of lists and linked data structures. From The Art of Computer Programming, Volume I, Section 2.6:

  Linked memory techniques were really born when A. Newell, J. C. Shaw, and H. A. Simon began their investigations of heuristic problem-solving by machine.


how can i know if a First order logic sentences is valid or unsatisfiable or neither? i have trouble with understand this type of questions ,

i know how i can determine if the sentences is valid or unsatisfiable in Propositional logic , but in FOL i can't

for example , i have the following sentences in FOL :

1 = 2

the professor said this is neither valid nor unsatisfiable

but , i think it is always unsatisfiable , because 1 != 2 !!!

can someone explain to me how can i answer this type of question

thank you all

A formula is valid if all of the possible truth-assignments to its variables evaluate to true.

A formula is satisfiable if at least one of the truth-assignments to its variables evaluates to true.

The formula you gave is :

  $1 = 2$

Since this contains no variables, under any truth-assignment, the expression is $1 = 2$, which is false.

Neither of the above conditions have been met.

Therefore the formula is neither valid nor satisfiable. Since it is not satisfiable, we can say that it is unsatisfiable.


If a language L is regular then the given operation sort(L) is context free I was asked in one of my homework tasks this next question and I'm not quite sure how to handle it:

Sort(w) is an operation which takes a string (w) from a given language and sorts the characters in an ascending order. Sort(L) is the outcome language of the operation Sort(w) on each and every string (w) in the language L.
I was asked to prove or disprove the following claim:

  If L is a regular language over the alphabet {0,1} where 0<1 then sort(L) is context free.

I would appreciate any hints or clues on how to approach this type of question.

The way to solve this sort of question is using your problem-solving skills. Here are three ways to approach this question:

Take some DFA (or NFA) for $L$. Now construct a PDA for $\mathsf{sort}(L)$ along the following lines. The PDA starts by reading $0$s, pushing them into the stack. At some point it switches to a second phase in which it only accepts $1$s. At each step it first pops an arbitrary number of $0$s from the stack and feeds them to the DFA, and then reads the next $1$ if any, feeding it to the DFA. It accepts if after processing all the $0$s in the stack and all the $1$s in the input, the DFA is in an accepting state.
Take a left regular grammar for $L$ (so the rules are of the form $A\to\epsilon$, $A\to a$, and $A\to a B$), and replace $A\to 1B$ with $A\to B1$. The result is a context-free grammar for $\mathsf{sort}(L)$.
Parikh's theorem states that $\mathsf{sort}(L)$ is of the form
$$
\bigcup_{i=0}^m \{ 0^{x_i+n_1 y_{i,1}+\cdots+n_{\ell_i} y_{i,\ell_i}} 1^{z_i + n_1 w_{i,1} + \cdots + n_{\ell_i} w_{i,\ell_i}} : n_1,\ldots,n_{\ell_i} \geq 0 \},
$$
where $x_i,y_{i,j},z_i,w_{i,j} \geq 0$. It's not hard to check that all languages of this form are context-free, for example by constructing a context-free grammar.

Note how all of these approaches rely on the alphabet being binary. The language $(012)^*$ shows that this assumption is necessary. (Similarly, the language $(01)^*$ shows that $\mathsf{sort}(L)$ need not be regular.)

Parikh's theorem implies that for languages over the binary alphabet, $\mathsf{sort}(L)$ is context-free whenever $L$ is context-free (that is, we don't need to assume that $L$ is regular, it suffices to assume that it is context-free). You can try proving this fact directly.


How many clauses are required for SAT to be NP-hard in CNF formulas? It is not hard to see that SAT for a CNF formula with $n$ variables and a constant number of clauses can be solved in polynomial time. On the other hand, it is not hard to see that a CNF formula with $n$ variables and $O(n)$ clauses is enough for NP-hardness (consider for example the instances of SAT associated with the natural formula for 3-colorability, applied to planar graphs).
We could define this formally as $\text{CNFSAT}-f-\text{Clauses}$, a family of problems parameterized by a function $f$, in which instances are formulas in CNF such that if they have $n$ variables, then they have at most $f(n)$ clauses. Based on this, what I'd like to know is what is the smallest function $g$ such that we know there exists $f \in O(g)$ such that $\text{CNFSAT}-f-\text{Clauses}$ is already NP-hard. We know that g = 1 (constant # of clauses) does not work, and $g = n$ (linear number of clauses) works.
What about $g = \log n$? Is there a simple algorithm for CNFSAT over formulas that have $O(\lg \lg n)$ clauses?

Lower bound. For $g \le c \cdot \sqrt{\log n}$ there exists a polynomial-time algorithm. The idea is the following: if some clauses have too many variables, then it should be trivial to select some variable to satisfy this clause, without hurting clauses with few variables. We repeat the following:
Find the clause with the smallest number of variables. Let $x_1,\ldots,x_k$ be the variables participating in this clause.

If $k > g$, then the entire formula is satisfiable (we process clauses one by one and select a variable which we didn't select before).
Otherwise, we remove the clause. We also remove $x_1,\ldots,x_k$ from all other clauses.

Now, we have to satisfy the removed clauses. Since there are at most $g$ clauses and each of them introduces at most $g$ new variables, it means that there are at most $g^2 = c^2 \cdot \log n$ variables overall. Therefore, there are at most $n^{c^2}$ variable combinations, and we can just use brute-force.
Conditional upper bound. It is almost tight in the following sense. Assume that the lower bound on the SAT with $n$ variables and $\ge c\cdot n$ clauses (for some $c$, e.g. coming from $3$-coloring) is $\alpha^n$ ($\alpha \in (1, 2]$). Note that the same lower bound holds after our transformation (since we can just apply it before any algorithm). Therefore, if there are at least $\log^{1+\epsilon} n$ clauses, they can have $\frac {\log^{1+\epsilon} n} c$ variables and the lower bound for running time for our problem is
$$\alpha^{\frac {\log^{1+\epsilon} n} c} = n^{\frac {\log^\epsilon n \cdot \log \alpha} {c}},$$
which is super-polynomial.


Bisimilarity and Trace Equivalence in Labelled Transition Systems I'm a bit confused regarding the relation between trace equivalence and bisimilarity. These lecture notes I found and a few others documents I've read state that "if an LTS is deterministic then two states are bisimilar if they are trace equivalent".

When reading around the topic I found this page, which shows the following image:

These LTS' are trace equivalent and deterministic(?), why does the rule not hold that they are then bisimilar?

The answer is that the LTS on the left isn't deterministic, as the label (or action) open_door doesn't go to a single state and hence that action is non-deterministic.

This example shows that determinism is indeed required for trace equivalence and bisimilarity to be equivalent.


How to prove by contradiction that every nonempty hereditary language contains the empty string? A language L is called hereditary if it has the following property:

For every nonempty string x in L, there is a character in x which can be deleted from x to give another string in L.

Prove by contradiction that every nonempty hereditary language contains the empty string.

Here's my attempt:

To prove by contradiction, we assume that for every nonempty string x in L, there is no character in x which can be deleted from x to give another string in L.

This means that if a character in x is deleted an empty string is left. Since an empty string is also a string, every nonempty hereditary language contains the empty string.

I'm not exactly sure how to proof by contradiction. Can someone help review this?

Let L be a nonempty hereditary language. Let x be one of the shortest strings in L. x exists because L is not empty.

Removing any character from x would produce a string not in L, since x is one of the shortest strings. Because L is hereditary, we can remove a character from x giving another string in L, unless x is the empty string. Therefore x is the empty string. Therefore L contains the empty string.

If you insist on proof by contradiction: Let L be a nonempty hereditary language not containing the empty string, and let x be one of the shortest strings in L. x is not the empty string since L doesn't contain the empty string. Therefore there is a character in x which can be removed, giving a string y in L.

But y is shorter than x, therefore x is not the shortest string in L.


Are type variables really only used in mathematical conversation about types? Are type variables really only used in mathematical conversation about types? i.e. are type variables (meta-variables that only contain the type classification label) only exist in proofs for types but not in real programming languages? At least is this true for monomorphic types? i.e. I can't actually define:

$$ \texttt{ let id x = x }: \tau$$

unless the type $\tau$ has already been defined or is built in? i.e. type variables only exist for symbolic manipulation of type proofs for humans (at least for monomorphism).

Extra thoughts:

I am trying to understand how one defines the identity function $\texttt{let id x = x}$ in monomorphic type systems. I believe the motivation for polymorphism is to allow to apply the same syntactic definition of a function to different data types that are NOT the same, like: $\texttt{id 2}$ and $\texttt{id true}$ without the type checker freaking out at us when it tries to run those (if the language is dynamically typed...I guess in static the compiler would complain at the first instance of the identity function being applied to the wrong type when we try to compile it to usable code).

So to my understanding, if we define types as a set of possible data values, so say $\texttt{int}$ defines the set of all integers. Then the set $Set_{int \to int}$ is the set of all functions that can map integers to integers. But if we have $Set_{\forall \alpha .  \alpha \to \alpha}$ and we consider the identity function corresponding to both sets so $id_{\forall \alpha . \alpha \to \alpha} \in Set_{\forall \alpha .  \alpha \to \alpha}$  and $id_{int} \in Set_{int \to int}$ then when both identity functions are applied to integers they will behave exactly the same BUT they are not the same function (because they are not the same data value, the data value for one is identity on only integers while the other is give me any type and I will act like its corresponding identity. So in particular $Set_{\alpha \to \alpha} = Set_{int \to int} \cup \dots \cup Set_{string \to string}$ (i.e. the identity $id_{\alpha \to \alpha}$ is just the identity function for a specific type but not actually a function that is able to process ANY type, its one and in this case this is why the for all is important).

So my question is, is $id_{\forall \alpha . \alpha \to \alpha} \in Set_{\alpha \to \alpha}$? I guess I am trying to clarify the dots ... What does it cover? Perhaps it depends on the context of how the types are formally defined? If the $\alpha$ stands for type variables, but type variables are only allowed to be monomorphic by definition (i.e. say the type constructor for the meta-langauge is recursive but only in the monomorphism where we can't introduce the forall quantifier) then the $id_{\forall \alpha . \alpha \to \alpha} \not\in Set_{\alpha \to \alpha}$. But if the recursive definition for polymorphic types is recursive at the polymorphic step then perhaps $id_{\forall \alpha . \alpha \to \alpha} \in Set_{\alpha \to \alpha}$ is true? Actually I don't think so...

Context: CS 421

Related:

What does $ \forall \alpha_1, \dots , \alpha_n . \tau $ mean formally as a type?
What is the difference between $ \alpha \to \alpha $ vs $ \forall \alpha. \alpha \to \alpha$?

I am not sure I understand your question, but I believe the answer is "yes".  When describing monomorphic languages, an expression such as

let id x = x : τ

(where τ is understood as a type meta-variable) does not mean that you can write τ in the program text.  Rather, it means an arbitrary expression of that shape, where the meta-variable is replaced by any type of the language:

let id x = x : int

let id x = x : string

etc.  The "meta" in "meta-variable" means that the "variable" in question is not part of the syntax of programs, but a device we use to talk about types abstractly -- or, as you put it, in "mathematical conversation about types."


Graph Theory Handshaking problem Mr. and Mrs. Smith, a married couple, invited 9 other married couples to a party. (So the party consisted of 10
couples.) There was a round of handshaking, but no one shook hand with his or her spouse. Afterwards, Mrs.
Smith asked everyone except herself, “how many persons have you shaken hands with?” All 19 answers were
diﬀerent.

Unfortunately, when I try to simulate a smaller problem with 3 couples, I am getting that each couple is shaking 4 hands. Here is the diagram:

As you can see both a1 and a2 have 4 blue lines each that are "attached" (ie they shake hands) to the other couples. Both b1 and b2 have 2 red lines and 2 blue lines. Do we count the blue lines again adding it to the 2 red lines giving us that b1 and b2 have 4 lines attached or do we just ignore the blue lines connecting to b1 and b2 and say that both b1 and b2 shake 2 hands each?

Both c1 and c2 also have 2 blue and 2 red lines. I meant to have blue lines designated for a1 and a2, and the red lines for b1 and b2. Does that mean that c1 and c2 have shaken 0 hands each? Or do I try another few lines attaching the c's to the a's and b's?

Another problem with the approach above is that each couple has the same number of handshakes even though that is not possible according to the question. I would appreciate any clarification on the question and what exactly am I doing wrong.

Thanks.

Here is a solution for two couples, $m_1,w_1$ and $m_2,w_2$. The edges are $(m_1,w_2),(w_1,w_2)$. The degrees are $1,1,0,2$ (in the order $m_1,w_1,m_2,w_2$).

Here is a solution for three couples, $m_1,w_1,m_2,w_2,m_3,w_3$. The edges are $(m_1,w_2),(w_1,w_2),(m_1,w_3),(w_1,w_3),(m_2,w_3),(w_2,w_3)$. The degrees are $2,2,1,3,0,4$.

Hopefully you can generalize this construction to an arbitrary number of couples. If not, you can always try running the Havel–Hakimi algorithm, trying to avoid connecting a husband to his wife.


Deciding whether the head of a TM remains in K slots? I am trying to find the following:$$ \text{For a given TM M with initial empty tape is it possible to decide whether there} $$
$$\text{exists a constant K such that the head of M remains within the first K slots?} $$

I thought this was possible if you know $K$, since you could add the current configuration to a separate tape and understand whether the machine is looping or not as there exists finitely many configurations with length $K$. But what if you don't know this number? Is it still possible to find a TM that decides this language or is there a reduction from another undecidable language?

Any help will be appreciated.

Hint: Given a Turing machine $M$, you can construct another Turing machine $M'$ with the following properties:

If $M$ halts then $M'$ halts.
If $M$ doesn't halt then the head of $M'$ eventually reaches the $K$th square from the right for every $K$.

This construction can be used to show that the halting problem reduces to your problem.

As you mention, given $K$, your property is decidable. This shows that your problem is $\Sigma_1$-complete.


Am I right about the differences between Floyd-Warshall, Dijkstra and Bellman-Ford algorithms? I've been studying the three and I'm stating my inferences from them below. Could someone tell me if I have understood them accurately enough or not? Thank you.

Dijkstra algorithm is used only when you have a single source and you want to know the smallest path from one node to another, but fails in cases like this.
Floyd-Warshall algorithm is used when any of all the nodes can be a source, so you want the shortest distance to reach any destination node from any source node. This only fails when there are negative cycles.
Bellman-Ford is used like Dijkstra, when there is only one source. This can handle negative weights and its working is the same as Floyd-Warshall except for one source, right? (This is the one I am least sure about.)

Dijkstra's algorithm is used only when you have a single source and
  you want to know the smallest path from one node to another, but fails
  [in graphs with negative edges]

Dijkstra's algorithm is one example of a single-source shortest path or SSSP algorithm.  Every SSSP algorithm computes the shortest-path distances from a chosen source node $s$ to every other node in the graph.  Moreover, it computes a compact representation of all the shortest paths from $s$ to every other node, in the form of a rooted tree.  In the Wikipedia code, previous[v] is the parent of $v$ in this tree.

The behavior of Dijkstra's algorithm in graphs with negative edges depends on the precise variant under discussion.  Some variants of the algorithm, like the one in Wikipedia, always runs quickly but do not correctly compute shortest paths when there are negative edges.  Other variants, like the one in Jeff Erickson's lecture notes always compute shortest paths correctly (unless there is a negative cycle reachable from the source) but may require exponential time in the worst case if there are negative edges.

  Floyd-Warshall's algorithm is used when any of all the nodes can be a
  source, so you want the shortest distance to reach any destination
  node from any source node. This only fails when there are negative
  cycles.

That's correct.  Floyd-Warshall is one example of an all-pairs shortest path algorithm, meaning it computes the shortest paths between every pair of nodes.  Another example is "for each node v, run Dijkstra with v as the source node".  There are several others.

  Bellman-Ford is used like Dijkstra's, when there is only one source.
  This can handle negative weights and its working is the same as
  Floyd-Warshall's except for one source, right?

Bellman-Ford is another example of a single-source shortest-path algorithm, like Dijkstra.  Bellman-Ford and Floyd-Warshall are similar—for example, they're both dynamic programming algorithms—but Floyd-Warshall is not the same algorithm as "for each node v, run Bellman-Ford with v as the source node".  In particular, Floyd-Warshall runs in $O(V^3)$ time, while repeated-Bellman-Ford runs in $O(V^2E)$ time ($O(VE)$ time for each source vertex).

For further details, consult your favorite algorithms textbook.  (You do have a favorite algorithms textbook, don't you?)


modular arithmetic in rolling hash algorithm My question was around the rolling hash function in RobinKarp algorithm. It is intuitive for me to understand how to get from xi to xi+1 without the mod, however with the mod i am not sure how we still get the right answer. Is there any mathematical theroem anyone could quote which would help me understand?

So i get,

xi = (ti)R^0 + (ti+1)R^1 + .. + (ti+m-1)R^M-1
xi+1 = (xi - (ti)R^0)/R + (ti+m)R^M

but whats the guarantee,

xi = [ (ti)R^0 + (ti+1)R^1 + .. + (ti+m-1)R^M-1 ] mod Q
xi+1 = [ (xi - (ti)R^0)/R + (ti+m)R^M ] mod Q

.. and so on will be correct even after introducing mod Q

Pretty sure its some basic mod arithmetic theorem i am missing here.

What you are missing is the identity
$$
(a + b) \bmod{Q} = (a \bmod{Q} + b \bmod{Q}) \bmod{Q}.
$$


Complexity of K-Colorful Coloring Problem for a Hypergraph I searched a lot trying to find a reference for the complexity of K-colorful coloring problem for a hypergraph but I cannot find it. Please if anyone has a reference for the complexity of the problem let me know. I think it will be NP-Complete

Let H = (V, E) be a hypergraph, and let ϕ be a coloring of H. A hyperedge e ∈ E
is said to be k-colorful with respect to ϕ if there exist k vertices in e that are colored distinctively under ϕ. The coloring ϕ is called k-colorful if every hyperedge e ∈ E is min{|e|, k}-colorful. Let $c_H (k)$ denote the least integer $L$ such that H admits a k-colorful coloring with $L$ colors.

The reference for the problem is E.Horev,  R.Krakovski,  and  S.Smorodinsky,  “Conflict-free  color-ing  made  stronger,”  in Scandinavian  Workshop  on  Algorithm  Theory,pp. 105–117, Springer, 2010.

A strong k-coloring of a hypergraph assigns distinct colors to every member of a hyperedge and uses $k$ colors. When the hypergraph is $k$-uniform, this problem is equivalent to the problem you describe. Further, this problem is NPC as shown by Colbourn, Jungnickel and Rosa [1].

You can also prove yourself that this problem is NPC by a straightforward reduction from chromatic number. Essentially, you can add enough vertices around every edge and make them into cliques and you can make the reduction work.

[1] Colbourn, Charles J., Dieter Jungnickel, and Alexander Rosa. "The strong chromatic number of partial triple systems." Discrete applied mathematics 20.1 (1988): 31-38.


Shortest paths graph Given a directed graph $G$, edge weights for each edge, source vertex $s$ and $d[v]$ for each vertex in the graph (the distance from $s$ to $v$), I need to find an algorithm that builds the shortest paths graph.

I was thinking of going on edges by BFS, but then how can I know which edge should be in the tree and how to check that the $d[v]$ for each vertex is true?

Thre are multiple algorithms already developed like Dijkstra's algorithm, Bellman-Ford algorithm or A* search algorithm.

The problem you face is also well described on Wikipedia.

Maybe there is something specific about your assignment like memory or time complexity?


Intuition why $ L= \{\langle M \rangle| \ L(M)=\Sigma ^* \}\notin RE $ I know how to prove it by reduction, but I couldn't find an explanation why it is true.

$\langle M \rangle$ represents the encoding of a turing machine $M$.

The class RE contains all languages $L$ which can be expressed in the form
$$
x \in L \Longleftrightarrow \exists y \, P(x,y),
$$
for some computable predicate $P$.

Your language can be expressed in the following way:
$$
\langle M \rangle \in L \Leftrightarrow \forall x \exists t \, \text{"$M$ halts on $x$ after $t$ steps"}
$$
The quoted predicate is computable. This puts your language in $\Pi_2$, a level on the arithmetical hierarchy. There seems to be no natural way to come up with a simpler expression (less quantifiers), and this is why, intuitively, the language is not r.e. This kind of intuition usually works – write down an expression for your language in the most natural way, and this usually puts it in the correct level of the arithmetical hierarchy.

Your language is in fact $\Pi_2$-complete – every language in $\Pi_2$ can be reduced to it. Indeed, suppose that
$$
x \in L' \Longleftrightarrow \forall y \exists z \, P(x,y,z),
$$
where $P$ is computable. Given $x$, you can construct a Turing machine which on input $y$, goes over all $z$ in parallel, determines the value of each $P(x,y,z)$, and if it ever finds a value of $z$ such that $P(x,y,z)$ is true, it halts. This construction gives a reduction from $L'$ to your language.

Since your language is $\Pi_2$-complete, we know that it is not in $\Sigma_1$ (another name for RE), since the arithmetical hierarchy is strict. This means that there is no way to describe the language using fewer quantifiers (or using $\exists\forall$ rather than $\forall\exists$).

Your language is usually known as TOT, the language of all total Turing machines.


what is the meaning of hit time? Average memory access time = Hit time + Miss rate * miss penalty

Assume a computer with only one cache level. What is the exact meaning of hit time? Is it the number of clock cycles to access data from cache? OR Clock cycles to execute an instruction? How does the number of clock cycle per instruction come into this equation?

It's back to the mechanism of cache. When the cpu wants a data in cache, try to read data from cache. If there is the data in cache, It will fetch data from cache. This time of reading data from cache (the different between the speed of cache memory and register!) will be denoted by Hit time.

If the wanted memory in the related instruction  does not exist in the cache memory, it should be read from RAM, hence, it takes more cpu clock to read the specified address and this time is calculated by the multiplication of the miss rate and the penalty of this miss in time of reading data from RAM which is denoted by miss penalty.


When is the concatenation of a language $L$ with $\Sigma^*$ regular? I've been looking at questions about the regular concatenation of two languages; one question said that the concatenation of $\{0^n1^n|n\geq 0\}$ and $\Sigma^*$ was regular (over the alphabet $\Sigma = \{0,1\}$). Another provided a counterexample by the concatenation of $\{a^{n^2}b|n\geq 0\}$ with $\Sigma^*$, which is irregular (over the alphabet $\Sigma = \{a,b\}$). Could someone provide clarification as to why some concatenations with $\Sigma^*$ are regular while others aren't? Both cases concatenate an irregular language unrecognisable by a DFA to one that is, and I don't understand how this produces a language that is recognisable.

Links to source questions:
https://math.stackexchange.com/questions/649335/are-languages-regular-if-their-concatenation-is-regular
Why is $\Sigma^*$ concatenated with some language regular?

In the first case, $n$ can be 0, and the concatenation will produce $\Sigma^*$. So any other value of $n$ is irrelevant; no other strings could be added. If the restriction were $n>1$, then the concatenation would not be regular.


How to solve the recurrence: T(n) = n*T(n-1) + n? In a an exercise I'm required to analyze the runtime of recursive function:

 foo(n)
     for i from 1 to n
         work() // O(1)
         foo(n-1)
     end for
 end foo

The recurrence relation I understand from the code is: T(n) = n*T(n-1) + n

But I'm failing trying to analyze it using the iterative method since I don't see a repeating pattern when I'm opening some of the terms

How do I solve this recurrence ?

Looks like
$$
T(n) = n! + \left(\frac{n!}{0!} +\frac{n!}{1!} +\frac{n!}{2!} +\frac{n!}{3!} + \dots + \frac{n!}{(n-2)!} + \frac{n!}{(n-1)!}\right)
$$
satisfies the recurrent relation (here $T(0) = 1$).

From this for example $T(n) \leq n!(1+e)$.


Finding a regular expression for all non-empty binary strings that contain both 0s and 1s but no consecutive 1s This is for formal-language-style regular expression and not about Unix-style regular expression.

I was trying to find the regular expression that doesn't accept empty string, doesn't accept strings composed of only 0's, and doesn't accept strings composed of only 1's. The regular expression should only accept strings composed of 0's and 1's but without consecutive 1's.

Here's what I've seen so far: $(0+10)^*(ε+1)$

The problem is that it can accept empty string or just 1-character string 1. I would like to skip empty string and 1 since they are not strings of 0's and 1's.

I just couldn't find a good pattern. It seems that I have to create 2 regular expressions so that the first will be $(01+10)(0+1)^*$. If I am right, that will not accept empty string, will not accept just 0's, and will not accept just 1's. Then I would pass the result to the 2nd pattern $(0+10)^*(ε+1)$ to further validate that it has no consecutive 1's.

Could anyone explain what is the best solution to have the correct regular expression for strings of 0's and 1's?

I would suggest you to draw a small finite state automaton. Things to keep track in the states are "seen 0", "seen 1" and "last letter 1" (to avoid consecutive 1's).

There is an "official" algorithm to go from automaton to expression, but with small examples you usually can read the expression directly.


What are the meanings of metalanguage and metasyntax and EBNF? I am trying to understand what BNF, metalanguage, and metasyntax are.

From https://proofwiki.org/wiki/Definition:Metalanguage

  A metalanguage of a formal language is a formal language used to
  specify the formal language (make statements about the formal
  language).

  The object language of a metalanguage is the language described by
  that metalanguage.

From https://proofwiki.org/wiki/Definition:Syntax

  The syntax of a formal language is its structure, and is specified by
  a formal grammar of the formal language.

So I wonder if a formal grammar of a formal language is a
metalanguage of the formal language?
From https://proofwiki.org/wiki/Definition:Metalanguage/Metasyntax

  The syntax of a metalanguage is called a metasyntax of the object
  language of that metalanguage.

From http://en.wikipedia.org/wiki/Extended_Backus–Naur_Form

  Extended Backus–Naur Form (EBNF) is a family of metasyntax notations,
  any of which can be used to express a context-free grammar.

Does it mean that a context-free grammar is a metalanguage of a
context-free language, and EBNF is a syntax for the context-free grammar as a metalanguage, and therefore EBNF is a metasyntax for the context-free language as a object language?
From http://en.wikipedia.org/wiki/Metasyntax

  A metasyntax describes the allowable structure and composition of
  phrases and sentences of a metalanguage, which is used to describe
  either a natural language or a computer programming language.

  Some of the widely used formal metalanguages for computer languages
  are Backus–Naur Form (BNF), Extended Backus–Naur Form (EBNF), Wirth
  syntax notation (WSN), and Augmented Backus–Naur Form (ABNF).

Does it mean that EBNF is a metalanguage of a formal language, and
this formal language is a context-free grammar?

Thanks and regards!

In general, informally, a metalanguage is a language used to talk
about a language, possibly to specify it or to study its properties.

For example, linguists use English to describe the English
language. As a consequence English is used as its own metalanguage.
To avoid confusion, various quoting system are used to distinguish the
two level. For example, when talking about a small animal that barks,
we use the word "dog". Here, "dog" represent a word of a language
being talked about, not any of the possible meanings of that word in
the language it belongs to. It cannot bite.

When a language A is used as metalanguage to talk about a language B,
B is called the object language. But, though sometimes used in a
formal way, this is very similar to saying that wheather is the object
of many conversations.

In computer science, a well known example is the programming language
ML. The name ML actually stand for metalanguage. ML was initially
conceived by Robin Milner as a metalanguage to develop proofs about a small language
called pplambda in the LCF theorem prover. Hence, both syntactic and
semantic properties of pplambda can be expressed in ML.

Another well known example is Lisp, a language that is its own meta
language, and has been the first programming language to have that property. Lisp programs can be syntactically represented as a Lisp
data structure. The semantics of Lisp is also expressed in Lisp, since
the first Lisp interpreter was written in Lisp.

This works so well that the feat has since be often repeated for many other
programming languages, and it is very customary to write the first
compiler of a language in the
language itself, as part of a language bootstrapping process. Hence
the language is self compiling. This requires defining both the syntax
and the semantics of the language in itself.

So, in effect, most programming languages are, or can be, a
metalanguage for themselves, and for other programming languages.
That is actually the least one can expect from languages that often
claim to have Turing power.

The concept of metalanguage often concerns a conplete object language,
whether natural language or programming language, with syntax and semantics. But it can also
concern languages in the formal language sense, which are only syntax.  A mathematical
formalism used to describe (a family of) formal languages (regular
sets, context-free, recursively enumerable, ...) is a metalanguage for
this formal language.

This is more interesting when the syntax of the metalanguage belongs to the same language
family as the formal languages it describes.  The best known example is the
BNF language (Backus-Naur Form), and its later EBNF variant. It is a
language used to write context-free (CF) grammars, thus to define
purely syntactic languages. Its own syntax is context-free, hence
describable in BNF.  Hence BNF can be syntactically its own metalanguage,
but not semantically.  But then, BNF describes only CF languages and
has no claim for Turing power.

It is to be noted that BNF has a CF syntax, but it also has
semantics. The semantics of a BNF program is precisely a CF grammar and the formal language it defines,
to which the BNF program associates no semantics. A context-free
grammar just defines a formal language, and no semantics is
associated. Hence it is wrong to consider that BNF is a CF
grammar.  BNF has a CF grammar which defines its syntax.

Answering your questions

Regarding the two preliminary quotes. They are expressed in the
context of formal systems, and "formal" means mathematically defined,
which may include both syntax and semantics for the language. It does
not contradict the above discussion, but rather confirms it.

A formal grammar of a formal language is not a metalanguage of
the formal language. The mathematical formalism used to write the
grammar is in this case the metalanguage.

The quote goes into an issue that I did not address here, that of the
structure that a syntax definition can attach to the strings of a
formal language. It is, as far as I see, quite unrelated to the
concept of metalanguage, when we talk of formal languages in the
formal language theory sense. Two different syntactic definitions can
produce the same language, when considering only the string it
defines for the language. But these definitions implicitly associate
diffrerent structures with the string (such as parse-trees in the context-free
case) and that can be important.

When the formal language is actually the syntax of a complete
language that also has semantics, the structure is important as it is
usually organizing the definition of the semantics, which is the
purpose of many metalanguages.
As written above, a context-free grammar cannot be a metalanguage
since it has no semantics. The formalism used to write the CF grammar
is a metalanguage for the purely syntactic formal language defined by
this CF grammar. EBNF is a language with both syntax and semantics.
A program  (or whatever you want to call it: text, description,
grammar, ...) written in EBNF is a text using the syntax of
EBNF. This text has a meaning, defined by the semantics of EBNF,
which is the CF grammar it describes. EBNF is not a metasyntax, but a
meta language for syntax.

This calls for more precision. I consider that the word metasyntax is
just shorthand for the expression "syntax of [a/the] metalanguage". I
do not ses what other meaning it could have.

The first quote is just nonsense to me. The second quote is poorly
phrased and should rather be (if I understand the intent):

  Extended Backus-Naur Form (EBNF) is a family of metalanguages for
  defining syntax, any of which can be used to express a context-free
  grammar.

The quote (out of its context) is in agreement with what I said so
far. The expression "formal metalanguage" is not to be understood as
formal language in the formal language theory sense, but as a
language with a formally, i.e., mathematically, defined syntax and
semantics.

This quote alone just say that EBNF is a widely used metalanguage for
computer languages, but without being more precise about it.
Actually, according to me, EBNF is a metalanguage for (more than one)
formal languages in the formal language theory sense, since it can
only talk about the syntax, and pure syntax without semantics may be
seen as such a formal language. But these formal languages are those
described by the grammars expressed in EBNF. A grammar itself is not
a language, but it may be part of a language seen as a global object of study, since it can describe its syntax.

I hope this clarifies things.


What do we know about $NP \cap co-NP$? What do we need about the intersection of $NP$ and $co-NP$ apart from the fact that $P$ is a subset of it?

(beyond what these answers here say, What do we know about NP ∩ co-NP and its relation to NPI?, if $L\in NP\cap Co-NP$ is NP-Hard, then $NP=Co-NP$)

Is there an example of a decision question which is known to be $co-NP /\ NP$ or $NP /\ co-NP$? (and great consequences of such a thing existing in the even that P not the same as NP)
Do we know anything about how BPP, RP, co-RP or ZPP intersect NP or co-NP? (apart from the fact that $(P \subset (ZPP = RP \cap co-RP)) \subset BPP$ and hence whatever intersection with NP and co-NP follows just from this)

There is no decision problem that is (unconditionally) known to be in $coNP \setminus NP$.  If we had a decision problem that we could prove is in $coNP$ and could prove is not in $NP$, then we would have proven that $NP \ne coNP$, from which it follows that $P \ne NP$.  In other words, if we knew of such a problem, a proof that is in $coNP \setminus NP$ would provide a proof that $P \ne NP$.  But of course we don't know of any proof that $P \ne NP$; that is a famous open question.

For similar reasons, there is no decision problem that is known to be in $NP \setminus coNP$.

The closest we have is the following: we know of decision problems that are in $NP \setminus coNP$, if $NP \ne coNP$.  For instance, if $NP \ne coNP$, then SAT is in $NP \setminus coNP$.  (You can replace SAT with any other problem that is known to be NP-complete.)  It is widely conjectured that $NP \ne coNP$, so SAT is a good candidate for such a  problem -- but we don't know any proof that $NP \ne coNP$ (that's another famous open problem).

We can also say that if $NP = coNP$, then there is no decision problem in $NP \setminus coNP$.  From this plus the above discussion, we obtain the following useful fact:

  There is a problem in $NP \setminus coNP$ if and only if $NP \ne coNP$.  If there is any problem in $NP \setminus coNP$, then SAT is one such problem.

The same remains valid if you replace SAT with any other NP-complete problem.  Symmetrically, we also know:

  There is a problem in $coNP \setminus NP$ if and only if $NP \ne coNP$.  If there is any problem in $coNP \setminus NP$, then TAUTOLOGY is one such problem.

You can replace TAUTOLOGY with any other problem known to be coNP-complete.

So, this is pretty much a complete characterization of those classes, up to our lack of knowledge whether $NP=coNP$ or not.


Why are reversible gates not used? I was reading the book "The singularity is near" written by Kurzweil and he mentioned the reversible gates like for example the Fredkin gate. The advantage using such gates is that we could get rid of the thermal waste related to computation where bits just disappear into heat, and computation won't need any energy input. Those assumptions make these gates sound like a miracle solution. So the question is what technical hurdles are still preventing their large scale usage.

I also think it is a shame that I never heard about those gates in my electrical engineering bachelor and master studies at a top German university...

I am by no means an expert on this topic, but just from casually reading Wikipedia:

  it relies on the motion of spherical billiard balls in a friction-free environment made of buffers against which the balls bounce perfectly

... this sounds very realistic.

Nobody has actually figured out how to actually make such gates yet, they're merely of theoretical interest. That might explain why you've never heard of them since engineering usually deals with practice.

The premise of Reversible Computing is that when a bit disappears, some amount of heat is generated. By using reversible gates, no bits ever appear or disappear so supposedly computation could be much more efficient with reversible gates.

The theoretical limit Reversible Computing claims to get around is that erasing 1 bit of information generates at least $kT\ln 2$ energy in heat. For a computer running at a toasty $60\,{}^\circ\mathrm{C}$ with $10^9$ transistors each making bits disappear at a rate of $5\,\mathrm{GHz}$, that corresponds to $16\,\mathrm{mW}$ of heat generation. That only accounts for a tiny proportion ($1/10000$) of a computer's energy usage.

Our current-day computers are not limited by heat generation associated with bits disappearing. They are limited by the inherent inefficiency in moving electrons around on tiny copper traces.


What is the grammar for language $L={a^nb^m : n \neq m-1}$? What is the grammar for language $L = \{ a^nb^m : n\neq m-1\}$?

I only know I have to write grammar for both $ n<m-1 $ and $ n>m-1 $, so this is what I wrote:

for n<m-1
S->Abb
A->aAb|lambda

for n>m-1
S->aaA
A->aAb|lambda

Yet I can not mix them and get a correct grammer for it.

If you split the grammar into two parts for disjoint parts of the language you better take different names for the variables, since they have a different meaning in the two parts.


What are the vertical and horizontal focal lengths? In this paper,

http://www.vision.caltech.edu/malaa/publications/aly08realtime.pdf

the author mentioned "the vertical and horizontal focal lengths" but didn't have any clear definition.

My understanding about "focal length" is the distance between the lens and the image plane.

Does anyone have the idea about these focal lengths?

Thank you.

Note that they assume a pinhole camera model. The term 'focal length' means something different here than it does with a lens camera.

All you ever really need to know about the pinhole camera model can be expressed as:
$$x_\mbox{imageplane} := x_\mbox{world}/z_\mbox{world}$$
$$y_\mbox{imageplane} := y_\mbox{world}/z_\mbox{world}$$
This describes how points in the scene project to an image plane 1 unit in front of the camera origin (center of projection & center of world coordinate system), with the optical axis along the z direction.

All the other values usually discussed in connection with pinhole cameras 'just' describe which rectangular part of the image plane is mapped to the rectangle of pixels that is your image. Or, conversely, how pixel coordinates can be transformed back into points on the image plane (and from there, can be transformed to directions in the scene).

Of course this rectangle-on-a-2d-plane can be defined by a 2d point
$b$ and two 2d vectors $v_1, v_2$ such that:

$$\begin{bmatrix}x_\mbox{image}\\y_\mbox{image}\end{bmatrix} :=
\begin{bmatrix}\vec{v_1}&\vec{v_2}\end{bmatrix}
\begin{bmatrix}x_\mbox{imageplane}\\y_\mbox{imageplane}\end{bmatrix} + b$$
If we abbreviate this as $(x_\mbox{image},y_\mbox{image}) = f(x_\mbox{imageplane},y_\mbox{imageplane})$ the part of the imageplane that your image depicts is the set $f^{-1}([0,\mbox{width}]\times[0,\mbox{height}])$ which, as I said, is a rectangle1.

The 'other values', for example:

optical center: $c_x, c_y$ or $c_u, c_v$
horizontal and vertical 'focal length': $f_x, f_y$ or $f_u, f_v$
aspect ratio
field of view angle $\alpha$
shear (you don't usually want that)

are just used to describe special cases of the above formula.

In your case, $b = (c_u, c_v)$ and $v_1 = (f_u,0), v_2 = (0,f_v)$ such that

$$\begin{bmatrix}x_\mbox{image}\\y_\mbox{image}\end{bmatrix} :=
\begin{bmatrix}f_u x_\mbox{imageplane} + c_u\\f_v y_\mbox{imageplane} + c_v\end{bmatrix} $$

1 Note that it is not the rectangle with corners $b, b+v_1,b+v_2,b+v_1+v_2$. To find it you'd have to compute the inverse of the function $f$.


Travelling salesman problem with small edge weights Are there any advantages in finding the shortest tour for the problem if edge weights are much smaller than the number of vertices?

Let's say the maximum edge weight is $n$, and the number of vertices is $n!$, and the adjacency matrix is dense and all distances $d_{ij}$ satisfy $0 \le d_{ij} \le n$. Are there any known methods which work well in similar cases?

Travelling salesman remains NP-complete even if you restrict to two different edge weights $a<b$.  Reduce from Hamiltonian cycle by giving weight $a$ to every edge and weight $b$ to every non-edge.  Then the resulting complete graph has a TSP tour of length $na$ (where $n$ is the number of vertices) if, and only if, the original graph has a Hamiltonian cycle.


How do computers compute? This is a kind of follow-up to a question I asked on superuser, where I asked for the definitions of a 'distinghuisable state' and a 'memory cell'. My questions where properly answered, but I was still confused about a certain matter.

I'm reading this little paper, and in particular these sentences:

  To perform useful computation, we need to irreversibly change distinguishable states of memory cell(s) .... So the energy required to write information into one binary memory bit is $E_{bit}= k_BT \ln2$

So my interpretation of this is that the author says that to compute, you need to change the state of bits ($ 0 \rightarrow 1$, $1 \rightarrow 0$) in order to compute.

But is that actually a reasonable statement? I'm not really interested in the rest of the paper, only this part. Do computers (I'm not talking about supercomputers, or future computers which use qubits and whatnot, but just your average computer) compute using bits with 2 dinstinghuisable states?

I actually was able to find this so-called 'SNL-expression' somewhere else, namely this pdf, on page 223; it's actually a part of MIT's ocw.

I'm not entirely sure if I understood the question the way it was intended, but what computers do is that they operate on electricity, so they don't have two discrete logical values $0$ and $1$ per se. What they do have is electricity with voltage, and they are made to operate as if there were two logical values $0$ and $1$ if the voltage at a gate is below a certain threshold (for $0$; for example, below 0.5mV) or above another threshold (for $1$, for example, above 2.5mV) with a reasonable distance between those two threshold values. Anything in between will give the processor undefined behaviour.

What processors then do is operate on the logical values $0$ and $1$ that were abstracted from the continuous voltages. The hardware implements functions using boolean logic, meaning functions of the kind $\{0,1\}^n \to \{0,1\}^m$. For an introduction to how these things are implemented in hardware, see for example the material found here. It starts out with boolean logic, and by chapter 4 p. 3 everything needed to build an adder (meaning a circuit that implements addition) has been explained. It's a total of 23 pages to read until then, so you can decide if you would like to spend the hour or two it takes to read through it (and another hour to reread for understanding).

The circuits that don't have a way to store values are called combinational circuits, and those are used to implement the most basic functions in hardware (for example, addition, multiplication, logical operations like OR, AND, XOR for binary vectors). Circuits that can store values are called sequential circuits, and they utilize techniques where the input of gates are interdependent, and the circuits have well defined stable states. For an introduction to that, see for example here. Don' be disappointed if you can't quickly grasp that - I for one had a bit of trouble with comprehending sequential circuits initially.

For a small summary on how circuits are built from the elemental building blocks called transistors, see for example here. It only summarizes the working of transistors without all the electromechanics that go into it. Basically a transistor has a source (input) where we can apply a voltage, a gate where we can apply a voltage to control whether the input is inverted or not, and a drain (output). Depending on what type of transistor we use, the gate allows transmission from source to drain if we apply a $0$ (for nMOS transistors) or a $1$ (for pMOS transistors) to the gate.

Note that all of this is actually not computer science related, it's electrical engineering. If you would like to find out more about circuits in depth, I would advise you to ask on electronics.SE.


Triangulating a simple polygon via its trapezoidal map Given a trapezoidal map of a simple polygon $P$, is it possible to compute the triangulation of $P$ in $\mathcal{O}(n)$ time?

Yes, "it's easy to derive from such a decomposition of $P$ in linear time a triangulation of $P$."

Take a look at lemma 1. here.


Why $\phi$ $\cdot$ R = $\phi$, rather than $\phi$ $\cdot$ R = R in Automata? I understand that $\phi$ is a null symbol.
why concatenation of any language L with $\phi$ is $\phi$ rather than L ?

Let us check the definition.

For two sets of strings $S_1$ and $S_2$, the concatenation $S_1\cdot S_2$ consists of all strings of the form $vw$ where $v$ is a string from $S_1$ and $w$ is a string from $S_2$, or formally $S_1\cdot S_2 = \{ vw : v \in S_1, w \in S_2 \}$.

What about $\emptyset\cdot R$?

 Since there is no string in the empty set, we cannot find any string of that form $vw$ where $v$ is a string from the empty set. For example, you cannot form a mixed double in tennis if there is no male players. So $\emptyset\cdot R=\emptyset$.


When does the IEEE-754 64-bit float break as a counter As a matter of curiosity I've been trying to determine at what point a 64-bit float no longer reflects the addition of 1 as expected; that is, at what point the digits as printed do not correspond to the digits of a 64-bit integer that is incremented in sync.

Around 1e15 I can continually add 1 or subtract 1 and the result seems right. At 1e16 the addition or subtraction of 1 has no effect on the value as printed. However, 1e16 - 2 gives 9.999999999999998e+15 (at least, as printed by go's fmt package).

I wonder whether there are discontinuities in the sequence of sums of n+=1 while n < 1e15. At what point does n+=1 no longer produce a result corresponding to the expected integer?

IEEE floating point format has a sign bit,  an 11 bit exponent (ranging from -1022 to 1023) and a 52-bit mantissa with an implicit "1" in the 53rd bit.

Thus, the largest integer that can be represented without rounding is the binary number with 53 "1"s, $2^{53}-1$ = 9,007,199,254,740,991 ~ 9e15 < 1e16.  After that you start having to round off low order bits.  So it looks like your experiment produced the right order of magnitude.


How to decompose into BCNF while preserving all functional dependencies I have a relation R = {A,B,C} and F={AB -> C , C -> B}.
In order to check if R is in BCNF.

I checked if AB and C are both superkeys and since C is not a superkey I conclude R is not in BCNF.

After decomposing R into BCNF, I have two relations :

R1(C,B)   F1{ C -> B}
R2(A,C)   F2{ A -> C}

Now since A and C are both superkeys, I can conclude that now R(R1, R2) is in BCNF.

But after computing (F1 U F2)+, I can't derive AB -> C and so I lose that FD.

My question is, how can I decompose than into BCNF while preserving FD's?

this very example is discussed in the first place I looked.

The short answer is that you cannot always achieve all of

BCNF;
an information-equivalent schema;
using keys as the only declared constraint(s).

Pick any two.

In this case you must retain R = {A, B, C}, with key {A, B} -- then we can't losslessly decompose R. In order to represent the FD C -> B as a relation with a suitable key, you need R1 = {C, B} with key {C}. So far we've achieved BCNF. To retain information equivalence, you need an Inclusion Dependency (aka Foreign Key constraint) R[C] ⊆ R1[C].

Strictly speaking to retain info equivalence, that Inclusion Dependency should probably be an Equality Dependency. But this is a contrived example, so nobody in practice would do that.


If each pixel contains the channels for the 3 primary colours, why can a 1-bit picture only be presented in white and black? I'm an igsce student. I'm taking computer science as an OL subject this year.
Pixels are the small squares which make an image. Inside each pixel there are 3 channels: one for blue, one for green, one for red. The three primary colours from which any other colour can be made. And that's how I imagine it:
When we say an image is 8-bits we actually mean that for each channel (in one pixel) of green, blue or red there are 8 bits. So green can have 255 shades/intensities/brightness and so on for the rest of the colours.
So even for a 1-bit image, each pixel contains 3 channels one for each of the primary colours. The only difference is that there's only 1 intensity/brightness/quantity for each colour.
So even in 1-bit image the three primary colours still exist so more colours other than black and white can be made by mixing the three colours together, 8 colours to be exact. Why is it said then that a 1-bit image is only black and white?

Please read the Wikipedia article 8-bit color.

8-bit color graphics are a method of storing image information in a computer's memory or in an image file, so that each pixel is represented by one 8-bit byte. The maximum number of colors that can be displayed at any one time is 256 or 2⁸.

In other words, the problem is that 8 bits mean that all three primary colors red, green, and blue, are encoded in 8 bits in total.  From Wikipedia:

The simplest form of quantization frequently called 8-bit truecolor is to simply assign 3 bits to red, 3 to green and 2 to blue (the human eye is less sensitive to blue light) to create a 3-3-2
Bit    7  6  5  4  3  2  1  0
Data   R  R  R  G  G  G  B  B

8-bit color image, but this process is sub optimal. There could be different groupings of colors that make evenly spreading the colors out inefficient and likely to misrepresent the actual image. Because the color map doesn't need to have every color in it and just needs to accurately represent the more color dense image, an arbitrary color can be assigned to each of the 256 available color 'slots' on the map. [...]

Concluding, 1 bit means that you can have only two states, e.g. black/white.


Shannon Entropy for Binary Numbers First of all, I have to mention that I am very new in the field of information theory.
I have a question regarding the Shannon Entropy calculation for binary values. As far as I understood, the main assumption in the Shannon Entropy formula is that all the bits have the same weights. However, I am looking for a formula/techniques to calculate the entropy based on the weight of each bit of a binary string. Let me elaborate on this.

Suppose we have a 3-bits binary number (b2, b1, b0) and let us assume that the probability of being 0 or 1 is 0.5. Based on the Shannon's theorem the entropy considers all these bits with the same weight. If I give tell you that (b1, b0) = (00) then you can guess that the final value is either 0 or 4. But if I give you (b2,b1) = (00) you can guess that the final value is either 0 or 1. To me it means b2, b1 provides more information than knowing b1,b0. Because, you can guess the final value with less error. Is it really related to information or it is something else?

It would be good if you could provide me some links to get more information about this topic.

This is the link to my related question:
Hamming Error Correction

Thanks

Take a look at rate-distortion theory, which studies information transmission in settings where a certain distortion is allowed (such as audio, image, or video compression).


Does $\mathsf{NSPACE}( f (n)) = \mathsf{coNSPACE}( f (n))$ hold for $ f(n) < \log (n) $? It's known that for $f(n) \geq \log n$,  $\mathsf{NSPACE}(f(n)) = \mathsf{coNSPACE}(f(n))$.

What if $f(n)<\log n$? Are they also equal?

Immerman–Szelepcsényi theorem  works under logarithmic reductions. Sublogarithmic space classes have different reductions. The TMs working within sublogarithmic space cannot even record the the length of the input. It has been shown that the space hierarchy for any sublogarithmic bound in Ω(log log n)-- o(log n) is inﬁnite. You can find it in following references:

V. Geffert. Sublogarithmic σ2-space is not closed under complement and other separation
results. Theoretical Informatics and Applications, 27:349–366, 1993.

M. Liśkiewicz and R. Reischuk. Separating the lower levels of the sublogarithmic space
hierarchy. In Proceedings of the Symposium on Theoretical Aspects of Computer Science,
pages 6–27, 1993.

B. von Braunmuhl "Alternation for two-way machines with sublogarithmic space". In Proceedings of the Symposium on Theoretical Aspects of Computer Science, pages 5–15, 1993.

The paper The complexity world below logarithmic space by M. Liśkiewicz and R. Reischuk contains an excellent wrap up of the sublogarithmic space.


Can a Turing Machine have infinite accept states? I'm still fairly new to Turing Machines, but I've been doing some research.

I know that a Turing Machine can have an infinite tape and that it requires a finite number of states, but does it necessarily follow that a Turing Machine can have an infinite number of accept states?

I keep seeing different layouts when formally defining Turing Machines, for example:

M = (Q, Σ, Γ, τ, s, F).

1) F ⊆ Q is the set of final or accepting states. (plural)

2) F ⊆ Q is the accept state. (singular)

So I'm just wondering which one is correct?

Any help would be greatly appreciated.

In the standard Turing machine, the set of states $Q$ is finite $|Q| < \infty$. Therefore, it cannot have infinite final states. However, it may, or may not have multiple final states. This will not change the power of the machine (i.e., one final state is equivalent to $k$ final states).


Are there existing extensions to behavior trees that fascilitate node communication? I've been looking into behavior trees, but I cannot find a lot about them. The Wikipedia page pretty much only mentions sequence and selector nodes.

I have found implementations that also provide memory selector, memory sequence, and parallel sequence, as well as some decorators like inversion and repetition.

I found some papers that discuss some form of a "weighted" selector/sequence that queries its children for their utility/probability. This can also be used in machine learning to dynamically adjust those weights.

What I have not yet found much about is communication between nodes.
Some implementations use a shared "blackboard" where nodes can write values, but this seems rather clumsy, as it creates a huge lookup table that tightly couples different nodes.

I've been thinking more in terms of sending messages to the next node.
I think the bulk of the shared state is a condition/action providing a specific value to the next action (rather than just success).

Has there been any research in this area? I was not able to find anything.
I'm also curious to hear about other useful extensions.

The most mathematical paper I have seen on Behavior Trees is How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture and Decision Trees. It is the only paper I have seen that defines Behavior Trees as a tuple e.g.

  A BT is a three-tuple $T_i = \{f_i, r_i, \Delta t\}$

Since Behavior Trees are related to Finite State Machines (FSMs), they mention Petri Nets which are also related to FSMs. They're a message passing / concurrency system, but weren't mentioned really in relation to message passing on Behavior Trees. Maybe it would provide some inspiration since they are highly developed message passing formalisms.

Other than that, there may be some private work done on message passing in complex Behavior Trees such as in game companies, but there doesn't seem to be any public resources on it. Maybe it is an artifact of the way behavior trees are developed, i.e. it seems to be done through node-based graphic interfaces, so less source-code-centric:

Probably best to just come up with your own system it seems. Maybe even try asking at the gamedev.se, they might have some insight. Hope that helps.


Turing machine that accepts language with more a's than b's I am doing an assignment for my 1st year langauges and automata class. I have been having trouble with the last question which is this: Create a Turing machine that acccepts more a's than b's. I think I am supposed to pair the a's and b's together and then do some more but I can't wrap my head around it. Would help greatly if someone can post the algorithm and explain a little.

Sit before a big empty sheet of paper. Write down a sequence of a's and b's. Now mechanically check whether that string should be accepted. You cannot use counting, that would be requiring an infinite number of "states" inside your head.
You can however use additional symols. A striked out b is just a new symbol that is written on the tape.

Turn your intuition into an algorithm. First informally, that is what Karolis has done. Then add information on how to implement this on a Turing tape. What direction is the head moving? Where will it stop? Then translate the whiles and untils into states and transitions (sort of goto-programming, which is improper unless you are programming a TM).

If you are a CS student, then you can do these steps. You can program. No matter whether it is C++, assembler, or Turing. That is just details.


A quine in pure lambda calculus I would like an example of a quine in pure lambda calculus. I was quite surprised that I couldn't find one by googling. The quine page lists quines for many
"real" languages, but not for lambda calculus.

Of course, this means defining what I mean by a quine in the lambda calculus, which I do below. (I'm asking for something quite specific.)

In a few places, e.g. Larkin and Stocks (2004), I see the following quoted as a "self-replicating" expression: $(\lambda x.x \; x)\;(\lambda x.x \; x)$. This reduces to itself after a single beta-reduction step, giving it a somehow quine-like feel. However, it's un-quine-like in that it doesn't terminate: further beta-reductions will keep producing the same expression, so it will never reduce to normal form. To me a quine is a program that terminates and outputs itself, and so I would like a lambda expression with that property.

Of course, any expression that contains no redexes is already in normal form, and will therefore terminate and output itself. But that's too trivial. So I propose the following definition in the hope that it will admit a non-trivial solution:

definition (tentative): A quine in lambda calculus is an expression of the form
$$(\lambda x . A)$$
(where $A$ stands for some specific lambda calculus expression) such that $((\lambda x . A)\,\, y)$ becomes $(\lambda x . A)$, or something equivalent to it under changes of variable names, when reduced to normal form, for any input $y$.

Given that the lambda calculus is as Turing equivalent as any other language, it seems as if this should be possible, but my lambda calculus is rusty, so I can't think of an example.

Reference

James Larkin and Phil Stocks. (2004) "Self-replicating expressions in the Lambda Calculus"
Conferences in Research and Practice in Information Technology, 26 (1), 167-173.
http://epublications.bond.edu.au/infotech_pubs/158

One one hand this is impossible, because a quine is supposed to output its own code, and the pure lambda calculus has no means for performing output.

On the other hand, if you assume that the resulting term is the output, then every normal form is a quine.

For example, lambda term $(\lambda x. x)$ is already a normal form, then assuming that its output is the resulting normal form, the output is $(\lambda x. x)$. Thus $(\lambda x. x)$ is a quine.


Proof of a greedy algorithm used for a variation of bin-packing problem We are given an array of weights $W$ (all weights are positive integers), and we need to put the
weights inside bins. Each bin can hold a maximum of Max_val, and each weight is at most Max_val. The variation is that the ordering of weights should not be changed, that is, $W_i$ should be inside a bin before $W_j$ is inserted, for all $i < j$.

For this problem statement, intuitively we can see that a greedy approach of filling a bin till its maximum value is reached and creating a new bin for further weights will produce the minimum number of bins. I am unable to come up with a formal proof that the greedy solution is optimal. Any hints or guidelines would be great!

Let $G$ be the solution produced by the greedy algorithm. For each other solution $S$, let $i(S)$ be the index of the first weight at which $S$ diverges from $G$. Let $O$ be an optimal solution maximizing $i(O)$. Thus $G$ places $i(O)$ in bin $j$ (for some $j$), and $O$ places $i(O)$ in bin $j+1$. If we move $i(O)$ to bin $j$ (which is possible since $O$ is ordered), we obtain a solution $O'$ using at most as many bins as $O$, and satisfying $i(O') > i(O)$. This contradicts the choice of $O$.

If we try to run this argument on the unrestricted bin packing algorithm, we will have trouble when moving $i(O)$ to bin $j$, since that bin might be occupied with other elements, not leaving enough room for $i(O)$. In the variant you consider, this cannot happen.


closure of Context free grammer to homomorphism using PDA I was looking online, on sipser book, and on lecture notes and I can't find a proof to closure of context free languages to homomorphism that using PDA instead of CFG.
I'm not looking for a full and formal proof, I just want to understand the general idea.

The idea is to replace a single transition by a sequence of transitions.
Suppose for example that $h(\sigma) = \tau_1 \ldots \tau_\ell$, and consider a transition at state $p$ which replaces the symbol $A$ on the stack with the string $\alpha$, and moves to state $q$.
We replace this transition by a sequence of transitions $p \to s_1 \to \cdots \to s_{\ell-1} \to q$, which read the letters $\tau_1,\ldots,\ell$ in sequence; the states $s_1,\ldots,s_{\ell-1}$ are unique for handling this transition. The first transition $p \to s_1$ replaces $A$ with $\alpha$, and the rest don't change the stack.


Numbering levels of a tree I find the need to use an explicit level numbering for a tree.
i.e. in the tree:

    A
   / \
  B   B
 /\   /\
C  C C  C

should I number the level C the 3rd and A as the first, or the opposite?
As going 'up' the tree is going towards A; should the numbering reflect that as well?
 If can, please supply an authorized CS reference.

Thanks!

There's no such thing as "an authorized CS reference", since nobody has the authority to declare how tree levels should be numbered.

The "height" of a vertex is its distance from the root (or distance plus one; see another question about the definition) so it probably makes sense to start at the top in most cases.  But you should use whichever numbering is most convenient in your situation.


Ray Tracing versus object-based rendering? Intro graphics courses usually have a project that asks you to build a ray tracer to render a scene. Many graphics students entering grad school say that they want to work on ray tracing. And yet it seems that ray tracing is a dead field in venues like SIGGRAPH etc.

Is ray tracing really the best way to render a scene accurately with all desired illumination etc, and is it just the slow (read non-interactive) performance of ray tracers that makes them uninteresting, or is there something else ?

Raytracing is a very nice and intuitive algorithm, and it is a more physically realistic way of describing the illumination of a scene than rasterization, but:

Raytracing is slow, specially if you want to implement the more realistic effects that distinguish it from rasterization (e.g. refraction, reflection, motion blur, soft shadows) because this implies creating a lot more rays per pixel.
Most people can't tell the difference between real and fake effects, which I think is the key point. The goal of a practical rendering algorithm is to create a photorealistic representation of a scene in the most efficient way, and right now Rasterization, although uses a lot of hacks, accomplishes this very well.
There are many other practical limitations of Raytracing compared to a Rasterization renderer: poor anti-aliasing and displacement mapping, limited instancing, etc.

Even in non-interactive applications, such as movies, Raytracing is used very little becasue of its limitations. Pixar only started using Raytracing in Cars, and only for some specific reflection effects (Ray Tracing for the Movie ‘Cars’).

Here is an excellent article that describes in more detail the current state of Raytracing and its advantages and disadvantages: State of Ray Tracing (in games).


Closure of regularity under the action of replacing identical pairs of letters Given any regular language L,
we define
$$shrink(L) = \{ \sigma_{1}\sigma_{2}\sigma_{3}...\sigma_{n} : \sigma_{1}\sigma_{1}\sigma_{2}\sigma_{2}\sigma_{3}\sigma_{3}...\sigma_{n}\sigma_{n} \in L \} $$
The question is whether these languages are regular or not.
The intuition says they are, and I was thinking about proving it with Homomorphism, i.e defining homomorphism from shrink(L) by duplicating each word and then proving that $h(shrink(L))$ is regular therefore shrink(L) is regular.
But I'm not exactly sure how to do it properly..
edit: another idea I had is by using DFA - if L is regular it has a DFA called M, so I can build M' by changing Delta such that $\delta (q,\sigma w) = \delta(\delta(q,\sigma w),\sigma w)$. Will it work?
Thanks for any help

You can do it using homeomorphism. Define $h:\Sigma\rightarrow \Sigma^*$ by: $h(\sigma)=\sigma\sigma$.
Then, $h$ induces a homeomorphism $g$ that is defined by $g(\sigma_1,\dots,\sigma_n)=h(\sigma_1)\dots h(\sigma_n)$.
Then, its easy to see that $shrink(L)=g^{-1}(L)$ (prove this!). From closure properties of regular languages we know that $g^{-1}(L)$ is regular, hence also $shrink(L)$.


Confusion regarding terminology surrounding perceptron learning I am having trouble understanding the terminology with perceptron learning. Is my current understanding correct? Let's say I have some data that classifies what type of flower a particular flower is. And let's say the factors taken into consideration are petal size, petal coloring, and leaf size. So my current understanding is that we take every pair of inputs and make them the axis of a graph(e.g. leaf size vs petal coloring). So in this case, we would have 3 graphs. Now, we plot the data points and see if it is linearly separable. That is, we can draw a line called a "decision boundary" that separates the data into two regions to be able to differentiate which inputs correlate with which outputs. This line is defined by $w^T \cdot x = y$. However, my first confusion is the following. How are 3 different graphs each with pairs of inputs (the 2 axis) represented using a equation of a single line that is used as the input layer of the neural network?

My second confusion is, is the objective function what defines how the $w^T \cdot x$ is to be interpreted? For instance, something like $y = 1 $ if $w^T \cdot x \geqslant 0$ and else $y = 0$. Also, as I have understood, the learning rule is supposed to be how to update consecutive weights.

Can someone please explain the situation I have laid out. I am reading Bishop's book on Neural Networks. But I am confused by the text.

In machine learning, the perceptron is an algorithm for supervised learning of binary classifiers.

Its much complex than just drawing some graph and fitting a line to divide these data. I should tell you that you gone entirely wrong about the core concept.

Our brain are capable of solving complex problem, few of which are impossible for a computer to figure out. Thus scientist studies our brain and tried to mimic its biological structure to achieve its capability in computers. One of the initial steps towards it was perceptron.

Two types of perceptron are:

Single Layer perceptron - works only in linearly separable data.
Multi Layer perceptron - work with non linear data too.

Perceptron have the capability of learning from a given (training) data and implement that knowledge into another (new) data as we desire.

Your problem: (desired output)

  classify what type of flower a particular flower is?

There are thousands and thousands of types of flowers so, for simplicity I'm modifying you question as "classify if this flower is jasmine or not"

Input you fed to the perceptron are: (features)

  petal size, petal coloring, and leaf size

If you construct a perceptron (network) it will be:

$x_1, x_2, x_3$ are input neuron, $w_1, w_2, w_3$ are weights (mimicking the strength between biological neurons) and $Y$ is the output neuron.

You may have a question "Why 3 nodes (or neurons) in input and 1 node in output layer?" so I'm explaining that below:

3 neuron in the input layer as we have 3 features(or inputs).

1 neuron in the output layer as we have 1 class (jasmine or not).

Input layer have 3 nodes which will carry you features to output neuron which will classify if its jasmine or not.

Unlike other classification methods, here we should teach the system (like a human brain learns when we first see a jasmine flower).

How will a computer come to know if its a jasmine flower? Answer is, by showing sample features (petal size, petal coloring, and leaf size) of many jasmine to it.

Note: In biology neural network, the neuron get activated when electric impulses exceeds a threshold. Mimicking it, we use a threshold function to active(output one) or not(output zero) a artificial neuron[ threshold value = $\theta$ ].

If the input is a jasmine flower, output neuron will output '1' else '0'.

$
Y =
     \begin{cases}
       \text{1,} &\quad\text{if $\sum_{}^{} w_ix_i>\theta $}\\
       \text{0,} &\quad\text{else}\\
     \end{cases}
$

Note: When we consider $w_i$ and $x_i$  as vector ($W$ and $X$ respectively) its can be written as $Y=W^tX$ (you mentioned it as objective function).

We give sample features (petal size, petal coloring, and leaf size) of jasmine to input neurons $x_1,x_2,x_3$ respectively and tell its a jasmine(set output as one). Meanwhile, the weights $w_1, w_2, w_3$ take some random (initial) values and output $Y$ is found. As we have given a jasmine data to input neuron we expect the output to be one but as weights are taken in random, the output wont be one and an error $E$ is formed.

$E =|ExpectedOutput - ActualOutput|$

This error is propagated back, so that according to the error the weights $w_1, w_2, w_3$ can be updated such that next time error will be much lesser or zero.

This process is called Training, the data used to train the perceptron is called Training data and the network after training is called trained network. The training is called back-propagation algorithm.

It learns from the training data we provide and this trained network can easily classify a new flower(can tell if its jasmine or not).

Read these : Biological neural networks, NPTEL Artificial intelligence, MIT Introduction: The Perceptron


Order-of-growth of selection sort is quadratic, it takes 2secs to sort 100 elements, what will be the expected completion time to sort 200 elements? The above is an MCQ from an online quiz given by my Algorithm lecturer. The available options are 6secs, 4secs, 12secs and 20secs.

The answer I selected was 12secs and it was rejected. The lecturer said the answer should be 4secs and then I started to prove that the answer is greater than or equal to 8secs in the following ways.

1. Using Proportions

T = kN2, where k is an arbitrary constant

2 = k x (1002)       -------------(1)

x = k x (2002)       -------------(2)

(2)/(1) implies, x/2 = 2002/1002 = 22 = 4,

i.e. x/2 = 4 but x = 2 x 4 = 8secs

2. Using 'doubling hypothesis'

NOTE: This is almost identical to the first proof.

Running Time = aNb, where b = 2

2 = 1002a, and a = 2/1002

Then again, Time = aN2 = (2/1002)N2 =(2/1002) x 2002 = 2 x 4 = 8secs

3. Using a slide from a reliable source

As you can see the ratio T(2N)/T(N) = 4 for Selection Sort

Suppose the answer is 4secs,

T(2N)/T(N) = 4/2 = 2 and the order-of-growth becomes linear and this proves the answer 4sec is wrong.

Whereas when you substitute the answer 8secs,

T(2N)/T(N) = 8/2 = 4 and proves that the order-of-growth is quadratic according to this slide.

4. By ploting the curve on a graph

Both the points (100,2) and (200,8) satisfies Y=mX2 and m = 2 x 10-2, and I proved it through equations as well to show that the curve is quadratic and not cubic or else. Also plotted the straight line for the points (100,2) and (200,4).

Finally, the lecturer agrees that the answer should be 8secs but since that option is missing I should select the closest approximation which is 6secs.

But my point is the running time should be greater than or equal to 8secs and at the same time closest to 8secs because there are other basic operations involved as well like variable declaration, initiation, comparison, swap function and for small inputs the time taken for those aren't negligible. So the answer 12secs is my answer in the given context.

Although we can't tell the exact running time, what do you think is the possible range for running time? and, is my argument valid or not?

I thank you in advance!

First off, that's a less than wonderful question.

Second: If the running time is indeed quadratic (with no linear term), the best answer is 8 seconds, not 4 seconds.  Suppose the running time is $T(n) = c \cdot n^2$ for some constant $c$.  Then we know $T(100) = $ 2 seconds.  One can show that

$$T(200) = c \cdot 200^2 = c \cdot 4 \cdot 100^2 = 4 \times T(100),$$

so it follows that $T(200) =$ 8 seconds.

That said, I still don't like the question very much.  Usually when we say that an algorithm has quadratic running time, we mean that its running time is in $\Theta(n^2)$.  That means the running time could be something like $T(n) = c_1 \cdot n^2 + c_2 \cdot n$.  If the running time looks like that, then we don't have enough information to conclude what the running time will be for $n=200$.


Can threads use resources from other processes? This is how I see threads. Please do correct me if I'm wrong:

A thread is a part of a process that runs a sequence of program code. There can be many threads within a process that run different parts of a program (one thread manages keyboard input, one manages auto-saving, one manages printing etc.).
The process allocates resources while the thread(s) are responsible for getting tasks executed by being scheduled for CPU time.

My question is:

  Are threads always bound to their own process or can they exchange
  resources with other threads outside of their process?

Threads are used to handle tasks simultaneously. For example, you keep your computation running in a thread, while another thread is waiting for keyboard input.

Threads inherit the privileges of the process they run in.
If the parent process is authorized to access another process's resources than the thread can do this.
The operating system assigns the process privileges when starting that process.

Whether your threads can obtain resources or not depends on the implementation of threads in your operating systems. In Linux, with some languages such as C, your threads are able to share memory with other processes, and even threads can create other threads. Basically, threads' access to memory is the same as your process. So, threads can create a shared memory with another process and keep communicating with other processes via shared memory space.


Find a CFG for palindromes with at most three c's I'm trying to figure this one out, as I've found the CFG for the palindrome language.
I can't work on a solution that also covers #c(w) <= 3.

Find a CFG for the language
      {w∈{a,b,c} | Reverse(w)=w, #c(w)<=3}?

Would appreciate your help

Call
$$
P=\{w\in\{a,b,c\}^*\mid w=w^R\}
$$
the palindrome language and
$$
Q=\{w\in\{a,b,c\}^*\mid |w|_c\le 3\}
$$
the language of strings having at most 3 $c$'s. Then your language is $L=P\cap Q$ and so is a CFL, since we know the intersection of a CFL (which $P$ is) and a regular language (which $Q$ is) is a CFL. With that out of the way, let's get a CFG for $L$.

You know that a grammar for $P$ can be given by the productions
$$
S\rightarrow aSa\mid bSb\mid cSc\mid a\mid b\mid c\mid\epsilon
$$
Now let's modify this grammar so that it generates palindromes with at most 3 $c$'s. The production $S\rightarrow cSc$ will add two $c$'s to the string being generated, so we want to limit ourself to subsequent productions that generate at most one more $c$. We can do that by changing $S\rightarrow cSc$ to $S\rightarrow cTc$ and forcing $T$ to generate palindromes with at most one $c$. This is simple enough: we can add these productions,
$$
T\rightarrow aTa\mid bTb\mid a\mid b\mid c\mid \epsilon
$$
So finally we have the grammar
$$\begin{eqnarray}
S&\rightarrow& aSa\mid bSb\mid cTc\mid a\mid b\mid c\mid\epsilon \\
T&\rightarrow& aTa\mid bTb\mid a\mid b\mid c\mid \epsilon
\end{eqnarray}$$


Find k nearest neighbors on a sphere Given a set $S$ of $N$ points on a sphere, and another point $P$ on the sphere, I want to find the $k$ points in $S$ that are the closest (Euclidean or great circle distance).

I'm willing to do a reasonable amount of pre-computation.  The solution must be exact and efficient (faster than linear time).

Use the space partitioning approach to nearest neighbor search.

For instance, one approach is to use a $k$-d tree on on the surface of the sphere.  You can express every point on the sphere using spherical coordinates: every point on the sphere has coordinate $(1,\theta,\phi)$.  Thus, we have a 2-dimensional space with coordinates $(\theta,\phi)$.  Now organize your points using a $k$-d tree, where here we are in $k=2$ dimensions.  There are standard algorithms for nearest neighbor search in a $k$-d tree; heuristically, the expected running time is $O(\lg N)$.

You will have to make small modifications to the data structure to reflect that the coordinates "wrap around" modulo $2\pi$, but this is not hard.  The key subroutine used in nearest neighbor search in a $k$-d tree is: given a point $P$ and a "rectangular" region $R$, find the distance from $P$ to the nearest point in $R$.  In your case, the region $R$ is $[\theta_\ell,\theta_u] \times [\phi_\ell, \phi_u]$, i.e., the set of points $\{(1,\theta,\phi) : \theta_\ell \le \theta \le \theta_u, \phi_\ell \le \phi \le \phi_u\}$.  It is easy to compute the distance from $P$ to the closest point in $R$.  This will then let you use the standard algorithm for nearest neighbor search in a $k$-d tree.

Alternatively, instead of a $k$-d tree, you could use any other binary space partitioning tree, or you could look at metric trees, though I don't have any reason to expect them to be significantly better.


Algorithm of split graph $G=(V,E)$ to 2 groups that at least half of the edges are between the groups Can someone remind me the algorithm that split vertex of graph to 2 groups that at least half of the edges are external, I mean between the groups. As I remember it was a greedy algorithm, each time chosen the vertex with highest number of edges, or something similar

The solution and the analysis is given in Section 6.2.1 and 6.3 of the Book: Probability and Computing
Randomized Algorithms and Probabilistic Analysis
Sometimes it is better to refer to a book rather than formulating an answer by ourselves :)


Do functions with slower growth than inverse Ackermann appear in runtime bounds? Some complicated algorithms (union-find) have the nearly-constant inverse Ackermann function that appears in the asymptotic time complexity, and are worst-case time optimal if the nearly constant inverse Ackermann term is ignored.

Are there any examples of known algorithms with running times that involve functions that grow fundamentally slower than inverse Ackermann (e.g. inverses of functions that are not equivalent to Ackermann under polynomial or exponential etc. transformations), that give the best-known worst-case time complexity for solving the underlying problem?

Seth Pettie came up with an algorithm for computing the sensitivity of a minimum spanning tree in time $O(m\log \alpha(m,n))$, improving on an algorithm of Tarjan which computes the same in time $O(m\alpha(m,n))$. (Compare this to Chazelle's $O(m\alpha(m,n))$ algorithm for computing the minimum spanning tree itself.) The sensitivity problem asks to compute, for a given graph and a given minimum spanning tree, by how much each edge weight can change without changing the minimum spanning tree.

(Thanks to Tsvi Kopelowitz for this reference.)