What is the the pumping length for the regular expression (0+0001)((1111)*+(00)*) I have this assignment question to find the pumping length of a regular language (L). The regular expression for the L is given as
$(0+0001)((1111)^*+(00)^*)$

What is the length of the longest string that cannot be pumped?
What is the length of the shortest string that can be pumped, I think this will come naturally when we find the $p$ (the pumping length).

The pumping length of a regular language $L$ is the minimal $p$ such that every word $w \in L$ of length at least $p$ can be split as $w = xyz$ such that (i) $|xy| \leq p$, (ii) $y \neq \epsilon$, (iii) $xy^iz \in L$ for every $i \geq 0$.
As per the answer https://cs.stackexchange.com/a/83727/33673, can we chose $y$ (the middle term in $xy^iz$ to be $1111$ in this case?

It will be convenient to distribute the concatenation to get the equivalent RE
$$0(1111)^\ast + 0(00)^\ast + 0001(1111)^\ast + 0001(00)^\ast.$$
Now note that any such string can be writen as $s = s_i(s_r)^\ast$ where $s_i$ denotes the initial part (i.e. $0$ or $0001$) and $s_r$ denotes the repeated part (i.e. $1111$ or $00$).
We see that $s$ can be pumped if and only if $s_r$ is non-empty and hence, the longest non-pumpable string is $0001$ and the answer is $4$.
Indeed any string of length $5$ or more must have a repeatable part as defined above.
The two shortest strings in the language are $0$ and $000$. We see that $0$ clearly cannot be pumped (as $\varepsilon$ is not in the language) but $000$ can be pumped by repeating the last two zeroes arbitrarily often (and importantly we can also delete them to get $0$).
Hence the answer is $3$.


How does a computer work? I have been a computer nerd for many many years. I can program in quite a few languages, and I can even build them.  I sat down with a buddy the other day and asked how a computer actually takes electricity and does something with it, and we just couldnt figure it out, and Google wasn't much help either.

I mean, how does a computer take a constant flow of electricity and turn it into 1's and 0's and then actually do something with those 1's and 0's like turn a light on for 15 seconds?

I understand gates (AND, OR, NOR, NAND, NOT) and a little about diodes, resistors and transistors, but I figured this would be the perfect place to have it explained in true laymens terms!

Can anybody point me in the right direction or give me a brief explanation?

This is a broad question that does not have an easy answer; it's a long way from electrons skittering along copper wires to rendering a website in Firefox. I will attempt to give you an overview from bottom to top and point you towards the right things to look up.

Encoding Numbers

The basic motivation is to compute things, as in doing arithmetics¹. The first thing to look at is how to represent numbers. There have been many approaches, using decimal or ternary and I think even octal systems, but in the end, binary won out. Now we know we have to build devices that deal with two values -- let's call them $0$ and $1$.

Note that there are also multiple ways to encode numbers in binary. After you build up your first processor, you realise advantages of doing things in certain ways. Popular examples are the two-complement and IEEE floats. For starters, restrict yourself to plain natural numbers.

Gates

Assume we use binary encoding. Think of how you learned adding in primary school and write down the same for binary numbers. As it turns out, the building blocks of Boolean algebra are already there for you; it is easy to build a basic adder (and other arithmetic functions) using logic gates.

How to build such gates is outside of the scope of computer science; eletrical engineering has provided multiple solution using e.g. tubes or transistors. Head over to Electrical Engineering Stack Exchange for questions on this.

Clock and State

Not all gates are equally fast and not all parts of a computation have the same number of gates. Therefore, we have to take extra care that individual operations do not overtake each other. It has proven useful to use a global clock; the result of a given network of gates is the state of the output wires at the end of the cycle (which may change wildly while the gates cascade towards their individual final states).

That means that results of one cycle may have to be stored until the next cycle starts, e.g. if you wire up loops. There are a number of basic elements you can use to varying effect, all build up from gates; some are called flip-flops. Those are also used to build registers, elements that store numbers for as many clock cycles as needed.

Architecture and Commands

Now you have a myriad of design choices to make. What arithmetic operations does your processor provide? What do your commands look like? It may be educational to look at the MIPS architecture whose early forms are easy compared to other designs. Have a look at the plans:

Original from http://ube.ege.edu.tr/~erciyes/CENG311

Essentially, it's fetching and and disassembling commands, a set of registers, an ALU and control. Commands encode which ALU operation to perform on which operands (by the number of the register they are held in), how to manipulate the program counter² or which register to load/store from/to memory³.

Further Considerations

By now you have a working processor in the modern sense, assuming you figured out how to build a memory and a way to feed it commands. On its way to a modern machine, many choices have to be made. Here are some:

Do you want a von Neumann architecture or would you rather keep commands and data separate?
Do you want regularity and simplicity or abstraction and space economy in your instructions?
Depending on your memory implementation, you might want to have caches.
Do you want your processor to handle multiple operations at the same time using a pipeline?
Are all operations (and memory addresses) available to all programs, or do you have an operating system?
How do you implement I/O?

Alternatives

The above is heavily influenced by how history turned out. In a different world with different minds, computers may work differently. In fact, there is a plenty of models of computation, some of which have advantages that make them useful as abstraction for real machines in many cases. There are also attempts to imitate the way our brains work, that is to enable neural computing, or more generally to exploit problem-solving and information-storing strategies observed in nature, most prominently DNA and quantum computing.

So maybe (hopefully?) the information above is all ancient history another 50 or 100 years from now.

All the fancy things we do with computers today are broken down into many small arithmetic tasks which the processor executes one by one.
If your model allows the program to manipulate control flow, this would be the memory address the processor gets the next instruction from. You can also conceive machines that only read a fixed set of instructions from, say, a tape. In fact, early implementations did that. No jumps meant no loops; a program was a completely unrolled/unfolded series of instructions depending on the data. Obviously, being able to use the same program for multiple input data is more powerful.
Assuming you have memory; your processor works fine without but can then only deal with so many values at once. Early computers did read in all their data from tapes and kept them in registers. There was no memory, let alone writable, persistent storage as we know it today.


oone exmple in hash topics? Example: Suppose $H:${$1,...,n$} $\rightarrow ${$1,..,n$} be a uniform hash function. for input $x$, $z$ is equal to number of trailing zero in the right side of $H(x)$. for $0 \leq c \leq 1$ what is the order of probability $ z \geq c \log n$? $C$ is constant here.
Answer: $O(1/n^c)$
How  this this is can be achieved?
I think this is same with this question:
Source: introduction to algorithm CLRS Page 652 Ex.11-C

Let $A_n\subseteq \{0,1\}^{\log n}$ denote the set of binary strings of length $\log n$ with at least $c\log n$ trailing zeros on the right (here I assume that $\log n$ in an integer and $0\le c\le 1$). Note that $|A_n|=2^{\log n -\lceil c\log n\rceil}\le 2^{(1-c)\log n}$. Since $H:\{0,1\}^{\log n}\rightarrow \{0,1\}^{\log n}$ is a one to one function, $\Pr_{x\sim U_{\log n}}\left[H(x)\in A_n\right]=\frac{|A_n|}{2^{\log n}}\le\frac{1}{n^c}$, where $U_k$ is the uniform distribution over $\{0,1\}^k$.


Communication Complexity for Product Distributions In general for the (two-party) set disjointness problem for inputs of length n, we know that the parties need to communicate $\Omega(n)$. Surprisingly, today I discovered (if I understood correctly) that this is not true for product distributions, i.e. when Alice's and Bob's inputs are chosen independently from arbitrary distributions! In this paper, for example, they provide an upper bound with communication complexity $\mathcal{O}(\sqrt{n}\log(1/\epsilon))$, where $\epsilon$ is some error term not relevant for the question here.
Now I am curious about whether gaps exist for other well known communication complexity problems.

Question: What other well-known problems exhibit a gap between the communication complexities when one considers arbitrary input distributions and product distributions. Are there similar results for inner products or intersections?

Set disjointness is easier for product distributions since the hard distribution for set disjointness is very far from being a product distribution. What do we require from a hard distribution $(X,Y)$ for inner product? We want each of $X,Y$ separately to be quite random, and we want $X\cdot Y$ to be mostly zero, say $X \cdot Y$ contains at most a single $1$. This cannot be accomplished by a product distribution. While you can get the $X \cdot Y$ property, this implies that each of the two inputs will be very biased. Conversely, if the inputs $X,Y$ are quite random, then $X \cdot Y$ will have many $1$s.

The inner product function doesn't suffer from the same issue. Indeed, it seems that the hardest distribution is the uniform distribution. You can prove a linear lower bound using the discrepancy method – this is standard, and uses a bound on the discrepancy known as Lindsey's lemma.

Sherstov came up with an optimal gap example in his paper Communication complexity under product and nonproduct distributions. His function is a random function, chosen so that there are no large monochromatic $1$-rectangles. The end result is a function whose randomized communication complexity is $\Omega(n)$, but for any product distribution, the randomized communication complexity is $O(1)$.


Turing Machine states When defining a Turing Machine formally, you enumerate its states. But I don't understand what states a TM can be in. Reading, Writing, and moving the head are the only ones that come to mind.

Specifically, the turing I am trying to describe behaves like this:

    WHILE the symbol under the FH head is not $ DO
        IF this symbol is not marked 0 THEN write it on the tape
        ELSE write the symbol 1 on the tape
            Read the next symbol (which is a 0) and write a marked 0 on the tape
    Write $ on the tape

Where FH is the reading head which begins on the far left of the tape, and BH is the writing head which begins on the blank space after the last symbol on the tape. Once a cell is read or written into, the head in question moves one cell to the right.

The starting configuration for the TM is this: 100!0110\$ where the 0! indicates that the 0 is a marked symbol. The FH head begins on the first 1, and the BH head begins on the blank cell after the \$. The ending configuration for that TM with that input is then 100!0110\$1010!110\$

So, when describing this TM, what would its states be? Thanks!

Raphael is correct in stating the states of a TM is a theoretical construct defining the operating program.  What you are thinking of ("reading", "writing", and "moving") are operations the machine can do out of a particular state.

Wikipedia has a nice little write up about it.  Explaining that each state, tells the machine what next operation to perform based off of a current state.


Closest Pair of Points Algorithm - Fortune and Hopcroft I am interested in implemented the deterministic ${O(n\log(\log(n)))}$ algorithm for the closest pair of points problem described here by Fortune and Hopcroft: https://ecommons.cornell.edu/bitstream/handle/1813/7460/78-340.pdf
In particular I would like to have a solution to the two-dimensional case.
They say: "The algorithm is based on the following observation: suppose we can find an interval size such that at most one point falls within each interval, and there are two nonempty adjacent intervals. Then to determine the closest pair we need only examine, for each point, the intervals surrounding the point". And for the one dimensional case which they describe in detail, the initial interval size is selected by taking (max(S) - min(S))/n where ${S}$ is the collection of points and ${n}$ is the number of points.
They claim the extension to higher dimensions is "obvious", but it's not at all clear to me how this above line might be generalised.
Does anyone have any suggestions? Many thanks.

One thing that you might not be aware of is that there's a 'hidden' exponential factor (it's explained on page 3). In $k$ dimensions the runtime is $O(kn \log(\log(n)) + 3^kn)$, as when you partition $k$-dimensional space into hypercubes each cube has $3^k - 1$ neighbors.
The rest of the algorithm really is 'obvious' then: you split your space up in hypercubes (which is just a fancy word for splitting up each dimension separately into intervals). Each point will then map to exactly one cube, and the rest of the algorithm follows.
E.g. suppose our interval size is $1$ and our domain is $[0, 10)$. Then in 1D we have that the point $3.4$ maps to bucket $3$ and $8.8$ maps to bucket $8$. In three dimensions if our interval size and (per-dimension) domain is the same, we have that $(2.3, 8.4, 4.4)$ maps to bucket $(2, 8, 4)$ and $(4.1, 5.2, 9.5)$ maps to $(4, 5, 9)$. So you end up with three-dimensional buckets but the algorithm hashes the buckets afterwards so that doesn't matter.

If you have anything more than two or three dimensions my suggestion would be to look for another algorithm.


Show that functions in O(1) can't grow faster than their composition with themselves Let $f(n)$ be a function s.t $f(n)\geq 1 $ for every $n$.

I want to disprove that if  $f(n) = \omega (f(f(n)))$
 then it means that  $f(n) = O(1)$.

I thougt of 2 approaches to show that this statement is incorrect:

Give an Example of a function that $f(n) = \omega (f(f(n)))$ for it,

for example: $f(n) = \sqrt n$

and then I'm supposed to get a contradiction, and show that $\sqrt n \neq O(1)$
but that's the step I'm stuck at, but I'm not sure how that contradiction is derived. I mean formally, because I understand it by intuition.

Start with the function that suffice $f(n) = O(1)$  and then show that it's impossible to get the condition under that function (It's sort of going from the end to the beginning)

what's the right approach and how do I get it right?

To complete the first approach and show that $\sqrt{n}\notin O(1)$, you just need to show that the statement "There exist constants $c$ and $n_0$ such that, for all $n\geq n_0$, $\sqrt{n}\leq c\cdot1$" is false. That is, you need to show that, for any $c$ and $n_0$, there is an $n\geq n_0$ such that $\sqrt{n}>c$.  For example, you can take $n=n_0+c^2$ (or $\max\,\{n_0,c^2\}$, if you prefer).

I don't really understand your second approach. If $f(n)=O(1)$, it's perfectly possible that $f(n)\in \omega(f(f(n)))$: take any constant function, for example.


Must Neural Networks always converge? Introduction

Step One

I wrote a standard backpropegating neural network, and to test it, I decided to have it map XOR.

It is a 2-2-1 network (with tanh activation function)

X1  M1
        O1
X2  M2

B1  B2

For testing purposes, I manually set up the top middle neuron (M1) to be an AND gate and the lower neuron (M2) to be an OR gate (both output 1 if true and -1 if false).

Now, I also manually set up the connection M1-O1 to be -.5, M2-O1 to be 1, and
B2 to be -.75

So if M1 = 1 and M2 = 1, the sum is (-0.5 +1 -0.75 = -.25) tanh(0.25) = -0.24

if M1 = -1 and M2 = 1, the sum is ((-0.5)*(-1) +1 -0.75 = .75) tanh(0.75) = 0.63

if M1 = -1 and M2 = -1, the sum is ((-0.5)*(-1) -1 -0.75 = -1.25) tanh(1.25) = -0.8

This is a relatively good result for a "first iteration".

Step Two

I then proceeded to modify these weights a bit, and then train them using error propagation algorithm (based on gradient descent). In this stage, I leave the weights between the input and middle neurons intact, and just modify the weights between the middle (and bias) and output.

For testing, I set the weights to be and .5 .4 .3 (respectively for M1, M2 and bias)

Here, however, I start having issues.

My Question

I set my learning rate to .2 and let the program iterate through training data (A B A^B) for 10000 iterations or more.

Most of the time, the weights converge to a good result. However, at times, those weights converge to (say) 1.5, 5.7, and .9 which results in a +1 output (even) to an input of {1, 1} (when the result should be a -1).

Is it possible for a relatively simple ANN which has a solution to not converge at all or is there a bug in my implementation?

(I assume by "error propagation" you mean what I call "error back-propagation.")

On page 231 of Neural Networks (by Haykin), he states that back propagation always converges, although the rate can be (in his words) "excruciatingly slow."

I think what you are asking though is not whether the algorithm will always converge, but whether it will always converge to the optimal answer. And unfortunately, it won't. Even in simple cases like yours, it's entirely possible that there are local minima which are not global minima.

Dealing with local extrema is a hugely important topic in optimization, and you can find a plethora of advice on how to deal with it. One of the most common is what it sounds like you're doing: random restarts (i.e. just run the algorithm multiple times, each starting from a random place).

To figure out if there's a bug in your code, I would print out the error term and verify that it decreases at each iteration. If so, then you're probably just hitting a local minima.


Every language that is reducible to a language in $\Sigma_i^p$ is also in $\Sigma_i^p$ . How? The complexity class $\Sigma_{k}^{p}$ is recursively defined as follows:
\begin{align}
\Sigma_{0}^{p} & := P, \\
\Sigma_{k+1}^{p} & := P^{\Sigma_{k}^{p}}.
\end{align}

Why is every language that is reducible to a language in $\Sigma_i^p$ also in $\Sigma_i^p$?

This comes in the proof of the theorem: If there is a PH-complete problem, then PH (the polynomial hierarchy) collapses.

First of all, there are many reduction concepts, but I assume you mean the polynomial reduction ($\le_p$).

The complexity class $\Sigma_{k}^{p}$ is recursively defined as follows:
\begin{align}
\Sigma_{0}^{p} & := P \\
\Sigma_{k+1}^{p} & := P^{\Sigma_{k}^{p}}
\end{align}

Let $A$ and $B$ be two languages over alphabets $\Sigma_A$ and $\Sigma_B$, respectively. Let $k \in \mathbb{N}_0$, $B \in \Sigma_{k}^{p}$ and $A \le_p B$. Since $A$ is polynomially reducible to $B$, there exists a function $f: \Sigma_A^\star \rightarrow \Sigma_B^\star$ (computable in polynomial time), such that $x \in A \Leftrightarrow f(x) \in B$. So we have an algorithm that decides $A$, which first transforms the input for $A$ to an input for $B$ using $f$, and then uses the algorithm for $B$ on the transformed instance. Therefore, $A$ is in $max\left\lbrace P, \Sigma_k^p \right\rbrace$.

If $k = 0$, $\Sigma_k^p = \Sigma_0^p = P$, then $A$ is also in $P = \Sigma_0^p$, since the transformation requires at most polynomial time and $B$ is in $P$.

If $k > 0$, the transformation is negligible and $A \in \Sigma_k^p$.


What does valid method overriding mean? In Types and Programming Languages by Pierce, from p257 to p258, about featherweight Java,

The predicate override(m, D, C→C0) judges whether a method
m with argument types C and a result type C0 may be deﬁned in a subclass of D. In case of overriding, if a method with the same name is declared in the superclass then it must have the same type.

I am not sure   what the predicate override(m, D, C→C0) means.
Does the predicate apply only to the case of overriding? (The first sentence doesn't imply so.)
Isn't it always possible to define a method with any name and any type in any class?

In case of non-overriding, that is true.
In case of overriding, that is also true.

Could you   give examples where it is possible and where it isn't?
Figure 19-2: Featherweight Java (auxiliary deﬁnitions) says:

Valid method overriding:
If mtype(m, D) = E→E0 implies C = E and C0 = E0, then
override(m, D, C→C0 )

How can mtype(m, D) = E→E0 imply C = E and C0 = E0?
mtype(m, D) = E→E0 only means that class D has a method m whose type is E→E0.
Why is "mtype(m, D) = E→E0 implies C = E and C0 = E0" a condition for override(m, D, C→C0 )?
Thanks.

The important sentence in the first quote is

  In case of overriding, if a method with the same name is declared in the superclass then it must have the same type.

So if you have

class C1 { ... }
class C2 { ... }

class Cls {
    C1 foo(C2 x) { ... }
}

override(foo, Cls, (C2)->C1) holds but override(foo, Cls, (C2)->C2) doesn't; the subclass

class SubCls extends Cls {
    C2 foo(C2 x) { ... }
}

is illegal. In FJ, you can't have

class SubCls extends Cls {
    C2 foo() { ... }
}

either, unlike in Java.

  If mtype(m, D) = E→E0 implies C = E and C0 = E0, then override(m, D, C→C0 )

This is implicitly quantified "for all E and E0". If mtype(m, D) is undefined, then mtype(m, D) = E→E0 is always false, so it implies anything. If it's defined, then "mtype(m, D) = E→E0 implies C = E and C0 = E0" is equivalent to mtype(m, D) = C→C0.

So it ends up being the same as

    If mtype(m, D) = C→C0 or mtype(m, D) is undefined, then override(m, D, C→C0)

(unless I went wrong somewhere)


Is Coq synthetic or analytic? In CMU's HoTT course, lecture 1, which can be found here: https://scs.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=0945cc7f-48b7-4803-81af-e7193a3f461d

At 33:52, Harper was giving parallel comparison between synthetic theories and analytic ones, and when he reached PL theory, he said Coq is analytic and said Coq only proves a language in its grammar but not the parser itself.

I have a strong desire to disagree somehow but I don't have a clear idea why I would want to do that. I believe that Coq is very synthetic, so are any other proof assistants based on dependent type theory, because all these languages do nothing but build programs. We can also express axiomatic algebra in Coq by using type classes for example, and concretize whenever suitable. This pattern is especially the case in Agda.

So my question is, was Harper right? If he's right, which part of my view causes my misunderstanding?

The remark is about one specific usage of Coq, namely formalization of programming language theory.

Let us first make clear the distinction between synthetic and analytic:

In a synthetic approach to a subject we say that there are things whose basic properties and structure are postulated in one way or another. We then study these things by relying only on the postulated properties and structure.
In an analytic approach to a subject we discover that there are certain things. To learn more about them, we take them apart, we study how they are made and we analze them. This way we discover their properties and structure.

How would one study a programming language in these two ways?

Synthetically, we would postulate the constituent parts of the language (there are terms, there are types), their basic structure (these are the ways of building terms) and basic properties. We do not ask what the terms and type are made of, or whether the terms are trees or strings, or whether the collection of types is built in a particular way.

Analytically, we would start with a mathematical setup that allows us to do many things, such as use inductive definitions to construct mathematical objects. We woudl build terms and types as particular inductively defined sets or types. Then we would study their structure, how we can transform them, etc.

It should be clear that Coq is of the analytic kind. When you implement a programming language in Coq, you define inductive types of terms and types. Then you analyze them using induction, define operational semantics as a recursive function on the syntax of terms, etc.

On the other hand, Twelf is of the synthetic kind. We postulate that there is a type of terms and a type of types, but we do not tell Twelf that these are inductive types (there's no way to say that in Twelf). We define operational semantics by providing basic transition rules. There is no mention of recursively defined functions (there's no way to define functions in Twelf), we just rely on the postulates that we wrote down.

You should compare the above situation to planar geometry. Hilbert's approach to geometry is synthetic (but his ideas are rooted in Euclid), Descartes' are analytic. The analytic geometry is so called because a line is not a primitive concepts: it has an inner structure, namely it is a set of points.


How does a GPU get data from a CPU? From what I’ve read, the CPU has to send the data to the GPU before the GPU can do anything with it. But, if that’s the case, won’t any time saved using the GPU be negated by the time taken to transfer that data? Wouldn’t that kind of defeat the whole purpose of a GPU?

It depends.  If it's a lot of data and a little bit of computation, yes, there is no net savings.  If it's a little bit of data and a lot of computation, no, there is a net savings.  It all depends.  Normally a GPU is used for situations where the amount of computation time saved greatly outweighs the time to transfer the data -- such as training machine learning models, or rendering complex graphics.


Is there a model of computation based on discrete event dynamic systems? I asked a question here about discrete event dynamic systems. They are systems whose state evolution depends on asynchronous events. It can be combined with flow to produce a hybrid system.

There must be an event-based model of computation, since it is so applicable to user interactions. Could someone point me in the right direction? Is there a canonical model of computation for event-based systems?

Let's first look at what Wikipedia says:

the theory of computation is the branch of mathematics and computer science that deals with how efficiently problems can be solved on a model of computation;
a model of computation is a model which describes how a set of outputs are computed given a set of inputs; they can be classified into three categories:

Sequential models, including

Finite state machines
Pushdown automata
Turing Machines

Functional models, including

Lambda calculus
Recursive functions
Combinatory logic
Cellular automata
Abstract rewriting systems

Concurrent models, including

Kahn process networks
Petri nets
Synchronous Data Flow
Interaction nets

All of these are mathematical formalisms to model the behavior of discrete event systems.  To be more precise, for each of them, there is a whole family of related formalisms, and many more formalisms exist outside of these families, thousands or tens of thousands in all, ranging from very popular to very obscure.

You're looking for ones that are event-based. Flow-based models are often considered to be event-based: what flows in can be regarded as a stream of events. Furthermore, finite automata were conceived of as an event-based formalism: they were introduced in a memo titled ''Representation of Events in Nerve Nets and Finite Automata''. Concurrent modeling techniques (e.g. Kahn process networks, Petri nets, Communicating Sequential Processes) are often based on finite state machines or variants of that idea. Techniques based on communicating state machines operating in parallel are popular in industry. Their models consist of components passing messages, or events, or data items, to each other over channels. This is really flexible: you can use it for modeling events, or dataflow, or literal message passing, or the flow of abstract information in, let's say, some office workflow process.

You say you're looking for something other than flow-based models, something suitable for describing user interaction. I've worked with modeling technology for embedded systems that makes this distinction. It has two kinds of communication:

asynchronous: used for data flow processing or event flow processing where data or events flow in on a streams, have a bit of processing done, then flow out on another stream
synchronous: procedure calls: one party instigates communication and waits for the response, the other party responds; used for interaction where the volume of communication is low and the calling party needs a result to continue, for instance, user interaction

I think most proponents of concurrent modeling techniques will tell you they don't need to have synchronous communication in their technique because they can emulate it. For instance, this

is how you express a synchronous call in the Petri-net based process modeling tool I used to work on. As you can see, the circles represent states or conditions, but also data items, while the squares represent state transitions. Control flow and data flow are both expressed, but not distinguished within the modeling technique. But this is unusual: techniques based on communicating state machines do separate state changes (within the machines) from event/data passing (between the machines).

Furthermore, there's a movement in systems design and programming that says to avoid synchronous communication in the first place. Systems should be concurrent and event-based by design, all the waiting for replies on synchronous calls just holds up your components for no other reason than your own ineptness at design, synchronous calls are just mental laziness induced by having looked at inherently sequential systems for too long. This approach to interactive applications has gained a lot of traction in recent years.

So many people in this area will say you don't need separate modeling constructs for user interaction: a user input and output to the user are just communications, flowing on communication channels between two system components, one of which is the user. It's message passing and all you need is a message passing formalism.

An alternative to modeling I/O as messages within the system is to model inputs and outputs as properties of state transitions. For instance, this is done in Mealy machines and I/O automata. This is used for model-based testing: the expected behavior of the system is modelled using an I/O automaton and used to generate test cases that are then used to verify whether the actual system meets the specifications. This approach is really focused on interactive systems, not flow-based systems.

So there are many approaches to choose from; none of them can be said to be canonical, but approaches based on some form of state machines are the most popular, so if you'd insist on calling anything canonical, I'd say it's the state machine.


Why is $n \log \log n$ not tightly bounded by $n$? I don't understand why $n \log \log n $ is not $\Theta (n)$.

Suppose we give $n$ a value of $10,000$. Then $n \log \log n$ is $6020.6$. So isn't $n \log \log n$ upper- and lower-bounded by $n$, as $n \log \log n \geq Cn$?

As $n$ grows bigger, the ratio between $n\log\log n$ and $n$, namely $\log\log n$, tends to infinity. Hence it is not possible to upper bound $n\log\log n \leq Cn$ for any constant $C$. If you stare at this inequality, you discover that the constant $C$ must satisfy $\log\log n \leq C$ for all $n$, yet the function $\log\log n$ is not bounded.


Given a specific computer system, is it possible to estimate the actual precise run time of a piece of Assembly code this is a piece of Assembly code

section .text
    global _start       ;must be declared for using gcc
_start:                     ;tell linker entry point
    mov edx, len    ;message length
    mov ecx, msg    ;message to write
    mov ebx, 1      ;file descriptor (stdout)
    mov eax, 4      ;system call number (sys_write)
    int 0x80        ;call kernel
    mov eax, 1      ;system call number (sys_exit)
    int 0x80        ;call kernel

section .data

msg db  'Hello, world!',0xa ;our dear string
len equ $ - msg         ;length of our dear string

Given a specific computer system, is it possible to predict precisely the actual run time of a piece of Assembly code.

I can only quote from the manual of a rather primitive CPU, a 68020 processor from around 1986: "Calculating the exact runtime of a sequence of instructions is difficult, even if you have precise knowledge of the processor implementation". Which we don't have. And compared to a modern processor, that CPU was primitive.

I can't predict the runtime of that code, and neither can you. But you can't even define what "runtime" of a piece of code is, when a processor has massive caches, and massive out-of-order capabilities. A typical modern processor can have 200 instructions "in flight", that is in various stages of execution. So the time from trying to read the first instruction byte, to retiring the last instruction, can be quite long. But the actual delay to all other work that the processor needs doing may be (and typically is) a lot less.

Of course doing two calls to the operating system makes this completely unpredictable. You don't know what "writing to stdout" actually does, so you can't predict the time.

And you can't know the clock speed of the computer at the precise moment you run the code. It may be in some power saving mode, the computer may have reduced clock speed because it got hot, so even the same number of clock cycles can take different amounts of time.

All in all: Totally unpredictable.


Stability for couples in the Stable Matching Problem In the Stable Matching Problem, it is stated that there can exist cases where the $m$ list of men can be content with their decisions, yet the list of $f$ cannot when the algorithm is run with men's proposals.

From what I read, an unstable match occurs when $m$ and $f$ prefer each other to their current partners.

I am a little lost in the definition of Stable Matching for this case. I'm going over the slides here.

  Is a pair $(m, f)$ stable as long as the men are content even though the female's preferences have not been matched?

Yes, it is stable. It doesn't need to assign the optimal choices for both sides. To break a marriage you need two willing parties, unhappiness of one side in a marriage doesn't make it unstable here.


$C_1 \subseteq C_2$ implies $C_1^A\subseteq C_2^A$? $C_1 \subseteq C_2$ implies $C_1^A\subseteq C_2^A$?

I've given a caveat that one shouldn't make this implication blindly and it shall be justified.

I can think of examples such that $C_1^A \subsetneq C_2^A$ and examples such that $C_1^A = C_2^A$.

but could it be that $C_2^A \subset C_1^A$? I can't see how.

So what's the point of this caveat?

A proof technique is (informally) relativizing if the results it generates also hold relative to an oracle. Not all proof techniques are relativizing. Perhaps the best known example is $\mathsf{IP}=\mathsf{PSPACE}$, which uses the technique of algebraization. Although $\mathsf{PSPACE} \subseteq \mathsf{IP}$, there is an oracle $O$ such that $\mathsf{PSPACE}^O \not\subseteq \mathsf{IP}^O$ (see this question on cstheory).


Longest path in directed graph cyclic graph where each node has one children Consider given directed unweighted cyclic graph with $N$ nodes, and $N$ edges, and each node has at most one out-going children. Find the longest path.

Example

Consider the following graph, the path $2, 3, 1$ is the longest covering all 3 nodes.

What I think for the solution

Because every node has at most one children we form some type of equation that for node $a$, and it's children $b$, the path starting from node $a$ = path to start from $b + 1$, but I think because there are cycles this wont work.

As rus9384 & you seemed to have figured out in the comments, there exists an $O(N)$ solution to the problem.

First, apply the well known algorithm to find Strongly Connected Components in the graph in $O(N)$. Then, after collapsing all such components into single nodes, you can slightly modify the algorithm to find the Longest Path in a DAG to get your answer in $O(N)$ time.


FSMs and Boolean dynamical systems Is it not always possible to represent a Finite State Machine (FSM) by a Boolean dynamical system?

A Boolean dynamical system is defined by a Boolean map $F\colon B_{0}^n\to B_{0}^n$ (where $B_{0}$ is the-two element Boolean algebra $\{0,1\}$ with operations of $\lor$ (OR), $\land$ (AND) and $\neg$ (NOT)) as

$$x(k+1)=F(x(k)),$$

which is the state update map of the FSM after representing the state space of an FSM as a subset of $B_{0}^n$.


What happens if the holder of a lock tries to acquire a lock? In a system, suppose there is a process and a resource with only one instance.

Let us assume that the process holds the instance and requests the same instance of that resource. Will there be a deadlock? Under what circumstances?

Resources that can only be used by a single process at a time are usually protected by a lock. If the process that currently holds the lock attempts to acquire it a second time, what happens depends on the type of lock.

If the lock is reentrant, then it can be acquired multiple times by the same process. The process will need to call the release function as many times as it called the acquire function.
If the lock is not reentrant (for example if it's a simple semaphore or an atomically-modified boolean), then a second attempt will block. You can call this a single-process deadlock.
In some mutex implementations (probably not in what is studied in Concurrency 101 though), a process can acquire the same lock more than once, and the second time is a no-op, so the process must only call the release function once. Another thing that sometimes happens is that calling the acquire function from the same process twice puts the implementation in a bad state after which anything can happen — the semantics doesn't define what happens in that case.

Thus, it depends on what semantics your locks have. You can build non-reentrant locks on top of reentrant locks or vice versa if all you have is the wrong kind for what you want to do.


How to prove that $n^d$ is $O(b^n)$ from $n$ is $O(2^n)$, given that $d>0, b>1$? I'm reading Rosen's Discrete Mathematics and Its Application, at Page 212, it's about the "Big-O" notation using in computer science.

This is the description in the book:

And here is my reasoning:

Since there wasn't a program with "negative" steps, I only consider the case $n>0$.

With $n$ is $O(2^n)$, there exist two constants $C$ and $k$ such that $$n \le C \cdot 2^n, \text{when } n>k.$$

Now take logarithms on both side we have $$\log{n} \le \log{C} + n$$

Multiply both side with $d$, we get $$d \cdot \log{n} \le d\cdot \log{C} + d \cdot n,$$

Then I stuck.

Please give me some hints about how to do next... Thanks a lot!

You cannot directly prove $f(n)^d$ is $O(b^n)$ from the fact that $f(n)$ is $O(2^n)$. For example, $2^n$ is $O(2^n)$, but $(2^n)^d$ is not necessarily $O(b^n)$.

So forget the fact that $n$ is $O(2^n)$. You should prove $n^d$ is $O(b^n)$ directly.

You may find a correct proof here.


Difference between Turing machine and Universal Turing machine I've read what a Turing machine and a UTM are, but I don't get the difference. What can a UTM do which a normal Turing machine can not?

A universal Turing machine is just a Turing machine whose programming simulates other Turing machines.  That is, the input to the UTM is a description of a Turing machine $T$ and an input for $T$, and the UTM simulates $T$ on that input.

It's universal in the sense that, for any problem that can be solved by Turing machines, you could either use a Turing machine that directly solves that problem, or you could use a UTM and give it the description of a TM that directly solves the problem.

If you like, a UTM is an interpreter for (all) Turing machines.


Blob detection as Constraint satisfaction problem? In image processing I have a black and white image which is represented by matrix {0,1}, I have to find blob (a region of connected pixels) in it. I'm confused, can this problem be reduced to Constraint Satisfaction problem (as p/np complete)?

Black and white image with white blobs.

The constraint satisfaction problem (CSP) is NP-complete.  Identifying blobs is a question about graph connectivity which is in P.  Therefore, yes, the question you're asking reduces to CSP but this doesn't tell you anything useful: it just says that CSP is at least as hard as this problem but it might be harder.  (In fact, it is strictly harder if P$\neq$NP.)  Since your problem is in P, it is not (believed to be) NP-complete.

A related question is whether the problem can be expressed directly as a CSP without needing a reduction.

If a blob is any connected region then, in particular, any blob contains two adjacent pixels and any two adjacent pixels are part of a blob.  Therefore, if all you want to know is whether an image contains at least one blob, this is a constraint satisfaction problem.

However, if you want to identify a whole blob (e.g., output a list of all the pixels within some blob) or identify or count all the blobs, the problem is no longer a CSP.  The reason for this is that CSPs are not able to express connectivity conditions: there is no CSP in a finite constraint language that says "This graph is connected" because every instance of CSP is equivalent to a first-order formula and first-order logic can't tell the difference between connected and disconnected graphs.


How do web browsers find out the MAC address? While reading through my textbook, I discovered that if you want to access a particular web page, your web browser will find out the IP address of the web server that hosts the web page and try and connect to it. It will then transfer a copy of the web page to your computer so that you may view it.

However, my concern is... I have discovered that the IP address enables data to be sent to the device's local area network, but in order for the data to be sent to the device itself, the MAC address is needed to transfer data from the local area network to the device.

BUT, in my textbook, nowhere does it say how the computer's web browser finds out the MAC address of the web server. It says that the computer finds out the IP address of the web server by using the Domain Name System (DNS).

So, how does the computer find out the MAC address of the server?

Answers would be much appreciated.

So, how does the computer find out the MAC address of the server?

It doesn't. The MAC address only has validity inside a local area network (LAN), which, as the name says, is local. Unless the destination IP address resides in the same network as your machine, what it does is create a packet destined to the target IP address and forward it to its default route, usually your router. (To do so it must obtain the router's MAC address too using ARP—but this is a different matter.) Obtaining the server's MAC address is the task of the final hop which is in the same LAN as the server; a machine notices it is the final hop by checking if the destination IP lies in the same subnet as its own.

It is only when the destination IP is in the same local network as your machine that the MAC address needs to be obtained. (And this is done using ARP too.) In this case, your computer just happens to be the final hop in the route to the server.


Calculating attributes' values in the semantic analysis stage I'm reading through the book : "Compiler Construction: Principles and Practice". In chapter 6 : semantic analysis, an example about attribute grammars is given. The example is of a simple integer arithmetic expressions (I posted a picture because different fonts means different things as you may know):

where the bold Courier font is a token and the Times New Roman is grammar.

Now this parse tree represents the expression: (34-3)*42 which is 1302. I know that every attribute rule corresponds with a grammar rule, and we're actually starting with the rule exp->term because it is what it fits the given expression, but I just don't understand how did the compiler know the value in the first place? When was the value computed? How does the compiler start implementing the semantic analysis? did it start from the bottom where the number token is? I hope I made it clear.

The computer is using the rules in the left-hand column of your table. This amounts to a bottom up approach: to compute the value of a node you first compute (recursively) the values of all its children, and then you use the given rule to compute the value of the node itself.


Is Math a MUST in computer science specificly in Software Development for Web servers I know math is necessary for application development in simulation software and else.

But I'm learning Python and trying to go deep in PHP, and like to develop applications and extends web servers' capability.

I'm before a big dilemma that whether to learn math professionally or not. I have tried my best to avoid being general on my question.

I have asked this question here because I want to learn it from roots and deal with its scientific aspects.

Your question seems to be based on the misunderstanding that software development = computer science.  They are not the same thing. Your questions starts out asking about software development, but then ends by asking about the roots and scientific aspects thereof, which brings you to computer science, so it is not entirely clear what you want.

If you want to focus on software development, then math is not required (though it will often come in handy).

If you want to focus on computer science, then it is absolutely essential.


How to conceptually represent attributes (characteristics) of an object in logics? I am reading about/working on the knowledge representation using OpenCog framework http://wiki.opencog.org/w/OpenCog_Framework which essentially is special kind of probabilistic logic (s.c. PLN - Probabilistic Logic Networks) that smoothly generalizes crisp logic (by assigning strength and confidence to the crisp truth value).

My question is - how to represent attributes in logic (in OpenCog or in any other logic). E.g. I want to express the statement 'An apple #1 has price 1$' (#1 is Apple; #1.price=1$). How can I do this in any logic?

My current solution is that I need to define 3 entities: apple a1, price p1, 1$_value v1 and enter those entities into whole-part relationships: whole_part_relation(a1, p1), whole_part_relation(p1, v1). Those relations are for instances and apparently similar relations can be formed for classes (concepts) as well. Is my representation of attributes by whole-part-relationships acceptable?

OpenCog has list of all supported types of terms (s.c. Atoms) and their relationships (e.g. Links) http://wiki.opencog.org/w/Category:Atom_Types but one can see that attribute link/relationship is not first class citizen in this logic as it is not in many other logics as well.

So - my question is - how to represent attributes in the logics in which attributes are not first class citizens?

There is need to formalize software development, to mode real world, to create knowledge bases for e.g. robotics and therefore the conceptualization of notion of attribute (characteristic) is important!

For this discussion, I'll use classical first-order logic. I'll interpret your term "first-class citizens" to mean those objects which can be quantified over or passed as arguments to predicates and functions. The examples provided below are toy examples, purely for expository purposes. Have a look at the leading AI textbook which gives a much more extensive, proper introduction to this subject.

There are often many ways to formalize a given statement in logic. Let's consider your example 'An apple #1 has price 1$'. There are some naive ways that come to mind:

price(apple1)               this is a function which yields the price
Price(apple1,80)            this is a predicate

As for your question, "Is my representation of attributes by whole-part-relationships acceptable?", it at least raises eyebrows. Generally, whole-part relationships should reflect the notion that the part is part of the object structure itself, not some attribute of the object. So while has-part(apple,stem), has-part(apple,skin), has-part(apple,seed) seem reasonable, has-part(apple,price) does not.

Now for your main question, "how to represent attributes in the logics in which attributes are not first class citizens?" you can use either functions or predicates. Examples are given under the paragraph above describing some ways one can formalize a given statement in logic.


Mutation and crossover operations in discrete differential evolutionary operations? I need to use discrete differential evolutionary algorithm for assigning discrete values from set size $L$ to vectors of size $D$ where $L$ could be smaller, equal or larger than $D$. Elements of vector $X$ could take the same values of other elements.  My question is if we have a population of size $NP$ with each vector $X$ in the population of size $D$. How do we actually apply the mutation operand:

$$V_{j,i}^{G+1} = X_{j, r_1}^{G} + F\cdot (X_{j, r_2}^{G}-X_{j, r_3}^{G})$$

where $i$, $r_1$, $r_2$, $r_3$ are references to vectors in $NP$ and none is equal to the other, $J$ is an index in vector $X$, and $F$ is a random number between $0$ and $1.2$.

Suppose $X_{r_1}^{G}$ is equal to $\{4, 1, 3, 2, 2, 0\}$ and  $X_{r_2}^{G}$ is equal to $\{2, 2, 3, 0, 4, 2\}$ and $X_{r_3}^{G}$ is equal to $\{1, 2, 3, 3, 0, 1\}$
Could anyone explain in detail the steps (through example if possible) on how to get the mutant vector $V_{j,i}^{G+1}$

There isn't a single way in which one can approach a discrete optimization problem using Differential Evolution (DE).

Widespread techniques listed under the Discrete Differential Evolution label aren't DE-specific.

You can allow variables to take values in a continuous range and use penalty functions to enforce integer values:

$$ \bar{f}(w) = f(w) - \sum_i{k_i \cdot (w_i - \operatorname{round}(w_i))^2} $$

$w$ is the vector of parameters (chromosome values), $f: \mathbb R^n \rightarrow \mathbb R$ the basic fitness function (here assuming "greater is better"), $k$ a problem-specific scaling vector, $\bar{f}(\cdot)$ the "penalized" fitness function.

In this way the DE algorithm (DE/rand/1) stays the same:

$$\begin{align}
X_{j,r2}^G - X_{j,r3}^G & = \{2,2,3,0,4,2\} - \{1,2,3,3,0,1\} = \{1,0,0,-3,4,1\} \\
F \cdot (X_{j,r2}^G - X_{j,r3}^G) & = 0.5 \cdot \{1,0,0,-3,4,1\} = \{0.5,0,0,-1.5,2,0.5\} \\
V_{j,i}^{G+1} & = \{4,1,3,2,2,0\} + \{0.5,0,0,-1.5,2,0.5\} = \{4.5,1,3,0.5,4,0.5\}
\end{align}
$$

The trial vector $U$ is obtained via crossover between the donor vector $V_{j,i}^{G+1}$ and a target vector $X$:

$$U_{j,i}^{G+1} = \operatorname{crossover}(V_{j,i}^{G+1}, X_{j,i}^{G})
$$

The target vector is compared with the trial vector and the best one is admitted to the next generation.

This is the recommended procedure with R DEOptim Package (via the optional fnMap parameter).

You can round all the real-valued parameters before evaluating the fitness function:

$$\bar{f}(w) = f(\operatorname{round}(w))$$

(round acts as a repair operator)

This is the technique used by Mathematica's functions NMinimize / NMaximize with the options Method → "DifferentialEvolution" and  Element[w,Integers]

There are also many variations of DE named something-Discrete-DE:

Binary Discrete Differential Evolution: the solution of a problem is presented as a binary string instead of a real-valued vector
Real Value based Discrete Differential Evolution introduces forward/backward transformations to map integer into real number
and viceversa
Exchange based Discrete Differential Evolution: here the crossover operator doesn't change but mutation, being the primary operator acting on
elements of vector in continuous space, is replaced.
...

So you should specify what form of Discrete DE you're interested in for a step by step example.

Meanwhile A Comparative Study of Discrete Differential Evolution on Binary
Constraint  Satisfaction Problems by Qingyun Yang (2008 IEEE Congress on Evolutionary Computation) is a good starting point with many references.


Conflict Detection Algorithm I have been trying to come up with a better algorithm that detects conflicts in the scenarios below.

Let's say we have 4 dancers. We pair them up and find out which ones can dance together. So, we have the dancer # combination and whether they can dance together or not.

(1,2) True
(1,3) True
(1,4) False
(2,3) True
(2,4) False
(3,4) False

At the end of the day, I want to know which group of dancers I can group together.

A group can only be formed when all of the dancers within the group can dance with each other AND no dancer outside the group can dance with any dancer in the group.

For example, group A can be formed with dancers {1,2,3} because they call can dance with each other (i.e. (1,2), (2,3), and (1,3) are True) AND no dancer outside the group can dance with them (i.e. 4 is outside the group and (1,4),(2,4),(3,4) are all false).

Now, if we change:

(2,4) -> True

grouping changes quite a bit. I can no longer group 1,2 and 3 together because even though (1,2), (1,3) and (2,3) are all True, there is a dancer (#4) that can dance with 2 (i.e. (2,4) is True).

Now, can we group 1 and 3? No. Even though (1,3) is True, there would be one dancer outside the group that CAN dance with either 1 or 3 (i.e. (2,3) and (1,2) are True).

I came up with an algorithm that simply uses some non-sophisticated logic, but I was wondering if one can frame this problem in terms of a CS or Math problem, and whether something similar has been formally solved already.

If it helps you visualize this, you can draw rectangles or circles where they overlap if they can dance together.

Your dancers are vertices of a graph, and there is an edge between two dancers if they are compatible.  A set of dancers is a component if there's what you might call a "chain of compatibility" between every pair of them: that is, every pair of dancers is either compatible or you can come up with a sequence such as "Alice is compatible with Bob, Bob is compatible with Charlotte and Charlotte is compatible with Daniel" to get between them.
A group of dancers who are all compatible with each other are a clique.

What you're looking for is a component that is also a clique. These are easy to find because you can use a greedy strategy.  Suppose we want to know if a particular dancer (say, Alice) is in one of these groups.  We grow a set of dancers as follows.  Initially, the set is just Alice.  Then, we keep adding dancers to the set if they're compatible with anybody inside the set. When we can't add anyone, we've found the component. So now, we just need to check that the component is a clique: that is, everybody within the component is compatible with everybody else.

You can do this more efficiently by checking for being a clique as you add new dancers. Again, start with just Alice.  Then define a set of newcomers to be all people who are compatible with somebody in the set we've built so far.  If any of those people are incompatible with each other or with somebody who's already in the set, Alice isn't part of a group; otherwise, add all the newcomers to the set and select the next set of newcomers.


Shouldn't complexity theory consider the time taken for different operations? I have read the answer found here which considers the size of integers when doing comparisons and how that affects on the basic cost of comparison.

I am trying to understand why each basic operation takes $O(1)$ time.
For example branches in general are considered to run in $O(1)$ time when they usually don't.

In computer architecture branches are considered the most time-consuming and problematic part of the code and this is one of the reasons why a loop is unrolled by the compiler in order to reduce the amount of branches the processor needs to execute.

For example a simple branch (let's say if a>b) needs to do at least four things

Get a from memory (whether it is cache or RAM or on disk does not
matter; cache misses and hits are a different field of study).
Get b from memory
Evaluate the two and select the proper answer
Search in instruction memory a new value for the Program Counter
     depending on the result of the evaluation.

Now get the variables from RAM is something done everywhere. So let's not count that.
But since all modern processors load more than just one instruction from instruction memory (let's say for our case 100) so as to reduce instruction memory accesses and a branch usually leads to a different place in the instructions list (let's say if a>b call a method that swaps them), that would mean that branches take a lot more time than any other basic function.

Also in all modern processors multiplications and divisions take significantly much more time than additions and subtractions. Which is the reason why when multiplying or diving by numbers that are powers of two we should use logical bit shifting.

I know that in CS Theory and evaluating an algorithm we do not care. But in practice when implementing an algorithm the operations we use really effect the efficiency and complexity of our code.

So let's say we have three algorithms

$n$ additions
$n$ multiplications
$n$ branches

In Theory all three of these compute in time $n$ but in practice, 1 is faster than 2, which is faster than 3.

All complexity theory is relative to some model of computation. Typically, we consider models of computation where all basic operations take unit time because that's usually precise enough and, frankly, it's already difficult enough to do that kind of analysis.

Typically, running time analyses are only quoted asymptotically anyway.  As long as there's a constant bound on the number of clock cycles required for any operation, saying that an algorithm takes $O(f(n))$ operations is exactly the same thing as saying that it takes $O(f(n))$ clock cycles: the difference is just in the constant hidden in the $O()$ notation.

Having said that, models of computation do vary in what operations they consider as being unit-cost. For example, ordinary Turing machines count moving the head one step as unit-cost; random access Turing machines can move the head farther at unit cost.  People who study the complexity of matrix multiplication are often interested in the number of times you need to multiply matrix elements, rather than the total number of arithmetic operations, precisely because of your observation that multiplies are significantly more expensive than additions on a real CPU.

But, again, many things are swept under the carpet by asymptotic analysis. Suppose you did produce a model in which branches are much more expensive than other operations. Fine but, if you have a loop that needs to be iterated $n$ times, where $n$ is an input, your compiler can only unroll a constant number of iterations of the loop.  So, instead of doing $n$ branches, you do, say, $n/8$ branches: that's still $O(n)$.


High Level Assemblers vs Compilers? I'm reading the "Art of Assembly" 2nd Edition by Randall Hyde. In the book the author seems uses his own language called High Level Assembly (HLA). Coming from a C Background, I question how useful this is in learning (real x86/NASM for use on Linux) Assembly. But, looking it up there seems to be a term "High Level Assembler" (wikipedia) that gives some credibility to calling HLA "Assembly".

HLA provides ENUMs; bounds checking; multi-dimensional arrays; constant, static, and readonly variables; operators; a standard library; some error-catching; alignment and a lot of other stuff.

Where is the line drawn between an Assembler and a Compiler. From the book, it seems there is even some addressing modes not supported by HLA,

  Actually, the 80x86 does support addressing modes involving certain 16-bit registers, as mentioned earlier. However, HLA does not support these modes and they are not useful under 32-bit operating systems.

If it is a compiler, then does it "compile" the Assembly, or "assemble" the Assembly? Or is "High Level Assembly" just a procedural programming language that has little to do with Assembly?

The verb assemble and the noun Assembler is useful when it's important to point out that the program generates machine code with a 1:1 correspondence to the atomic instructions of the (Assembly) language.

But only a few simple directives (e.g. macros) need be added to the Assembler to reach something that gives more readable and compact code that can be, for all intents and purposes, considered high level.

If this was all that was added, you supply the actual macros, e.g. FUNC, CALL, STRUCT, etc. yourself, and can build your own language.

These macros are not the atomic Assembly Language instructions; nor are the directives built into the Assembler that lets you create them. Neither the macros you write, nor the directives are part of the agreed-upon Assembly syntax for the CPU.

For most intents and purposes, Compiler can be substituted for Assembler, and it's clear that you mean the program that generates an exe from text (or a tool). Perhaps some distinction could be useful when you mean language-specific such programs that can't parse Assembly, but there are ones that can do both.


If a language is context free, then its complement is decidable I am having a bit of trouble figuring this out. If L is context-free then we know it is decidable. The class of decidable languages is closed under complement thus, $L$ $\cap$ $L^{c}$, therefore $L^{c}$ is decidable.

Does this make any sense?

If $L$ is context free, it is decidable. Thus so is it's complement (to see if $\sigma \in L^c$, check if it is in $L$ and answer the opposite).

$L \cap L^c = \varnothing$, which is certainly decidable (just say no).

Your question is seriously confused...


2-SAT or 3-SAT or k-SAT in AC-0 This may be an elementary question, but I'm new to circuit complexity.  Does 2-SAT in CNF form belong to the complexity class AC$^0$?

It seems simple enough to construct an AC$^0$ circuit of depth 2 of polynomial size for 2-SAT. $~$Given $n$ variables (which means $2n$ literals), there can be at most $\frac{(2n)(2n-1)}{2} = n(2n-1)$ number of OR gates at Level one, because, given $2n$ literals, there can be at most $n(2n-1)$ clauses.  At Level 2, there is just one gate (an AND gate).

But we can also extend this to 3-SAT.  $~$The only difference is that at Level one, the maximum number of OR gates would now be ($2n$ choose $3$), which is $O(n^3)$, still polynomial in the number of variables.  Doesn't this mean that 3-SAT is also a member of AC$^0$?  Wouldn't this mean that 3-SAT is polynomially solvable?  What am I doing wrong?

2SAT is the following problem: given $\varphi$ (a Boolean formula in 2-CNF), is $\varphi$ satisfiable?

To show that 2SAT is in $\textsf{AC}^0$, you must show a constant-depth, polynomial-size circuit that can solve 2SAT.  In other words, you need to come up with an algorithm to solve 2SAT, and then show that the algorithm can be implemented by an $\textsf{AC}^0$ circuit.

In your question, you showed that $\varphi$ is in $\textsf{AC}^0$, but that's not what we need.  We need to know that the algorithm to solve 2SAT (i.e., to check whether $\varphi$ is satisfiable) is in $\textsf{AC}^0$, not that $\varphi$ is in $\textsf{AC}^0$.


Determine whether a point lies in a convex hull of points in O(logn) I've researched several algorithms for determining whether a point lies in a convex hull, but I can't seem to find any algorithm which can do the trick in O(log n) time, nor can I come up with one myself. Let a[] be an array containing the vertices of the convex hull, can I preprocess this array in anyway, to make it possible to check if a new point lies inside the convex hull in O(log n) time?

This is a classic problem in computational geometry, called Polygon Inclusion Problem. Further, you are considering its special case --- Convex Inclusion.

In chapter 4 of this thesis by Michael lail Shamos 1978, you will find that:

Generally,

  Theorem 4.2 (Page 92): Whether a point is interior to a simple $n$-gon can be determined in $O(n)$ time, without preprocessing.

and for convex polygon,

  Theorem 4.3 (Page 95): The Inclusion question for a convex $n$-gon can be answered in
  $O(\log n)$ time and $O(n)$ space, given $O(n)$ preprocessing time.

The proofs of these two theorems contain the algorithms you are looking for.


Superset of another language and recognizability of turing machines $L_1$ = $\{\langle M \rangle \mid M$ is a turing machine and $M$ halts on some string$\}$

$L_2$ = $\{\langle M \rangle \mid M$ is a turing machine and $M$ halts on all strings $\}$

a) Is $L_2$ a superset of $L_1$ ?

b) Is $L_2$ not co-recognizable and not recognizable ?

(without formally proving)

my attempt

$a)$ $L_2$ is a superset of $L_1$ since all strings are in $L_2$ whereas $L_1$ is some string

$(b)$ $L_2$ is not recognizable because, out of the infinite enumerations of strings, a single one could not halt disproving it from being recognizable.

For not co-recognizable: It can be written like this

$\bar{L_2} = \{ \langle M \rangle \mid M$ is a turing machine and $M$ loops on some string $\}$.

It's not possible to make a recognizer for loops so its instantly not co-recognizable. This is because looping means it never stops so to come up with a recognizer for anything to prove it loops is impossible since we are working with infinite combinations.

Not sure about it being a superset or not and my explanation for co-recognizable

If a machine halts on all strings then it halts on some string. Therefore $L_2 \subseteq L_1$.

If a machine halts on some string but not on all strings then it is in $L_1 \setminus L_2$. Since there are such machines, $L_1 \subsetneq L_2$.

The language $L_2$, usual known as TOT, is well known to be $\Pi_2$-complete. In particular, it is neither r.e. nor co-r.e. This can also be proved directly by reducing both the halting problem and its negation to $L_2$:

Given a Turing machine $M$ and an input $x$, construct a Turing machine $M'$ which erases its input and then runs $M$ on input $x$. Then $M$ halts on $x$ iff $M' \in L_2$.
Given a Turing machine $M$ and an input $x$, construct a Turing machine $M'$ which on input $n$ simulates $M$ on $x$ for $n$ steps, and loops if $M$ halted within $n$ steps. Then $M$ doesn't halt on $x$ iff $M' \in L_2$.


Why is it that a lambda function requiring multiple input also requires multiple functions? So I recently discovered lambda calculus and for the most part I understand it. However, one specific part of it that I cannot understand is this:

Let's say we define a very simple function

$$ I := \lambda a.a$$

This is simple to understand, nothing confusing. However, if you add another input I will scratch my head furiously:

$$A := \lambda a.\lambda b.a+b$$

This is confusing to me for at least 2 reasons:

Why is it that I cannot define a function with multiple parameters like so:

$$A := \lambda a,b. a+b$$
How does the second function returned have access to the first parameter if they can only hold one parameter? Is there a prospective for scope? If so, how does it work?

One view is that there are no functions of multiple parameters. A function which takes "two parameters" is a function taking a single ordered pair. In mathematics, a function $f : A \to B$ has one domain $A$ and codomain $B$. While it is possible to speak of functions with multiple domains, it is more customary to think of a multi-variate function $g$ as an ordinary function whose domain is a cartesian product, $g : A \times B \to C$.

So, if you would like to have functions taking two parameters in $\lambda$-calculus, you should not be changing how $\lambda$-abstraction works, but you should rather extend the calculus with ordered pairs (and people do that).

But we do not have to extend the calculus with ordered pairs, because every function of two arguments $A \times B \to C$ can be converted to a function of a single argument $A$ returning a function $B \to C$. This may take some getting used to, but it works perfectly. That is, there is a bijection between functions $A \times B \to C$ and functions $A \to (B \to C)$, where the latter expression is read as "functions taking an argument from $A$ and returning a function from $B$ to $C$". This is known as currying.

The expression $\lambda a . \lambda b . a + b$ should be read as a function taking an argument $a$ and returning the function $\lambda b . a + b$. It is thus an example of a multi-variate function that has been curried to take one argument at a time.


what is the complexity of recurrence relation? what is the complexity of below relation

$ T(n) = 2*T(\sqrt n) + \log n$

and $T(2) = 1$

Is it $\Theta (\log n * \log \log n)$ ?

Yes, the answer is $\lg n \cdot \lg \lg n$:

Reason this out by expanding the recurrence and looking for a pattern:

\begin{align*}
T(n) &= 2T(\sqrt{n}) + \lg n \\
     &= 2( 2T( \sqrt[4]{n} ) + \log(\sqrt{n}) ) + \lg n \\
     &= 2\left( 2T(\sqrt[4]{n}) + \frac{1}{2} \lg n \right) + \lg n  \\
     &= 4T( \sqrt[4]{n} ) + 2 \lg n \\
     &= 4( 2T( \sqrt[8]{n} ) + \lg\sqrt[8]{n} ) + 2 \lg n \\
     &= 8T( \sqrt[8]{n} ) + 3 \lg n \\
\end{align*}
So as we continue expanding this and taking the square root of $n$, we will eventually bottom out where $n < 2$.  To figure out how many times we can take the square root of $n$, consider $n = 2^{\lg n}$, and on each recursive call, $n$ will have its square root taken.  Ending when $n < 2$ gives us:
\begin{align*}
2^{\frac{\lg n}{2^k}} &= 2 \\
\frac{\lg n}{2^k} &= 1 \\
\lg n &= 2^k \\
k &= \lg \lg n
\end{align*}

Giving a solution of $\lg n \lg \lg n$.

Alternatively, this can be solved via variable substitution and the Master Theorem.  Substituting $m = \lg n$:
\begin{align*}
T(2^m) &= 2T(2^{m/2}) + m \\
S(m) &= 2S(m/2) + m
\end{align*}
At this point the Master Theorem applies, with $a=2$, $b=2$, and $f(m) = m$.  Since
$m^{\log_b a} = m^{\lg 2} = m$, resulting in $f(m) = m = \Theta(m^{\log_b a})$.  Therefore case 2 of the Master Theorem applies, and the solution is $m \lg m$.  Substituting $m = \lg n$ gives us $T(n) = \lg n \lg \lg n$.

Edit: fixed a typo (needed to write this to exceed the minimum number of characters).


Is there a name and efficient algorithm for this Tree Traversal method? Consider a tree structured task list where intermediate nodes define sub-groupings of tasks but are not tasks themselves, and the leaves represent the actual tasks.

I want to traverse this type of tree giving equal opportunity/priority/time(?) for each group with respect to its parent.

For example, if the root have 3 sub-trees (node or leaf), first I want to complete 1 task from the first sub-tree, then complete another task from the second sub-tree, and finally complete a task from the third sub-tree. When all sub-trees processed, the algorithm would start from the beginning this time selecting the second task from the sub-trees. This way, all the sub-trees would have equal processing time in terms of tasks in a given time frame. The same requirement is also present in each sub-trees themselves recursively of course.

This might require keeping tabs of traversed child paths for each loop on each node. ... Maybe a recursive traversal could automatically handle this?

Consider the following tree structure as an example:

So the traversal I am thinking about would be as following for this example.

Level 0 has no task, 3 sub-trees, go into first sub-tree to find a task
We follow as in depth-first to arrive at task A and select it (complete it)
Now the first sub-tree in level 1 has a task completed, while its siblings are at 0, so we select from the second sub-tree
Level 1 second sub-tree has only one task, D, so we select it
Similarly we go in to the third sub-tree and find the task F and select it
Now we return to level 1 and try to find our second task from the first sub-tree
IMPORTANT: We have already selected a task from level 1's first sub-tree, so we go into its second sub-tree and select task E
Now level 1 first sub-tree has two tasks completed, and the second sub-tree has no other tasks, so we skip it and go into third sub-stree and select G
Similary, we loop again and select B from left side, and I from right side (we don't select H because its sibling already selected)

Then we select C from the left side completing this side and K from the right side (J is not selected similarly)
Only the right is left, so we select first H and finally the J, completing our traversal.

Traversal of leaves: (A->D->F)->(E->G)->(B->I)->(C->K)->(H)->(J)

[Adding this clarifying paragraph from the comments:]

Essentially the algorithm prevents any sub-grouping getting ahead (more than 1 tasks) of its unfinished siblings. It might be considered, in part, as a hierarchical round-robin scheduling giving equal time in terms of task operations.

So my questions are:

Is there a name for this kind of tree traversal. If not, what would you
call it?
How would you approach traversing this tree in an efficient way and what would be the complexity?

Big thanks!

EDIT: Changed "opportunity" to "opportunity/priority/time(?)" in text and removed it from the title.

UPDATE: I have used the final algorithm from Apass.Jack and compared some different trees on it. Calculating the complexity proved difficult, though it definitely looks lower than $O(n\log n)$,.

JS Code can be found as a:

JS Online Engine: Javascript (Node ES6+) Implementation
Gist Code: GitHub Gist Source

Here are some execution results for different depths (D) and leaf counts (L):

          D3L10   | D3L1000 | D6L10 | D6L1000
          ===================================
Push      |  35   |   3350  |  50   |  4698 |
Unshift   |  14   |   1150  |  17   |  1549 |
Splice    |  35   |   3350  |  50   |  4698 |
Access    |  35   |   3350  |  50   |  4698 |
Traverse()|  16   |   1351  |  20   |  1808 |
Zip()     |   5   |    151  |   8   |   550 |
          -----------------------------------

NOTE: My question traversed siblings in left to right order but as Apass.Jack has stated below, a randomized recursive round-robin (RRRR) algorithm would indeed be more useful in task-management situation and current algorithm could be modified to do that easily.

Here is a simple algorithm using a stable priority queue, where elements of equal priority will exit the queue in the order they are inserted into the queue.

Let the priority of each node be its level, a.k.a. its depth from the root. Lower level means higher priority.
Initialize $Q$ to be a stable priority queue of nodes containing the root.
while $Q$ is not empty:

Take a node $q$ from $Q$.
while $q$ is not a leaf:

Add $q$'s next right sibling, if any, to $Q$.
Replace $q$ by its leftmost child.

output $q$.

This traversal goes level by level, outputting the leftmost leaf of each subtree and keeping track of what to do next in each subtree in the stable priority queue. Note that the traversal uses each edge only once.

Here is a sample run of the algorithm.

1
├──2
│  ├──3
│  │  ├──A
│  │  ├──B
│  │  └──6
│  │     └──C
│  └──8
│     └──E
├──D
└──11
   ├──F
   └──13
      ├──14
      │  ├──G
      │  └──H
      ├──17
      │  └──18
      │     ├──I
      │     └──J
      └──K

Queue is not empty: [1]
1 has no more siblings.

Descending to the first child of 1: node 2
Added 2's sibling D to the queue.
The queue is now: [D]

Descending to the first child of 2: node 3
Added 3's sibling 8 to the queue.
The queue is now: [D, 8]

Descending to the first child of 3: node A
Added A's sibling B to the queue.
The queue is now: [D, 8, B]
Output leaf: A

Queue is not empty: [D, 8, B]
Added D's sibling 11 to the queue.
The queue is now: [11, 8, B]
Output leaf: D

Queue is not empty: [11, 8, B]
11 has no more siblings.

Descending to the first child of 11: node F
Added F's sibling 13 to the queue.
The queue is now: [8, 13, B]
Output leaf: F

Queue is not empty: [8, 13, B]
8 has no more siblings.

Descending to the first child of 8: node E
E has no more siblings.
Output leaf: E

Queue is not empty: [13, B]
13 has no more siblings.

Descending to the first child of 13: node 14
Added 14's sibling 17 to the queue.
The queue is now: [B, 17]

Descending to the first child of 14: node G
Added G's sibling H to the queue.
The queue is now: [B, 17, H]
Output leaf: G

Queue is not empty: [B, 17, H]
Added B's sibling 6 to the queue.
The queue is now: [17, 6, H]
Output leaf: B

Queue is not empty: [17, 6, H]
Added 17's sibling K to the queue.
The queue is now: [6, K, H]

Descending to the first child of 17: node 18
18 has no more siblings.

Descending to the first child of 18: node I
Added I's sibling J to the queue.
The queue is now: [6, K, H, J]
Output leaf: I

Queue is not empty: [6, K, H, J]
6 has no more siblings.

Descending to the first child of 6: node C
C has no more siblings.
Output leaf: C

Queue is not empty: [K, H, J]
K has no more siblings.
Output leaf: K

Queue is not empty: [H, J]
H has no more siblings.
Output leaf: H

Queue is not empty: [J]
J has no more siblings.
Output leaf: J

You can play with a JavaScript implementation by Apass.Jack of this algorithm

The only slowdown for this algorithm is the stable priority queue. Using generic stable priority queue will give you $\mathcal{O}(n \log n)$ total runtime, where $n$ is the size of the tree.

However, it is possible to cut the running time down to $\mathcal{O}(n)$. Note that once we take a node with priority $p$ from the top of the queue, we will then possibly add a node with priority $p$, then descend to the child, then possibly add a node with priority $p+1$ and so on. This gives an idea to implement the priority queue as a linked list:

Each element of the list is a queue of nodes with the same priority.
Top priority is at the head of the list. If we pop last node from the top queue, the head of the list is removed.
When we descend to a child, the (candidate) priority is incremented, so we should move through the list, if necessary.
When we push new node, we either insert new queue into the list, or push the element to existing one.

Here's the states of such a priority queue from the run above (asterisk means current queue for insertion):

Initial:
└─[1] *

After popping node 1 and descending to node 2:
└─[D] *

After descending to node 3:
├─[D]
└─[8] *

After descending to node A:
├─[D]
├─[8]
└─[B] *

Taking D from the top:
├─[8] *
└─[B]

And pushing 11 before [8] because of greater priority.
├─[11] *
├─[8]
└─[B]

Taking 11 from the top and adding 13, which has the same priority as 8:
├─[8, 13] *
└─[B]

Taking 8 from the top:
├─[13] *
└─[B]

Taking 13 from the top:
└─[B] *

Pushing 17 with the same as B priority:
└─[B, 17] *

Added H to after [B, 17] because we descended:
├─[B, 17]
└─[H] *

Took B from the top:
├─[17] *
└─[H]

Added 6:
├─[17, 6] *
└─[H]

Took 17, added K:
├─[6, K] *
└─[H]

Descended to the child:
├─[6, K]
└─[H] *

Added J to a new queue, because we descended:
├─[6, K]
├─[H]
└─[J] *

Exhausting the rest of the queue:
├─[K] *
├─[H]
└─[J]

├─[H] *
└─[J]

└─[J] *


For a computational problem, can the set of instances be finite? A computational problem consists of a set of instances. In most cases the set of instances is infinite. Like the set of all graphs, e.g.:

  Given a graph $G$, is there a Hamiltonian circuit in $G$?

Can the set of instances be finite and a problem still be non-trivial?

A finite problem can be decided in O(1) time: we can simply compare the input to a finite (bounded) list of known cases, and emit the output consequently.

Indeed, for that we do not need a Turing powerful system: a finite-state automaton suffices.

So, the problem is indeed trivial.

Co-finite (finite complement) problems are similarly trivial.


Develop a winning strategy for a game Okay so I've been going crazy about this problem I was given. It is as follows:

Given a pile of N matches, 2 people take turns removing matches from the pile. When it is your turn you are allowed remove 1, 5 or 6 matches. If it is your turn and you are unable to make a move then the game is over and you have lost.

The idea is to develop a strategy where you can always win. Note that you can always decides who goes first.

Not sure if I'm even on the right track but currently I can guarantee that if it is my go and  then I remove 1, 5 or 6 matches, leaving my opponent with 22 matches I will win. But unsure how to guarantee that this situation will arise.

Any help would be appreciated even if it's just a reassurance that it is possible because I've spent hours within the last 2 days and still can't come up with a winning strategy that works all the time.

The nature of a position in this game depends only on $n \bmod{11}$. If $n \equiv 0,2,4 \pmod{11}$ then $n$ is a losing position, otherwise it is a winning position. You can prove this by induction by showing that (1) every move from a losing position leads to a winning position, (2) at every winning position one can move to a losing position. This can be checked by exhaustive case analysis:

$0 \bmod{11}$: moves lead to $5,6,10 \bmod{11}$, all winning positions.
$1 \bmod{11}$: removing 1 match leads to $0 \bmod{11}$, a losing position.
$2 \bmod{11}$: moves lead to $1,7,8 \bmod{11}$, all winning positions.
$3 \bmod{11}$: removing 1 match leads to $2 \bmod{11}$, a losing position.
$4 \bmod{11}$: moves lead to $3,9,10 \bmod{11}$, all winning positions.
$5 \bmod{11}$: removing 1 match leads to $4 \bmod{11}$, a losing position.
$6 \bmod{11}$: removing 6 matches leads to $0 \bmod{11}$, a losing position.
$7 \bmod{11}$: removing 5 match leads to $2 \bmod{11}$, a losing position.
$8 \bmod{11}$: removing 6 match leads to $2 \bmod{11}$, a losing position.
$9 \bmod{11}$: removing 5 match leads to $4 \bmod{11}$, a losing position.
$10 \bmod{11}$: removing 6 match leads to $4 \bmod{11}$, a losing position.

For completeness, the $g$ values are $0,1,0,1,0,1,2,3,2,3,2$ (and then they repeat).

Your strategy is as follows: if $n$ is a winning position you start, otherwise you go second. Then you follow the strategy outlined above, which is guaranteed to win.

This strategy can be computed mechanically using the Sprague–Grundy function $g$.


Minimize same placed elements in a list of permutations (Heap) I'm trying to optimize the permutations generated from a set of n elements.

Here is the pitch:
I have a set of 6 elements $\{1,2,3,4,5,6\}$ and I want to create 10 permutations. I could use Heap algorithm to keep 10 among 6! possible combinations.

But I'd like to add specific constraint : I want to select the 10 permutations that minimize the number of elements at the same index.
(avoid having 10 permutations with the 3 at the same index for example)

For instance, I simply create the first 6 permutations by rotating my initial set from 1 to 6 to the right to obtain the following combinations: $\{1,2,3,4,5,6\}$, $\{2,3,4,5,6,1\}$, $\{3,4,5,6,1,2\}$, $\{4,5,6,1,2,3\}$, $\{5,6,1,2,3,4\}$, $\{6,1,2,3,4,5\}$

Now, I would like to generate additional combinations following my constraint, do you have any clue or advice ?

My initial guess, based on some cursory knowledge about Permutohedrons:

Given your set $S = {1,2,3,...}$, generate all permutations $P(S)$ and define a multigraph $G(V,E)$ where $V = P(S)$ (each permutation is a vertex) and the edge-set $E$ consists of pairs of permutations that share an element at a common location (e.g. $123456$ and $123465$ are connected by $4$ edges).

Your problem is then picking a subset of $V' \subset V$ s.t. the subgraph induced by $V'$ has as few edges as possible.

Considerations:

You can use a weighted graph instead of a multigraph. Replace $n$ edges with 1 edge with weight $n$. The optimization objective would then be total edge weight of the induced subgraph.
Based on the many symmetries, I would guess that it should be possible to achieve a very good (maybe even optimal) solution with a greedy algorithm.

Possible greedy algorithm:

Construct graph, initialize $V' = \emptyset$
Until $|V'| = n$:

For each $v \in V \setminus V'$: $v^+ :=$ total weight of edges between $v$ and $w\in V'$
If $v^+ = 0$, add $v$ to $V'$. Else, add vertex with lowest $v^+$.


Calculate Pagerank of three nodes Soon I will have an exam where I will be asked to calculate pagerank. So far, I have been thought to use power iteration. However, this can be a very expensive operation to do during an exam, especially when most of the times, the number of nodes is just 3.

Is there any better algorithm to calculate the pagerank of only 3 websites involved?

There is a formula for the PageRank which involves inverting an $n\times n$ matrix. When $n = 3$ this is not too hard. For inverting the matrix, use the formula given on Wikipedia, which is just a special case of the general formula involving the adjugate matrix.

That said, I see absolutely no reason why you would ever have to calculate PageRank by hand. That's what we have computers for. If you are given such an exercise in an exam, the matrix will probably have some very simple structure which will make it easier to handle by hand.


Why is IDA$^*$ faster than A$^*$? Why does IDA$^*$ visit more nodes than A$^*$? I used IDA$^*$ for optimally solving the 8-puzzle and my friends used A$^*$ for it too (with same manhattan distance heuristic).

I calculated the average running time and number of nodes of my algorithm for 20 examples and my friend's algorithm. The time average for my algorithm was much faster than my friend's algorithm, but my average number of nodes visited is a lot more than my friend's.

I know IDA$^*$ visits each node more than once but why is it faster than A$^*$?

Since you already implemented IDA$^*$ you certainly understand why it expands more nodes than A$^*$, i.e., it starts from the start state with a new depth-first traversal in each iteration. Note first that, the overall number of nodes visited by IDA$^*$, while necessarily larger than A$^*$ is not that much larger. The reason is that the number of nodes at each depth progresses according to a geometric series with factor $b$, the branching factor. As a result, the number of nodes at depth $d$, $b^d$, is much larger than the sum of all nodes expanded at the previous iterations, i.e., $b^d>\sum_{i=0}^{d-1}b^i$. From this difference, it turns out that IDA$^*$ requires $\frac{b}{b-1}$ additional expansions which is asymptotically optimal as the limit for large $b$ is 1. Concluding, for any algorithm visiting all nodes at depth $d$ is much more difficult than visiting all nodes at the preceding depths.

In case that you want to delve more into this issue, I strongly recommend you reading the original paper: Korf, Richard E. Depth-First iterative-deepening: An optimal admissible tree search. Artificial Intelligence (27), 97-109, 1985. See in particular Theorem 4.2:

  Depth-first iterative-deepening is asymptotically optimal among
  brute-force tree searches in terms of time, space, and length of
  solution.

Of course, it delivers optimal solutions so that it is admissible and hence, asymptotically optimal. It only practices depth-first traversals and therefore, it is asymptotically optimal in terms of space (requiring with a good implementation only $O(d)$).

As for the time, I already outlined the main theoretical reason but let me know highlight three main reasons why it is so fast in practice:

First of all, for almost all purposes, the overall running time of any algorithm is dominated by the time it takes to expand nodes (other operations are rather simple and atomic). It is indeed when expanding nodes that IDA$^*$ can be extraordinarily fast because:

1.1. IDA$^*$ is implemented recursively so that all you need is to take the state given as an argument and to generate a child at a time (for your specific case this simply means swapping the blank with an adjacent tile, that's only one statement!). However, for A$^*$ the expansion operation requires: first, popping a state from the queue, then generating all its children (i.e., moving the blank tile in all possible directions).

1.2. While the preceding operation makes some difference, the really important one is that A$^*$ requires sorting nodes in OPEN. Even if you do this with a 1-bucket (which would take $O(1)$), note that IDA$^*$ does not require to sort nodes at all, so that while A$^*$ takes time which is linear in the number of nodes expanded, IDA$^*$ takes none at all.
Thirdly, one of the contributions of best-first search algorithms (such as A$^*$) is that they avoid re-expanding nodes by using a CLOSED list (which in spite of its name is usually implemented as a set!!). IDA$^*$ does not have duplicate-detection mechanisms and hence, again, A$^*$ performs an extra operation which is not performed at all by IDA$^*$. If you want to know more about duplicate-detection in IDA$^*$ see: Reinefeld, A.; Marsland, T. Enhanced iterative-deepening search. IEEE Transactions on Pattern Analysis and Machine Intelligence (16) 7, 701-710, 1994.

The last point is truly relevant. In the case of the sliding-tile puzzle there are not many transpositions indeed and the shortest cycle consists of 12 moves, so that the number of re-expansions is not that large. Putting all these together, IDA$^*$ is a killer machine for all sizes of the sliding-tile puzzle.

However,, in spite of all its advantages, it might not be of practical interest in those applications that have a large number of transpositions. There have been various attempts to overcome this difficulty with limited success, see for example:

Dow, P. Alex; Korf, Richard E. Duplicate avoidance in depth-first search with applications to treewidth. International Joint Conference on Artificial Intelligence, 480-485, 2009.

Hope this helps,


Robot swarm, Maximum area coverage I have a swarm ofN robots to place on a plane area. Each robot would control a sub part of the area (navigating in it). What algorithm could I use to deploy my robots so that they all control a comparable part of the area.

I was looking at Voronoi diagrams but I cannot find how to determine the location of the points.

Sorry if this is not very clear, I am not even sure what I am looking for.

I assume by "comparable part of the area" you mean that they should all scan a region of equal area. Additionally, knowing what kind of plane area you have would be helpful, is it convex, is it concave, is it just a regular polygon? If you know this then there are easier ways to do it.
So assuming you want for the worst case, a concave polygon, the best solution that I know of is this.
This page has a detailed explanation of the algorithm and there's even some comments with implementations.


Markov Model to compute the probaility on the $n^{th}$ day This is a question about Markov Models. Let's say we have the following situation

Let's say that we want to find the probability that $2$ rainy days follow a nice day. You'd simply have $0.25 \cdot 0.5=0.125=12.5\%$. However let's take it up a notch. What's the probability that on the $7^{th}$ day it's snowy? Or in general how would you find the probability that on the $n^{th}$ day it's a certain weather?

I think that you could take one possibility of a sequence of events, such that on the $7^{th}$ day it snows, such as nice, rain, snow, nice, rain, snow and snow which has a probability of $0.1953\%$ and then add all such probabilities but I'm not a 100% sure.

Yes, you just add up the probabilities of all the possibilities. However, there's a conceptually clearer way of doing it that's less error-prone.

The transition matrix tells you the probability of moving from one state to another in one step.  The probability that it rains the day after tomorrow given that it's nice today is, as you've seen, given by
$$\Pr(N\to N)\,\Pr(N\to R) + \Pr(N\to R)\,\Pr(R\to R) + \Pr(N\to S)\,\Pr(S\to R)\,.$$
If you look at this closely, you'll see that it's exactly the (Nice, Rain) entry of the square of the transition matrix.  Similarly, the $n$th power of the transition matrix tells you the probability of moving between two states in $n$ steps.

Powers of the transition matrix can be computed efficiently with repeated squaring – for example $M^7 = (M^2)^2\times M^2\times M$ and there's the bonus that you get all the $n$-step probabilities instead of just one.


Why can there be no reductions from NP-complete problems to P problems under P ≠ NP Under the assumption that $P \ne NP$, why is it impossible to reduce a problem that is known to be NP-complete to a problem that is known to be of polynomial time complexity? What kind of fundamental theorems would this contradict if it was possible?

It would contradict the assumption that P$\,\neq\,$NP. You could solve the NP-complete problem in polynomial time by reducing it to a problem in P and solving that.


How to find the class of a problem? I've learnt about complexity classes but my knowledge doesn't seem to help much when I am given a problem and need to decide it's complexity.

Here is the problem at hand:
A set of weights with the same dimensions but with different densities have to be ordered on a plank (on a straight line). The length of the plank is not enough to put everything in one line so you'd have to stack weights on top of each other. There are $n$ weights and there's space only for $m$, $m<n$ weights on the plank. The weight of each object is given.

The target is to stack weights such that the weights are spread across the plank as smoothly as possible. The following figure shows a sample (possible) solution for n=11 weights each having weight w1 to w11 and m=5.

The smoothness of the weight distribution is calculated by finding the average of all weights and summing up the deviation from this value at each spot.

Now definitely this is a combinatorial problem. And it is definitely a 'yes' 'no' answerable problem.

It seems to me that it's not in NP. Because given a solution, there is no way of saying in polynomial time that it's the correct answer. Is this right?

If so, does that mean it is in NP hard?

How can I really find which class it belongs to.

I'd appreciate it if anybody could help me with this problem.

You have described an optimization problem, namely, find the arrangement that minimizes the average deviation from the mean. The decision version of this problem is, given an input to your problem and a value $T$, whether there exists an arrangement whose average deviation is at most $T$. This problem is in NP.

Whether it is NP-hard or not is for you to ponder. Combinatorial problems in NP tend to be either NP-hard or in P, so you should simultaneously try to prove that your problem is NP-hard via reduction from a known NP-hard problem, or to find an efficient algorithm for your problem.


Understanding Master Method's Case 2 Whats the intuition behind multiplying the factor $\log n$

  Master Method Case 2 (CLRS Section 4.5)

  If $f(n) = \theta(n^{\log_b a})$, then $T(n)= \theta(n^{\log_b a} \log n)$

In generalized form sometime it can be written as

  If $f(n) = \theta(n^{\log_b a} log^k n)$ with $k = 0$, then $T(n) = \theta(n^{\log_b a} \log^{k+1} n)$

Suppose that $T(n) = aT(n/b) + n^{\log_b a}$ and $T(1) = 1$. Now consider some $n$ which is a power of $b$, say $n = b^k$. The formula gives
$$
\begin{align*}
T(n) &= aT(n/b) + n^{\log_b a} \\ &=
a^2T(n/b^2) + a(n/b)^{\log_b a} + n^{\log_b a} \\ &=
a^3T(n/b^3) + a^2(n/b^2)^{\log_b a} + a(n/b)^{\log_b a} + n^{\log_b a} \\ &=
\cdots \\ &=
a^kT(n/b^k) + a^{k-1}(n/b^{k-1})^{\log_b a} + \cdots + n^{\log_b a} \\ &=
a^k + a^{k-1}(n/b^{k-1})^{\log_b a} + \cdots + n^{\log_b a} \\ &=
a^k(n/b^k)^{\log_b a} + a^{k-1}(n/b^{k-1})^{\log_b a} + \cdots + n^{\log_b a}.
\end{align*}
$$
There are $k+1 = \log_b n + 1$ terms in the final formula. Miraculously, all of them are equal to $n^{\log_b a}$! (Work that out on your own.)