why do CPU architectures use a flags register (advantages?) Some CPUs have a flags register (ARM,x86,...), others don't (MIPS,...). What's the advantage of having a CMP instruction to update the flags register followed by a branch instruction instead of using a zero register and conditional branches to check for sign, overflow etc?

In modern micro-architectures with register renaming the implementation cost for flags or not flags is pretty similar.  The main difference I can think of is that some flags indicate the characteristics of a value (Is the value negative?  Is the value zero?  Does the value have even or odd parity?), while some represent an event that occurred during a previous operation (did the add instruction have a carry out or an overflow?)  This led to a less-than-ideal situation on the MIPS when you wanted to simulate 64-bit addition on the 32-bit architecture (or 128-bit addition on the 64-bit architecture.)  On most architectures with a carry flag there is a special add-with-carry instruction, that includes the carry flag from the previous add instruction.  This makes simulating multi-precision arithmetic relatively inexpensive on many architectures with flags registers.

On the flip side, testing an N-bit register for zero or not-zero is actually surprisingly expensive.  To test an N-bit register for zero you need to perform an N-bit NOR operation, which requires $O(\log N)$ levels of logic to calculate.  On architectures with flags registers the extra logic for the zero/not-zero calculation at the end of the ALU stage can cause the clock to run slower (or force the ALU to have two cycle operations.)  For this reason, I think, some architectures, like SPARC had two versions of each arithmetic operation, one that set flags and one that didn't.

But MIPS doesn't save anything here.  They just moved the problem somewhere else.  On MIPS there is a branch-on-equal instruction.  This means that the branch instruction must actually have an ALU stage (including something like a bitwise xor operation followed by a nor to reduce down to the single equal/not-equal bit) before determining which way the branch goes.

The DEC Alpha architecture tried to split the difference by using a trick.  DEC Alpha had no flags registers, but also didn't have a branch-on-equal instruction.  Instead the branch instructions all look at the state of a single general purpose register.  There is branch-on-zero, branch-on-not-zero, branch-on-less-than-zero, etc.  The trick is that you can give every general purpose register an extra 65th bit that tells you whether the other 64 bits are all zero or not.  This makes it more like having a flags register: all the branch instructions look at a single bit (that is already calculated) to make their decision, but now you are back to figuring out how to calculate that extra zero indicator bit during a normal ALU cycle.  (And you still can't do multi-precision arithmetic just by looking at the carry flag from the previous operation.)


Double Hashing with Strings as key How would you choose the second hash function with for double hashing with string as key?
My first hash function is the scalar product of a random int array with the 16 bit number of each char. Is that a good first hash function? And what should I do for the second function now?
hanks in advance.

There are many hash functions for hashing a string; a web search should turn up a bunch.  You can use any one you like.  The fact that you are using double hashing doesn't impose any additional requirements on the hash function.  Yes, that would be a reasonable hash (and you could use two different int arrays for the two different hash functions); there are many other choices that would be reasonable as well.


What does this definition of a Primary key mean? My text book gives the following definition of a primary key in a relational database, which I don't entirely understand. Help would be greatly appreciated.

  Let $R$ be a relation. Then the primary key for $R$ is a subset of the
  set of attributes of $R$, say $K$, satisfying the following two properties:

  Uniqueness Property: No two distinct tuples of $R$ have the same value for $K$.
  Irreducibility Property: No proper subset of $K$ has the uniqueness property.

I'm getting lost by the Irreducibility property.

Note how $K$ can be a set of columns. Irreducibility means that you have to pick minimal sets of columns.

Nota bene: They should require $K \neq \emptyset$.

For instance, consider this relation.

A   B   C

1   4   4
2   4   6
3   6   6

Let us investigate all possible keys.

A -- unique and irreducible.
B -- not unique.
C -- not unique.
A,B -- reducible to A.
A,C -- reducible to A.
B,C -- unique and irreducible.
A,B,C -- reducible to A.

Hence, there are two choices for primare keys here: A and B,C.


How is $\emptyset^* = \{\epsilon\}$? I know that $\emptyset$ is a an empty language, i.e. language containing no string.

A law involving empty language is:

  $\emptyset L = L\emptyset = \emptyset$

It correctly states that we cannot concatenate non empty language $L$ with a language $\emptyset$ containing no string  (as their is no string to concatenate in $\emptyset$), it yields empty language.

Then how concatenating a language containing no string with itself any number of times can yield even empty string? That is, how following law exist:

  $\emptyset^* = \{\epsilon\}$

For any language $L$, by definition
$$ L^* = \bigcup_{i=0}^\infty L^i, $$
where a word in $L^i$ is the concatenation of $i$ words from $L$. In particular, $L^0 = \{ \epsilon \}$ since $\epsilon$ is the concatenation of zero words from $L$. It doesn't matter if $L$ is empty or not, since we are choosing zero words from $L$.


Finding $t$, $r$ and $w$ in Cache - Direct Mapping I had a question in my past System Architecture exam and I am not sure how to solve it.

Question was this:

  Consider a 16-bit addressable memory and a direct-mapped cache sized 64 bytes. MAR is 10 bits and a block in memory is 8 bytes sized. Find $t$, $r$ and $w$ (they are Tag, cache index, and block offset respectively.)

Can you show steps of solution of this and such questions? Should I divide cache size by 2 since it is 2 byte addressable? Thanks.

I think i found out the solution, may be helpful for others reading this.

The size of a block is 8 bytes. And the memory is adressed with 2 bytes. So each block contains 4 words (considering 1 adressible unit = 1 word).

4 = 2^2, Then $w$ = 2 bits

Since cache has a size of 64 bytes which is 2^6, than $r$ + $w$ must be 6.

$r$ + $w$ = 6, $w$ = 2 so $r$ = 6-2 = 4 bits

Lastly the MAR is 10 bits so the length of RA ($r$ + $w$ + $t$) must be 10.

$r$ + $w$ + $t$ = 10, $r$ + $w$ = 6, then $t$ = 10 - 6  = 4 bits .

So the RA distribution will be like:

+----------------------------------------+
| t = 4 |       r = 4      |    w = 2    |
+----------------------------------------+


What is a predicate transformer? I'm reading Programming - The derivation of algorithms, and I want to understand the purpose of a predicate transformer. This is the excerpt (p. 14-15):

A more precise way in which constructs may be introduced is as follows. For each construct $S$ one defines a predicate transformer, denoted $wp.S$, which is a function from predicates to predicates. For construct $S$ and predicate $Q$, $wp.S.Q$ is interpreted as the weakest predicate $P$ for which $\{P\}\,S\,\{Q\}$ holds. It is called the weakest precondition of $S$ with respect to $Q$. The relation between the expressions $\{P\}\,S\,\{Q\}$ and $wp.S.Q$ is given by
$$ \{P\}\,S\,\{Q\}$ \text{ is equivalent to } [P \implies wp.S.Q]$$

Explain me the concept predicate transformer. What is its purpose?

The predicate transformer is just a formalization of the idea that you can produce a precondition given a program and its postcondition.

For example, given a program sqrt with the postcondition that sqrt(x) = y and y*y = x, what are some valid preconditions?

x > 10
x > 20
x > 1

Some invalid preconditions would be

x < 0
x > -10

One predicate P1 is weaker than another predicate P2 if P2 => P1, but it is not true that P1 => P2. For example, x > 1 is weaker than x > 10 because x > 10 implies x > 1 as well, but x > 1 does not imply x > 10; x == 3 would be a counterexample.

Given all possible preconditions for our square-root program, one must be the weakest of them all; we denote that with the function wp.S.Q (which you could also write in the more familiar notation wp(S, Q)). In this case, wp.S.Q = {x >=0 }. You can prove that if x satisfies any precondition P, then it must satisfy x >= 0, and that if it does not satisfy x >= 0, it cannot satisfy any other precondition P.

The idea of a weakest precondition is useful because it allows a program to work with as many values as possible. Using a precondition of x >= 20 isn't useful because it doesn't allow us to compute the square root of 4.

Note that just because wp.S.Q is defined, that doesn't mean we have to provide an algorithm to actually compute its value. Doing so would provide a constructive proof of its existence, but non-constructive proofs could be found as well.


Category theory structures to describe topics and queues What are the category theory structures describing queues and topics? By queues and topics I mean the ones described in systems like Apache Kafka, AcriveMQ or Java Messaging Service.

Where I can find material about that?

A data structure Queue is very close to the concept of a List, however a Queue is a First-In-First-Out (FIFO) data structure. The available operations to interact with the List structure then, are limited to enqueue() and dequeue() (it is not a case in fact that a queue can be implemented using a List structure).

In the context of Category Theory you might find a parallelism between a List data structure and a Free Monoid https://ncatlab.org/nlab/show/free+monoid which can provide a recursive implementation of a List data structure. The same category equipped with ad-hoc morphism can be used to describe the behaviour of Stacks and Queues data structure.

In the case of Kafka and other similar queue services, besides the complications coming from the distributed case scenario, they don't really resemble the usual case of a Queue data structure. In fact, such a data structure is always supposed to be finite - they are rather implementing the concept of a stream (which could be finite or infinite) under the access condition of a queue (to be completely precise, for Kafka that's not even completely true, since you have the ability to access elements arbitrarily from the topic/queue using an offset). To model such kind of streaming structures an approach similar to this https://ncatlab.org/nlab/show/stream could be used.


Stacking things of different thickness to approximate desired thickness I have $N$ objects of different thickness. Is there an algorithm to determine which of those objects should be stacked on each other to get as near to a desired thickness as possible? (I don't want to numerically check every combination.)

This is as hard as the subset sum problem.  The subset problem asks "is there a way to get exactly the desired thickness?".  Obviously, if we could solve your problem, we could also solve the subset sum problem.  Unfortunately, the subset sum problem is NP-hard, so your problem will be too.

In practice you can try using an approximation algorithm for the subset sum problem, e.g., by rounding to the nearest integer (or to the nearest multiple of $1/k$ for some $k$) and then applying the dynamic programming algorithm for subset sum.  See, e.g., https://en.wikipedia.org/wiki/Subset_sum_problem


Is the search for a k-Hamiltonian Path NP-hard? A $k$-Hamiltonian Path is an Hamiltonian Path where each node (but the last $k$ nodes on the path) is connected to his $k$ successors, and the last $k$ nodes are connected to all of their successors.

This is an Hamiltonian Path:

This is a 3-Hamiltonian Path:

How would you prove that searching for a k-Hamiltonian Path is also NP-hard (if it is)?

Any problem in NP that contains an NP-complete problem as a special case is NP-complete.

Any algorithm that can solve the $k$-Hamiltonian path problem must, in particular, be able to solve the case $k=1$, which is just an ordinary Hamiltonian path.  We can obviously verify a claimed $k$-Hamiltonian path in polynomial time, so the problem remains in NP. Therefore, $k$-Hamiltonian path is NP-complete.


sort n numbers in the range [0,1] without multiplying or dividing Given an array with n real numbers, each in the range [0,1], I need to sort them. Moreover, the only operations that are allowed are comparisons or copying.

It means I cannot multiply or divide the numbers, which prohibits me from using bucket sort.

From what I learned, when you use only comparisons you cant sort any faster that O(nlogn). That means that I can just use any sort algorithm that achieves this bound, let's say heapsort, and be done with it.

However, in this way i don't use the info that the numbers are from the range [0,1]. For this reason,  I'm not sure if I'm right.

The $\Omega(n \log n)$ lower bound still applies; you still can't do better than $O(n \log n)$.

(Proof: Take any array of numbers.  You can find the maximum and minimum in $O(n)$ time.  Then, rescale the array.  In particular, if the minimum and maximum are $\alpha$ and $\beta$, replace each element $x$ of the array with $(x-\alpha)/(\beta-\alpha)$.  After the replacement, every element will be in the range $[0,1]$.  If you had a way to sort such arrays faster than $O(n \log n)$, you'd immediately obtain a way to sort the original array faster than $O(n \log n)$.)


What is the maximum directly adddressable memory capacity? This is taken from OPERATING SYSTEMS: INTERNALS AND DESIGN PRINCIPLES by WILLIAM STALLINGS

Consider a 32-bit microprocessor composed of 2 fields: the first byte contains the opcode and remainder an immediate operand or an operand address.
What is the maximum directly addressable memory capacity?

Now the answer should be 2^24=16777216 bits = 2 megabytes but the solution set says 2^24=16 MBytes

So am I wrong or is the solution set wrong?

Start with a simpler example. Suppose you only had 3 address bits, rather than 24. With $3$ bits we could have $2^3=8$ addresses: 000, 001, 010, 011, 100, 101, 110, 111. In this case, we could think of memory as being divided up into 8 chunks, of equal sizes, with one address per chunk:

memory:  chunk 0 | chunk 1 | chunk 2 | chunk 3 | chunk 4 | chunk 5 | chunk 6 | chunk 7
address:   000       001       010       011       100       101       110       111

For example, the contents of chunk 3 would be addressed by the three bits 011. Now how much memory would there be in total? It'll clearly be 8 times the size of a chunk. Stalling is using a memory model where the chunks are bytes, so with 3-bit addresses, we would have a total memory of $2^3=8$ bytes: one byte per address.

A different computer, though, might be built so that each chunk was 4 bytes. On such a machine with 3-bit addresses we would have $8\times 4 = 32$ bytes of memory, 4 bytes per address.

At any rate, with 24-bit addresses, we'd have $2^{24}= 16777216 = 16\text{M}$ possible addresses, hence that many possible chunks. If each chunk was a byte that would mean that the total addressable memory would be 16777216 bytes, or 16MB. Similarly, if each chunk was 4 bytes long, the total addressable memory would be (chunk size $\times$ number of addresses), or $4\text{B}\times 16\text{M} =64\text{MB}$.


Is a "protocol" a set of algorithms and data structures? I'm not major in science at all and would like to verify whether my understanding is correct or not.

I just did some googling about the definition of protocol, such as in this, this one, this one and more.

And, I would like to know:

is a protocol a pack of algorithms and programming source codes? (in both the computer and network)
regarding the previous question, if so, does that mean that the operating systems/network nodes/applications/hardware indeed have such packs of codes inside their body to perform communications to each other that follow the same protocols? (such as TCP/IP, smb, secure shell, SMTP...)

is a protocol a pack of algorithms and programming source codes? (in both the computer and network)

No. A protocol is an abstract description of how systems communicate. Source code could be an implementation of a protocol, but the protocol is not the same as its implementation. Basically, a protocol tells a programmer "the messages should be formatted like this and you should respond in this way to this message", but it is up to the programmer to decide how to implement this in an algorithm and/or source code.

  regarding the previous question, if so, that means the operating systems/network nodes/applications/hardware indeed have such packs of codes inside their body to perform communications to each other that follows the same protocols? (such as TCP/IP, smb, secure shell, SMTP...)

Yes, operating systems and other hardware do contain code (or sometimes specialized hardware) that implements protocols. However, the way a protocol is implemented may (will) be different between different operating systems and pieces of hardware. The protocol sets standards for how the system should behave to the outside world, but not for how this is implemented internally.


Show how lack of universe levels would create contradiction in homotopy type theory (in Agda) The homotopy type theory book claims in section 1.3 that "As in naive set theory, we might wish for a universe of all types" but from this one could "deduce from it that every type, including the empty type representing the proposition False, is inhabited"

The reference that it gives uses notation that I don't understand, however.

Could someone write invalid Agda code which produces a element of $\bot$, but which would be valid if Agda had a single universe that contains itself?

The problem is not specific to homotopy type theory. In type theory in general, if there is a type of all types, then every type is inhabited. This was shown first by Girard who encoded the Burali-Forti paradox in type theory.

A simplification of the paradox was found by Hurkens. Here is Agda code for it, and here is Coq code.


Dominating set of given size $k$ in $O(2^k |V| |E|)$ Recently I've encountered an interesting case of dominating set problem: given an unweighted and undirected graph $G(V, E)$ and knowing that it contains a dominating set of size $k$, find any such dominating set in time $O(2^k\ \vert V \vert\ \vert E \vert)$.

During my research, I found only some algorithms to find fixed-size dominating set in a $d$-degenerated graphs, but no such restriction is applied in this problem.

Is there any way to solve that problem in such time?

It is well-known (for a very specific group of people) that dominating set is W[2]-complete (for undirected graphs).

You are asking for a fixed-parameter tractable algorithm for solving dominating set in general graphs.  The class of algorithms admitting such running times comprises the class called FPT.

Unfortunately, most people in the aforementioned group believe that FPT is a strict subset of W[1] which again is a strict subset of W[2].

To summarize, we don't think that Dominating Set has an FPT algorithm.

Under the assumption that $\text{FPT} \neq \text{W[2]}$, there is no $O(f(k) \cdot \text{poly}(|V|, |E|)$ algorithm for any function $f$ and any polynomial function $\text{poly}$.

For the Vertex Cover problem, there is such an algorithm, that is, Vertex Cover is in FPT.  Clique and Independent Set are W[1]-complete, whereas Chromatic Number is in XP, which means that it is above the entire W-hierarchy.

Why guarantees of yes-instances won't help

Let $A$ be an algorithm that in running time $f(x)$ (where $x$ is the size of the input) returns a solution of size at most $k$. Algorithm $A$ only works on "yes"-instances.  Create an algorithm $A′$ that takes any input, runs $A$ for $f(x)$ steps, and if $A$ hasn't terminated, returns "no".  If $A$ returns, $A′$ verifies the solution (in polynomial time) and outputs either "yes" or "no" according to $A$s output.

The algorithm $A$ is an algorithm, so it's not likely to get mad at you for trying to cheat; it has to do something for any input, possibly crash and go up in smoke, but there is a nice dichotomy we can use to cheat:

If $A$ gives you any output, we can verify that the output is a correct solution in polynomial time
If $A$ fails to give you any (correct) output in its specified running time, the input has to be a no instance.

Hence, if an algorithm works on guaranteed yes-instances, we can create an algorithm that works on any instance.


Does canonicity imply weak normalization? Context: type theory.
My understanding of:

WN: every term can rewrite to NF.
Canonicity: every term rewrites into canonical form.

Then it leads to an intuition where if canonicity holds, then we get NF = canonical form and therefore WN holds. However, I don't see people state this often, like this question talks about canonicity but never mentions NF or normalization. On nLab, canonical form is said to be normal form, which justifies my "NF = canonical form" guess but it doesn't say WN therefore holds. Therefore I'm doubting my intuition.
So, I wonder if it's right (is there a proof?), or if it's wrong (is there a counterexample?).

Canonicity does not imply weak normalization. First, let me phrase the involved definitions more precisely:

WN: every open term is reducible to a normal term
Canonicity: every closed term is reducible to a canonical term

(Note: in modern metatheory of type theory, it is more common to talk about conversion instead of reduction, and likewise to talk about unique existence of normal forms instead of weak/strong normalization. This answer remains valid if we replace "reducible" above with "convertible").
Normal and canonical terms are not the same. For example, the x variable in x : Bool context is normal but not canonical. Also, the closed term λ(b : Bool). if true then b else b is canonical but not normal.
Extensional type theory has the canonicity property but not WN, SN, or unique existence of normal forms. That's because in ETT it is possible to add an inconsistent definitional equality to the context, or add an equational theory of a Turing-complete system. For example, in the ETT context n : Nat, p : n = suc n the n variable has no unique normal form, since n can be expanded arbitrarily using p.
However, if we have a closed ETT term, we can't have anything dodgy in the context, so a closed term can be still evaluated to a canonical form.


How to simulate systems' unavailability? I am simulating a system where the clients' unavailability is one big issue to the systems behavior.

I gathered the real system logs to analyze the unavailability of the clients in the deployment environments and I computed the values for Mean Time Between Failure (MTBF) and Mean Time To Repair (MTTR).

Now I want to simulate such a system failure in my simulator.
Currently what I am doing is as follows:

1. Every client rolls the dice every 1 minute (Uniform random in [0, 1])
2. If the number if larger than a specified probability (P_unavail),
   the client becomes unavailable for the next (T_unavail) minutes (i.e. (T_unavail) = 10min).

The simulation does not need to capture the whole details of the real world. Showing the trends (how often the failure occurs? how long does the repair take?) is indeed enough. However, the simulation method and parameters should not be arbitrary.

If any one who has some knowledge on it.

Is the method that I am using appropriate?
If yes, what values for P_unavail and T_unavail would be appropriate? Can I compute them MTBF and MTTR from the log analysis?
If no, could you give me any idea?

Thanks,

Fix some probability distribution for failures and failure duration and sample from there. Maybe a Poisson distribution for failures and a normal distribution for repair times would make sense. Compare the results from your sampling with the real data to see whether things match.


Constructing Turing Machine for division with 8 Can someone help me to construct a Turing Machine for this function:

$f(n) = \frac{n}{8}$. If $n \mod 8 = 0$, then
$f(n)$ is undefined.

So the machine should somehow first prove if the number (which is represented in binary) is divisible by $8$ . That means for numbers like $1000$, $10000$, $11000$ and so on. But I don't know how can I check this.

EDIT:

The result from the division is when we delete the last 3 digits in the binary representation of the number. I think this is not so hard. But I still have a problem with the first part. How can I prove if the number is divisible?

A number (in binary) is divisible by 8 if it ends at least by 3 0's. Remember that an integer is divisible by 2 (without remainder) if it ends with 0 and since $8=2^3$ its binary representation must end with at least 3 zeros.

In fact a finite automaton is enough to recognize numbers divisible by 8. The following transitions are for a DFA which can be easily rewritten as TM instructions.

$q_1$ - start state, $q_4$ - accept state.
$\delta(q_1, 0) = q_2, \delta(q_1, 1) = q_1$
$\delta(q_2, 0) = q_3, \delta(q_2, 1) = q_1$
$\delta(q_3, 0) = q_4, \delta(q_3, 1) = q_1$
$\delta(q_4, 0) = q_4, \delta(q_4, 1) = q_1$


How did the Logic Theorist prove the Pons Asinorum? I was reading about the Logic Theorist proving many of the Whitehead and Russell's Principia's theorems. However, I cannot find any technical explanation on how the program proved those theorems and specifically what method did it use to solve the Pons Asinorum. I'm interested in understanding how "independent" it was in providing those proofs, mostly since it is celebrated as an "AI" program.

If you google "logic theorist source code" you find this which is clearly not the original source code, but presumably is a modernization of the ideas in the code. You can also find this 1963 RAND memorandum which is a more contemporary description of the system. It seems to include a complete code listing as well as descriptions in terms of flowcharts.

As far as I can tell, it proved basic statements in essentially classical propositional logic.  The main idea is backward chaining.

Page 52 of Perspectives on the History of Mathematical Logic shows the (erroneous) proof of Theorem 2.85 in Principia Mathematica and the proof Logic Theorist produced.  Theorem 2.85 (using more common notation) is $$((P\lor Q)\Rightarrow(P\lor R))\Rightarrow(P\lor(Q\Rightarrow R))$$ which (ironically) is actually easier to read in Logic Theorist's notation, (((PVQ)I(PVR))I(PV(QIR))), than it is in the aforementioned page. As you should be able to tell, this has no particular connection to any geometrical theorem, let alone the isosceles triangle theorem.  I have no idea why it's linked that way on Wikipedia.  You could, however, take e.g. Tarski's axioms for planar geometry and apply the same proof search techniques to questions in Euclidean geometry as done in Automated Development of Tarski's Geometry by Art Quaife. I can't find a good reference, but I'm fairly certain novel and elegant proofs have been found when automated theorem proving (in this style) has been applied to planar geometry. This isn't surprising as these systems tend to search the proof space starting from the shortest proof candidates.


How can I check constraints on my state machine behaviour? My background is fairly practical rather than theoretical, so this question may be a bit basic.

I have a state machine with events, and events may optionally trigger action functions to be called as part of the state transition.  In practice, actions functions do things like lighting LEDs.  The state machine is defined in an in-house domain-specific language, and a tool generates C code from the definition.

I have constraints that need to be satisfied -- eg "when in state A, only LED 1 and 5 should be lit."

What practical techniques are there to check that my state machine design satisfies my constraints?

I considered using Prolog.  If I could enter the side-effects of my action functions, the state machine states, and the valid transitions and action functions, I should be able to query whether the constraints hold true -- is this correct?

Are there other frameworks or tools that could be useful in this situation?

Use a model checker.  This is exactly what they're good for.  You might look at SPIN and NuSMV as a starting point, but there are many others as well.


Is $L=\left \{ wxw \,\,|\,\,w,x \,\in \left ( a+b \right )^{+}\right \}$ Regular? Question

Is $L=\left \{ wxw \,\,|\,\,w,x \,\in \left ( a+b \right )^{+}\right \}$ regular?

My Understanding/Doubt
We can say that Language

$L_{2}=\left \{ wxw \,\,|\,\,w,x \,\in  \left ( a+b \right )^{*}\right \}$ is regular

By making  $x=(a+b)^{*}$ and $w=\epsilon$
Based on above Understanding , i can say that $L$ is regular?

My regular expression will be-:
$L=a(a+b)^{+}a+b(a+b)^{+}b+a(a+b)^{+}b+b(a+b)^{+}a$
Am i right?

When is a string of the form $a^*ba^*b$ in the language $L$, i.e., of the form $wxw$, for nonempty $w,x$?

Or, to be more explicit, what is the language $L \cap a^*ba^*b$?


what is the difference between Operating system and Window Systems? Quoting from Tannenbaum_Operating_Systems_Design :

  On top of the operating system is the rest of the system software.
  Here we find the command interpreter (shell), window systems,
  compilers, editors, and similar application-independent programs. It
  is important to realize that these programs are definitely not part of
  the operating system

I am not getting the difference between these two keywords ,isn't the Windows an Operating system so what's the meaning of this Window Systems which is not the part of Operating System.
When we say that windows is an operating system then how can we make a distinction between windows systems and an Operating system ?

I think you misunderstand the window systems. It is software to manage different parts of the display screen, not the Windows OS. In Microsoft's Windows OS, the window system is Desktop Window Manager.


Which Type of Grammar is this? I am learning Compiler Design. Can somebody explain what type of Grammar this is? The answer given is $LL(1)$ but there exists a left recursion in the grammar so it cannot be $LL(1)$. I derived the parse table it had conflicts. Am I doing some thing wrong or is the answer given wrong?

My texbook defines:

  For LL(1) Grammar if there is left recursion or left factoring then that grammar is not LL(1) grammar if this applies to this grammar then it is not a LL(1) grammar

$E \to E+T \mid E$

$T \to T$#$F \mid F$

$F \to (E) \mid i$

I also have one more question: "Is there a Grammar which can be LL(1) but not LALR(1)"

There is left recursion in the grammar, so it isn't $LL(1)$.

The set of $LL(1)$ grammars is a proper subset of the $LR(1)$ grammars, see for example this summary, which incidentally also shows that $LL(1)$ isn't a subset of $LR(0)$. The first part is is intuitively easy to see, the $LL(k)$ parser has to decide looking only at the $k$ first symbols; the $LR(k)$ has the whole left hand side (and $k$ extra symbols) at its disposal.


Converting NFA to regular expression Here is the regular expression I made for it

This is my first answer, used the naive method aka don't know what am doin' method.
$$
\epsilon \cup a^* \cup (a^*b) \left((a| b^*a) | \left( (a|(b^*a))ba^*\right) \right) ^*
$$

this is my re-worked answer, with the state removal method.

$$
\left( a^* \cup (b)(a \cup bb^*a) \right) ^*
$$

steps taken :

Add a new start state and a new final state.
Add epsi transitions to the new states.
Remove Q2
Link between Q1 and Q3 is now $a \cup bb*a$
Remove Q1
Add a new link between Q0 and Q3 with $ (b)(a U bb*a)$ label
Remove Q0
There are three paths. a*, the big regex and the start with epsi
$\epsilon \cup a* \cup (b)(a \cup bb*a)$
Remove Q3
We get $\epsilon \cup \left( a^* \cup (b)(a \cup bb^*a) \right) ^*$ =$ \left( a^* \cup (b)(a \cup bb^*a) \right) ^*$

My questions are:

Is my regular expression correct ?
What happens if it loops ?

To be clear, let's say we have the string aababaaaaabab

I think that string is recognized by the NFA, but I'm not sure it is by my regular expression.

does the $^*$ at the end cover it correctly ?

ps: As suggested I moved this from math.se

For your specific problem, I propose a regular expression in a ad-hoc meth, and the outcome was: (notation comes from Regular Expressions)

  (a*(b(b+)?ab?)?)*

I found it with the next methodology: moving from simple to more complex ( states to final states)

To arrive to $q_3$, you need to put a
This a comes from $q_1$ or $q_2$
If it comes from $q_1$, use a b else it comes from $q_2$, so use one o more b's: b+
But, $q_2$ comes from b too, so union these two possibilities, a comes from b((b+)?)
For that, we have b(b+)?a in regular expression to go from $q_1$ to $q_3$
Now, If you want to move from $q_3$ to $q_0$, you need a extra b, so use b?. This is the part of regular expression: b(b+)?ab?
To start you probably have empty string, or a's or b to go from $q_0$ to $q_1$
Above can achieve with a* and visit $q1$ or not visit is express like: a*(b(b+)?ab?)?
Finally, you could have a nothing of that, or more than once this strings, so you should use *, and take as regular expression: (a*(b(b+)?ab?)?)*

Test Cases

I tested with the next strings and all match with the regex:

aaaaba
aababaaaaaa
abbbbbba
abbbbbbab
abbbbbbabaaaa
abbbbbbaba
bab
ba
babaaaa
aaaaa
bbba

In the other hand, you may be interested in consider algorithms to converting DFA to Regular expression, so you can find a dynamic programing algorithm, and the full description of this approach is given in the book of Models of Computation, Chapter 4. And other method, Brzozowski algebraic method. All above, because with the powerset constructive you can obtain a DFA from NFA.


How to create disjoint sets out of an adjacency list I'm not a computer scientist, so please bear with me if I'm misusing some terminology.

What I'm trying to do is to find the different components of an undirected graph.

I have an array of pairs that represent the edges of my graph, like so:
[[1,3],[4,2],[2,1],[5,6],[100,20],[22,5]] and what I want to create out of this are arrays (or objects) containing the connected vertexes (the disjoint sets or components, like this (for the above example): [[1,2,3,4],[5,6,22],[20,100]]

My first approach was to convert the array of pairs into an adjacency list, using hashmaps/tables/sets or something in this line it can be done in O(n) time and additional space (n being the number of pairs). Then using BFS, I scan every vertex in the graph. Whenever the queue is empty, I have completed a component/disjoint set. If unvisited nodes are still in the graph, this is a new component/disjoint set. Until all the nodes are visited.

Now, I learned about the disjoint-set data structure.

My question: Using disjoint-set data structure how can I convert my array of pairs into the disjoint components of the graph I'm looking for? Any resources are also very much appreciated. I'm still learning and don't really know what I'm talking about.

What are the pros and cons of the first approach compared to the second approach.

Oh, BTW, if this is the wrong place to ask this question, please, advise!

Thanks in advance!

In the disjoint-set approach you start from a collection of single vertices and repeatedly join the incident vertices of the edges. This will give you the connected components in $O(n+m\times(\text{find}+\text{union}))$.

The BFS approach takes only $O(n+m)$ and thus is faster, since the disjoint set operations take more than O(1).


What is a good reference to learn about state transition systems? I am studying different approaches for the definition of computation with continuous dynamical systems. I have been trying to find a nice introduction to the theory of "State transition systems" but failed to do so.

Does anybody know a modern introduction to the topic?
Of particular interest would be something dealing with computability.

One of the key uses of state transition systems, also known as labelled transition systems, is for modelling concurrent systems.

One very nice, delightful even, book that uses labelled transition systems to give semantics to concurrent formalisms CCS and the $\pi$-calculus is
Communicating and Mobile Systems: the Pi-Calculus by Robin Milner. Definitely worth reading.

Principles of Model Checking by Christel Baier and Joost-Pieter Katoen is about model checking concurrent systems, so early in the book labelled transition systems are introduced to give semantics to such systems. This book also talks about probabilistic labelled transitions too.

Another possibility is Concurrency: State Models & Java Programs by Jeff Magee & Jeff Kramer. This book takes a more practical approach, but comes with an analyzer for systems described using labelled transition systems.

I don't know much about continuous dynamic systems. Perhaps you want to look at hybrid systems?


How can I infer inputs to a function, given an output? Is there a way to generate a set of inputs, for a given output of a function? This may be a common thing in lisp/haskell world, but I'm not aware of it. Is this what mini-kanren does?

I understand that there may not be a general solution to this problem, since the halting problem may apply here. Say the function implementation is constrained to remove unlimited recursion. Type inference engines obviously do something similar to figure out the types of variables, I would like to generate actual values.

I'm thinking of a couple of scenarios where this might be useful:

func blowup(x): 1/x

I would like some sort of static checker to figure out that this function will cause problems if x=0.

func launch(x): ...launch missle x miles...
func isSafe(y): if x > 10 then true else false
func main(): x=.1; if isSafe(x): launch(x)

In this case, I would like to not only infer values of launch, but I would like to take isSafe as a constraint and tell me at compile time (since all information is available) that x of .1 not a good value.

Btw, I'm not looking for a library to do this. What I would love is either the name of this concept (beyond the generic 'static checking') and reference material which describes this idea (easily read papers, books, etc.). I should also mention that I'm aware of tools such as quickcheck. I'm not looking for a probabilistic way of inferring values. I would like a deterministic way of inferring values as early as possible, even if that means that my solution limits the types of expressions I can express.

In the worst case, this is impossible.  However, there are techniques for inversion that can work on some programs.  Of course, you shouldn't expect them to work on all programs given that the problem is hard.

Here are a few standard approaches:

Theorem proving. Use the VCGen part of a theorem prover to generate a precondition formula, where if the formula is true, that implies that the function produces the desired output (or divides by zero, etc.).  Then, use an automated solver to try to find a satisfying assignment to that formula.
Symbolic execution. Execute the function symbolically, and build up a symbolic expression that represents the output of the function, in terms of a bunch of variables (unknowns) that represent the inputs to the function.  Then build a formula by setting that expression equal to the desired output, feed that formula to a SMT solver and ask the solver to find a satisfying assignment for the formula.
Concolic execution.  Pick concrete values for the inputs to the function.  Execute the function on those inputs and record what path it took.  On the side, build up a symbolic expression that represents the output of the function, if it follows the same path.  Build up a "path constraint", which is a formula that is the conjunction of all of the branch conditions followed: the path constraint is a formula over symbolic variables representing the inputs, where inputs that make the path constraint true will cause the function to execute the same path that was previously recorded.  Then, write down a formula that represents the statement "the function takes that path, and its output is equal to the desired value", and feed this to a SMT solver or SAT solver and ask it to find a satisfying assignment.  See concolic testing.

These approaches have different tradeoffs and perform differently, but as you can see, they are similar conceptually.  Here are some significant differences:

Theorem proving and symbolic execution can have problems with loops.  For instance, theorem provers usually require you to supply a loop invariant for every loop.  Concolic execution circumvents this by not trying to reason about all possible paths; only a single one.
Theorem proving and symbolic execution can have problems with state space explosion, as the number of possible paths through the function can be exponentially (or even infinitely) large.  Concolic execution circumvents this by not trying to reason about all possible paths; only a single one.
Theorem proving can use more expressive logics, such as fist-order logic.  Symbolic execution and concolic execution often use propositional logic or a SMT extension.

You can find lots of reference material on these approaches.  For instance, today they're taught in a number of advanced (e.g., graduate) program analysis courses, and there are many publications in the research literature on these topics.


Designing a parallel algorithm to find the second largest item in an array Using pseudocode, I need to design a parallel algorithm that, when given k keys, a[0], a[1], a[2],... a[k-1] stored in an unsorted array a, would find the second largest key in it.

I'm new to parallel computing, so I know that in terms of sequential programming, we can use bubble sort with two passes. First pass gets your the largest element, while the second pass will get you the second largest element, the goal. Should we split the bubble sorta via parallel processing, we only need to do one pass each iterations largest element to find the second largest. My problem is I don't know how to exactly 'parallelize' the algorithm.

I'll sketch informally one obvious variant, assuming some model with shared memory and unbounded parallelism (I'm not going to discuss the synchronization issues, though). Lets denote the size of the original array as $n$.

Divide your array into $k$ subarrays of approximately equal sizes $s_i$, such that $s_i \approx \frac{n}{k} \wedge s_i \ge 2$, then assign each subarray to a thread or whatever you use, lets call it "process". This assignment procedure can be (should be) implemented in a way such that its time complexity is $O(1)$.
Then $i$-th parallel process finds the largest $M_i$ and the second largest element $m_i$ of $i$-th subarray sequentially. It's an easy linear complexity algorithm, which works in one go through all the elements of the input. So, time complexity of this step is $O\left(\frac{n}{k}\right)$. $i$-th process will store the results in the first two elements of $i$-th subarray, so you won't need to send $M_i$ and $m_i$ anywhere and resolve the synchronization issues connected with sending/receiving. That's why we need $s_i \ge 2$, and if there is not enough elements then it is not worth to process it in parallel.
Wait until all processes finish (its called a barrier). At this point you have an array of all the results ($M_i$ and $m_i$) of all processes. Now, simply use the sequential algorithm again. The resulting $m$ will be the answer for the whole original array. Time complexity of this step is $O(k)$.

The overall time complexity of our algorithm is $O\left(\frac{n}{k} + k\right)$. Under this very simplistic model it's better to have the number of parallel processes $k \sim \sqrt{n}$ to make the overall time complexity minimal: $O \left( \sqrt{n} \right)$. This result can be easily obtained using differential calculus. Of course, this result is very far from the reality of practical parallel computing: we don't have unbounded parallelism in practice and we need to consider the parallel processing management overhead.


How can a 64-bit processor address 2^64 different memory locations at a time? I understand that a 64-bit processor can hold a 64-bit long address and that a 64-bit address can represent $2^{64}$ different values. But I don't understand why that processor can address $2^{64}$ different locations in memory at one time and thus process billions of billions of GB at a time (theoretically).

I haven't found a satisfying answer on google. On google they just explain that a 64-bit address can represent $2^{64}$ different values and thus it equates to the processor being able to process $2^{64}$ values (or memory locations) at a single time, though I am interested in as much detail as possible regarding how exactly that looks like.

64-bit address means for me that this address can have one of $2^{64}$ possible values and not that it can process $2^{64}$ at a time.

It's not clear where you found this claim so it's hard to tell exactly what it's supposed to mean.

But, obviously, no, the CPU can't access every memory location simultaneously. Each CPU instruction can only access some fixed small number of memory locations at a time, and only a fixed small number of instructions can be executing simultaneously.


How do I prove that all primitive recursive functions are computable? I stumbled across an exam question, and I am not sure how to prove that that all primitive recursive functions are computable. Is there a formal definition of this?

You prove it by structural induction over the definition of primitive recursive functions. The definition of computable is: a function is computable if it is computable by a Turing machine. There are many other equivalent definitions.


Q-learning in a Dynamic environment I am new to reinforcement learning. Lately, I  have learned Q-learning using the following tutorial.

Is Q-learning still possible if the environment is dynamic. Using the environment of the tutorial as an example, in some states it is possible to go from room 0 to room 1 and and it is not possible to go from room 0 to 4.

Is it possible to use Q-learning in a problem like that? if not is there an algorithm that handle dynamic environments?

In general you can't change the state and action spaces (rows and columns of your reward matrix) since that changes the underlying model that you are sampling with Q-learning.  It'd be similar to changing the population you're sampling when statistically sampling.  Hence, you have to define a set of actions and states that don't change in order to use Q-learning.  Instead of the house graph, you'd need something else.  Ideally you'd have to come up with a set of states and actions that didn't change as the house's topology changed. E.g. actions could be strategy to use could be the action given the number of rooms in the house and total number of edges (note: this'd probably be a poor choice, but I needed an example.).
All that said Q-learning albeit a little slow is pretty robust to some types of disturbances.  If the model doesn't change significantly (e.g. you add a room) and you are exploring a large state space (statistically), then your older policies (solved Q matrices) might be nice breadcrumb trails for your new algorithm's exploration strategy, and the algorithm may re-learn much faster.  However, I don't know about the theoretical guarantees (look into terms like "cross learning").


Given two heuristic values how do I tell which one is admissible? I am given 2 list of admissible values for a graph, and the graph with the real cost to each of the nodes.

Am I correct in thinking the way to see which one is admissible is add up all the values of the h(n) and compare it to the total real cost of the graph?

Example:

  h1 total = 681 h2 total = 732

  Total cost of graph = 704

Does this mean h1 is admissible as it doesn't overestimate?

A heuristic function $h$ is admissible, if it never overestimates the cost for any given node. Formally speaking, let $h^{*}$ map each node to its true cost of reaching the goal. The heuristic function $h$ is admissible, if for all nodes $n$ in the search tree the following inequality holds:
\begin{align}
  h(n) \leq h^*(n). \tag{$\star$}
\end{align}

That means for checking whether a given heuristic function $h$ is admissible, we have to verify that the inequality $(\star)$ holds by either
  (a) calculating the real cost $h^{*}$ for each node and comparing the values, or
  (b) proving it by using additional information available of the heuristic.

For example, we know that the eucledian distance is admissible for searching the shortest path (in terms of actual distance, not path cost). Note also that any consistent heuristic is admissible (but not always vice-versa).

For your example, there is no additional information available regarding the two heuristics. Thus you have to calculate the real cost $h^*$ for each node, and then check whether the inequality $(\star)$ holds (I leave this task to you).

By checking the total cost you can neither prove that a heuristic is admissible nor that a heuristic is not admissible. The problem with this idea is that on the one hand you sum up the costs of the edges, but on the other hand you sum up the path cost (the heuristic values). For example, consider the following search tree with start node $A$ and goal node $C$

and the following heuristic functions $h_1$ and $h_2$:

\begin{align}
  h_1(A) = 20; &\quad h_2(A) = 8 \\
  h_1(B) = 10; &\quad h_2(B) = 11 \\
  h_1(C) = 0; &\quad h_2(B) = 0 \\
\end{align}

The sum of the total cost of the search graph is $10 + 10 = 20$. The sum of the heuristic values of $h_1$ is equal to $20 + 10 + 0 = 30$, which is larger than $20$ although $h_1$ is admissible. The sum of the heuristic values of $h_2$ is equal to $8 + 11 + 0 = 19$, which is smaller than $20$, but $h_2$ is not admissible, since $h_2(B) = 11 \nleq h^{*}(B) = 10$.


How hard would it be to state P vs. NP in a proof assistant? GJ Woeginger lists 116 invalid proofs of P vs. NP problem. Scott Aaronson published "Eight Signs A Claimed P≠NP Proof Is Wrong" to reduce hype each time someone attempts to settle P vs. NP. Some researchers even refuse to proof-read papers settling the "P versus NP" question.
I have 3 related questions:

Why are people not using proof assistants that could verify whether a proof of P vs. NP is correct?
How hard or how much effort would it be to state P vs. NP in a proof assistant in the first place?
Is there currently any software that would be at least in principle capable of verifying a P vs. NP proof?

I'm going to disagree with DW. I think that it is possible (although difficult) for a P vs. NP result to be stated in a proof assistant, and moreover, I wouldn't trust any supposed proofs unless they were formalized in this way, unless they came from very reputable sources.
In particular, none of the resources DW states are based on type theory, which is a very promising direction for proof assistants. Coq has been used to formalize the proof of the 4-color theorem among others, so it's clearly capable of some heavy mathematical lifting.
To answer your specific questions:

The main reason is that theorem provers aren't widely accepted in the mathematical community. Learning them takes effort, and mathematicians are often skeptical of the underlying techniques (type theory, constructive math, etc.)
But there are some fields where leading researchers are very comfortable with making large developments formalized in a proof assistant, like category theory, programming language theory, formal logic, etc. So I think there is as much of a cultural issue as an inherent feasibility issue.
The other reason is that, so far, most of the purported "proofs" have been by cranks, who don't want to formalize their result because it will inevitably reveal the flaws.

It is not hard at all to state P vs. NP in a proof assistant. One could use Turing Machines, but it would probably be easier to model a simple Turing-complete programming language using inductive families to model small-step semantics, and define the run-time as the number of steps a program takes. You could define $P$ as the languages accepted by programs halting in a polynomial number of steps, and $NP$ as languages that can be verified in polytime with a polynomial-length certificate.
EDIT: It turns out there are existing techniques for showing that algorithms run in polynomial time in a theorem prover. So this could be used either to show a polytime algorithm for an NP-hard problem, or to derive a contradiction from the existence of such an algorithm.

There is tons of software that is capable of verifying such a proof, provided the proof was written using that software. The two candidates I'd put the most stock in are Coq and Lean. Coq in particular has been used to verify several major results in mathematics.


If is true f(n) = Θ(g(n)) and if f(n) = o(h(n)) then g(n) = o(h(n))? In asymptotic notation the transivity holds, however what happens when we have small o such as if f(n)= o(h(n)) does that means that also g(n)=o(h(n)) holds?
i take as granted that both of f(n)=o(h(n)) is true and f(n)= O(g(n)) (from THETA) then i need to show
g(n) < c h(n) given that i have f(n) <= d g(n) and f(n) < c h(n) how one would proceed from there?

From $f(n) = \Theta(g(n))$ you know that, for some positive constants $c \in \mathbb{R}^+$ and $\eta \in \mathbb{N}$, and for all $n \ge \eta$, it holds that $f(n) \ge c g(n)$, i.e., $g(n) \le \frac{1}{c} f(n)$.$^1$
Moreover, from $f(n) = o(h(n))$, you know that for any constant $c' > 0$ there is some $\eta'_{c'}$ such that $f(n) \le c' h(n)$ for any $n \ge \eta'_{c'}$.
Pick any constant $c'' > 0$ and let $\eta'' = \max\{\eta, \eta'_{c'}\}$ where $c' = c \cdot c'' > 0$.
From the previous inequalities we have that, for any $n \ge \eta''$:
$$
g(n) \le \frac{1}{c} f(n) \le \frac{1}{c} \cdot  c' h(n) =  c'' h(n),
$$
thus proving that $g(n) = o(h(n))$.

$^1$: In fact, the weaker condition $f(n) = \Omega(g(n))$ suffices.


Conway's Game of Life: Is it really P-complete? Wikipedia claims that the Game of Life is P-complete (or the decision problem version of it is; the function version, I suppose, would then be FP-complete).
Colloquially, P-complete and FP-complete problems are difficult, if not impossible, to parallelize.  However, most software for evaluating the Game of Life is parallelized.  The algorithms aren't even that hard to understand.  This seems to be in conflict.  What is going on?  Is Wikipedia wrong, or do I misunderstand something?

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


Why deadlock in cigarette smokers problem "The Little Book of Semaphores" (2nd Ed. by Allen B. Downey, section 4.5.1) as well as Wiki (link) mentioned that a trivial solution (as shown below) to the 'Cigarette smokers problem' will cause a deadlock. Somehow I couldn't wrap my head around it. Pls help me undersatnd how deadlock can occur for the below solution.
P.S. We assumed agent code cannot be modified and We're free to use semaphores and other variables as needed

Code sample (from the book):

     Agent A                 Agent B          Agent C
1 agentSem.wait()     agentSem.wait()      agentSem.wait()
2 tobacco.signal()    paper.signal()       tobacco.signal()
3 paper.signal()      match.signal()       match.signal()

     Smoker I           Smoker II               Smoker III
1 tobacco.wait()       paper.wait()           tobacco.wait()
2 paper.wait()         match.wait()           match.wait()
3 agentSem.signal()    agentSem.signal()      agentSem.signal()

    Assume semaphores 'tobacco', 'paper', and 'match' are  initialized with
    zero, and 'agentSem' is initialized with one.

Agent A consumes agentSem, and produces tobacco and paper.

That might make Smoker I smoke but he is late: Smoker II already took the paper and Smoker III took tobacco.

Now, all the smokers are stuck, and the agents as well.


How to understand and apply pumping lemma to prove $a^{i+1} b^{4i+2}$ is not regular? I am having trouble understanding how to apply Pumping Lemma to show a Language is not regular.
If the alphabet is $\Sigma = \{a, b\}$ and the language is $L = \{a^{i + 1} b^{4i + 2} \mid i \in \mathbb N\}$, how do I prove the language is not regular using pumping Lemma?
Also what is a pumping length, how do i know to assign a pumping length to the language stated above?

Since I see questions about the pumping lemma on this site quite often, I decided to write a bit of a longer answer hoping that it helps people "get" the PL rather than just treating it as a "plug-n-chug" tool given to us by the gods of math.
Understanding the PL
I think the best way to go about it is to basically (re-)derive the lemma.
The idea is that if some language $L$ is regular, then there exists some DFA $A$ such that $A$ recognizes $L$.
Now say that $A$ has $m$ states and suppose that we have some $w \in L$ with of length $n > m$ (note that any infinite $L$ must contain such a word) and consider the run of $A$ on $w$.
As $w$ has more characters than $A$ has states, there must be some state $q$ which occurs at least twice in $A$'s run on $w$, i.e. if we draw out the run through the graphic representation of $A$ we find some loop.
In more formal terms, this means that there must be some substring $s$ of $w$ -- so $w$ can be written as $w = rst$ where $r$ and $t$ are remaining parts of $w$ left and right of $s$ -- such that $A$ is in state $q$ on the both the first and last symbol of $s$.
At this point, we need to understand the D part of DFA: $A$ is deterministic, so given that we start from the initial state on any input of the form $r\Sigma^\ast$ (any string starting with the substring $r$) we will always end up at the state $q$ and similarly, starting from $q$ on the word $s$ we always end up at $q$ again and finally, starting on $q$ given the word $t$ we always end up at the same (accepting) state.
I like to think of such deterministic machines as music boxes; if you start the at the same point they end up playing the same melody.
This means that we can now create new words which $A$ must also accept by making $A$ go into state $q$ and presenting it with $t$, and the easiest way to do so is by taking the known string $r$ to get it to the state $q$ initially, then repeating $s$ some $k \geq 0$ times (which, because we start at $q$ now) will always get us back to $q$ and then appending $t$ to make $A$ go into an accepting state.
Hence these words are of the form $w_k = rs^kt$ for some $k \geq 0$.
Taking a step back, we have now basically argued that $A$ cannot distinguish between $w$ and $w_k$; the result of the computation will always be the same.
This is the essence of how the pumping lemma works.
Using the PL
To apply the pumping lemma we must now find such $w$ and $k$ where $w \in L$ and $w_k \notin L$. Usually one will not be able to give $w$ directly as the size of the automaton $A$ is unknown (in fact we are trying to argue that such an $A$ does not exist, so yeah).
In most cases, this boils down to taking a "large" string in $L$ such that the middle part of said string is big enough for us to find some part that if repeated would give us the $w_k$ we need.
Let us get specific now.
Our language is $L = \{a^{i + 1} b^{4i + 2} \mid i \in \mathbb N\}$.
We assume that $L$ is regular and thus admits a DFA $A$ of size $m$.
If we consider the string $w = a^{10m + 1} b^{40m + 2} \in L$, we find that a state repetition must already occur in the $a$-part of $w$ as $a^{10m + 1}$ has more symbols than $A$ has states.
Hence there must be a decomposition $w = rst$ where $r = a^{\ell}$, $s = a^k$ and $t = a^{10m + 1 - \ell - k} b^{40m + 2}$ with $0 \leq \ell < m$ and $0 < k \leq m$ (Can you figure out why the bounds on these variables are this way? This is a good test to see if you are confident with the first part, I think).
If we now consider the word
$$ w_2 = rs^2t = a^\ell (a^k)^2 a^{10m + 1 - \ell - k} b^{40m + 2} $$
and unpack it to
$$ a^{m + k + 1} b^{40m + 2} $$
we see that $w_2$ is not in $L$.
It follows that $A$ does not recognize $L$ as we assumed that $A$ accepts $w \in L$ and then argued that it must also accept $w_2 \notin L$.
As the choice of $A$ was arbitrary we find that no DFA can recognize $L$, which means that $L$ is not regular.


What is f(x,y) in Digital Image Processing? I am a novice in Digital Image Processing, and while reading the book of DIP by Gonzalez and Woods, I find that they have represented digital image as $f(x,y)$ but nowhere it is mentioned what is $x$ and $y$ actually that we are passing to the function $f?$ Does $f(x,y)$ represent the intensity of the points located at point $(x,y)$, so does $f$ actually returns the intensity of the pixel at that point or is it something else that I am missing?

Yes, it represent the intensity at that point.

f( x, y ) gives the intensity of a channel at position (x, y)

Source : https://courses.cs.washington.edu/courses/cse557/00wi/lectures/imageprocessing.pdf


Cantor's diagonal method in simple terms? Could anyone please explain Cantor's diagonalization principle in simple terms?

Here's the standard application explained in the simplest terms I can:

Theorem: There are more real numbers than there are integers.

Lemma: A real number has a decimal representation (that might not terminate), and all decimal representations create real numbers.

Proof of Theorem: Suppose there are as many integers as reals. Then we can list the reals in some order,

$r_1 = 3.141592...$

$r_2 = 2.718281...$

$r_3 = 1.000000...$

and so on for each $r_i$ where $i$ is an integer

There is a contradiction because I can construct a real that is not in the above list. Let $r' = 0.d_1d_2d_3d_4\ldots$ where $d_1$ is not equal to the 1st digit after the decimal of $r_1$, $d_2$ is not equal to the 2nd digit after the decimal of $r_2$, and so forth. For example, I could add 5 and take it mod 10. In the example this gives $r' = 0.665\ldots$. The contradiction is that $r'$ is not in the list, because for any $i$ I know that $r'$ and $r_i$ differ by at least $4*10^{-i}$ (since they differ in $d_i$).

The fact that the reals cannot be enumerated as such shows that they are larger than the integers. But, the important result of Cantor is simply that they cannot be enumerated.


default TCP Maximum Segment Size Why default TCP Maximum Segment Size is 536? If found this line in TCP/IP by behrouz forouzan

The short answer is because of RFC 791 which reads "All hosts must be prepared to accept datagrams of up to 576 octets (whether they arrive whole or in fragments)."

If you take 20 octets for IP and 20 octets for TCP then you're left with 536 for MSS.

Now why is 576 chosen? Mostly likely the fact that machine at that time wasn't that powerful and some reasonable minimum number had to be agreed that would be supported across all of the devices regardless how low-fi they are.


Clock skew vs clock offset in the context of clock synchronization network protocols In the context of clock synchronization among nodes of a network, what is clock offset and what is clock skew?

Are these terms synonymous or is there a difference between them?

The terms aren't exactly the same, although have some similarities.

Clock Skew - a skew in the clock signal is referred to a time gap between the expected arrival of the clock to it's actual arrival, the skew can be positive or negative.
This might also be called jitter, it may be considered as sort of instability parameter of your system.
Skew is measured in time units (i.e. ns, us, etc.)
When designing a synchronous system you must make sure that your system doesn't have timing violations due to clock skews.
Clock Offset - offset of the clock is a delay of a given clock source, it might be known, or unknown. Offset can be measured in time units or phase degree.
Many times clock offset is intentional, for instance it's very common for data to be synchronised to falling edge of a clock, in this case, the receiver of the data, might consider the clock to have an offset of 180 degrees.

Another popular case might be receiving data in a certain clock, for instance 100MHz, while your system also has 100MHz clock, the 2 clocks might have a very low jitter rate, but the offset between them is usually unknown, there are components that can compensate and "fix" the offset and synchronise clocks such as PLL's.

Hope it's more clear now.


Register Allocation and Definition of Interference In my textbook on compiler design [1], it describes interference between two variables (the property that they cannot be in the same register at once) as follows:

  Definition 9.2:  A variable $x$ interferes with a variable $y$ if $x \neq y$ and there is an instruction $i$ such that $x \in kill[i], y \in out[i]$ and instruction $i$ is not "$x := y$"

This definition does not make sense to me. If I interpret this in plain English:

  A variable interferes with another if some variable $x$ is being overwritten, while some variable $y$ is live at the exit of the instruction, and the instruction is not $x := y$ and $x$ and $y$ have distinct values.

To me, a more logical definition of interference is if two variables $x$ and $y$ appear in the same $gen$ set of some instruction $i$. This necessarily means that these two variables are used (i.e their value) in the same instruction. Is there some crucial detail that I am missing?

For those interested, this definition appears on page 197 of the book referenced above.

Your "reading" of the definition is a little unclear. In particular, it says nothing about the values of the variables. Here's a clearer reading:

  A variable $x$ interferes with a variable $y$ if 1) they are not the
  same variable, i.e. a variable never interferes with itself, and 2) there
  is some instruction other than $x := y$ where $x$ is overwritten while
  $y$ is live at the end of the instruction (and typically also
  during, but a multiple assignment instruction like $(x,y):=(a,b)$ would be an example where variables can interfere even though $y$ is not live during the instruction).

As the book points out immediately after that definition, if $x$ and $y$ have the same value (for some stretch of code), then there is no reason they can't be held in the same register (in that stretch of code). This is what makes ignoring $x := y$ instructions valid. The analysis does not calculate the values of anything however. $x$ and $y$ interfere in $\{x := k;y := k; f(x,y)\}$ and so will be assigned different registers. For this analysis to exploit the fact that they have the same value, a prior optimization pass would need to rewrite it to $\{x := k; y := x; f(x,y)\}$.

Your definition is also incorrect. The $gen$ set of $x := k$ is empty, but certainly two variables can't share a register if one is being mutated and the other isn't. Again, as the book points out immediately after the definition, the definition is close to saying that distinct variables $x$ and $y$ can't both be live at the same time. (Both being live at the same time would be formulated as $x,y \in out[i]$.) This is a more conservative condition than yours, but it is still incorrect for the same reason. If $x := k$ is the last occurrence of $x$, and thus isn't in the $out$ set of that instruction, it still interferes with $y$.


Can anyone tell me why this search parition for quicksort works? private static < T extends Comparable < ?super T >> int partition(T[] a, int first, int last) {
  int mid = (first + last) / 2;
  sortFirstMiddleLast(a, first, mid, last);

  swap(a, mid, last - 1);
  int pivotIndex = last - 1;
  T pivot = a[pivotIndex];

  int indexFromLeft = first + 1;
  int indexFromRight = last - 2;
  boolean done = false;
  while (!done) {

    while (a[indexFromLeft].compareTo(pivot) < 0)
    indexFromLeft++;

    while (a[indexFromRight].compareTo(pivot) > 0)
    indexFromRight--;

    if (indexFromLeft < indexFromRight) {
      swap(a, indexFromLeft, indexFromRight);
      indexFromLeft++;
      indexFromRight--;
    }
    else done = true;
  }
  swap(a, pivotIndex, indexFromLeft);
  pivotIndex = indexFromLeft;

  return pivotIndex;
}

It doesn't seem to touch the first or last elements

sortFirstMiddleLast() sorts the first, middle, and last elements in-place. Once that's done, there's no need to consider the first or last value because (if the middle value is used as the pivot) they're known to be correctly partitioned.


Confusion in CLRS's version of Prim's algorithm The algorithm is as follows:

MST-PRIM(G,w,r)
1   for each u ∈ G.V   //initialization
2      u.key = ∞
3      u.π = NIL
4   r.key = 0
5   Q = G.V          //end initialization
6   while Q ≠ ∅
7      u = EXTRACT-MIN(Q)
8      for each v ∈ G.Adj[u]
9         if v ∈ Q and w(u,v) < v.key
10           v.π = u
11           v.key = w(u,v)

All vertices that are not in the tree reside in a min-priority queue Q based on a key attribute.
v.key is the minimum weight of any edge connecting v to a vertex in the tree
v.π points to the parent of v in the tree
G is a graph, w is a weight function, r is a root

The example given is as follows:

I am confused, why in step (c), edge $(b,c)$ is added instead of edge $(a,h)$. Below the diagram, there is a note saying:

  In second step, the algorithm has a choice of adding either edge $(b,c)$ or edge $(a,h)$ to the tree since both are light edges crossing the cut.

However still I think that according to the line 8 in algorithm, all adjacent vertices of $a$ not in the tree must be added first to the tree. Thus $h$ should also get added immediately after $b$, before $c$.
The line 8 says for **each v** ∈ G.Adj[u](i.e. for each adjacent vertex $v$ of $u$), why only adjacent node $b$ of $a$ is considered, but not $h$ (which is also adjacent to $a$).

If what author says should occur, then there should be something like break construct on line 12 inside the if construct's body, which will result in exiting for loop and hence grabbing next u = EXTRACT-MIN(Q).

Am I correct? or I must be missing something very stupid. What's that?

Question 1: However still I think that according to the line 8 in algorithm, all adjacent vertices of $a$ not in the tree must be added first to the tree. Thus $h$ should also get added immediately after $b$, before $c$.

You are confusing the resulting MST tree (denoted $T$) with the intermediate priority queue $Q$.

All the vertices are already in $Q$ at the end of initialization (Lines 1 ~ 5). However, $T = \emptyset$ at this time point.
A vertex $u$ is extracted from $Q$ and becomes a member of tree $T$ at line 7.
In the loop starting from Line 8, vertice $v$ satisfying the requirements of Line 9 are not inserted into the tree $T$; instead their keys in the priority queue $Q$ are changed (in fact, decreased).

  Question 2: "My point is when the line 8 says "for each adjacent vertex $v$ of $u$", why only adjacent node $b$ of $a$ is considered, but not $h$ (which is also adjacent to $a$)."

Yes, $h$ is also considered, but in the way different from what you describe. In the iteration for $a$, both $b$ and $h$ are considered (satisfying Line 8 and Line 9): their keys are updated (i.e., decreased) in the priority queue $Q$ (Line 11) and their parents are updated accordingly (Line 10). (Note that these updates are not finalized and may be updated again during the algorithm.)

The key point is: neither $b$ nor $h$ has been added into the resulting MST tree $T$. Vertex $b$ will be extracted from $Q$ and added into $T$ in the next iteration at Line 7 (shown in step (b)).

Also note that the figure in CLRS only shows the changes on $T$; it does not show the states of $Q$.


Prove/Disprove: Every two non-trivial NP-complete problems are decreasing reducible? We say that two languages $L_1,L_2$ are decreasing reducible if there exists a polynomial time reduction $f:\Sigma^*\to\Sigma^* $ and there exists $n\in\mathbb{N}$ such that for every $x\in\Sigma^*$ satisfying $|x|\ge n \implies |f(x)|\lt |x|$.

Assuming $P\ne NP$

  Prove\Disprove: Every two NP-complete languages $L_1,L_2$ are decreasing reducible.

I'd appreciate a hint or direction

Let $L$ be any NP-complete language, and consider what happens when $L_1 = L_2 = L$. Given an instance $x$, by applying $f$ a linear number of times we would get that $x \in L$ iff $y \in L$, where $|y| < n$. Since there are only finitely many strings of length smaller than $n$, we can hardcode the correct answer for these strings, thus obtaining a polynomial time algorithm for $L$.


Can someone explain why the MAX-CUT problem is in NP? Given an undirected graph $G = (V, E)$ and an integer $k$, is there a partition of the vertices into two (nonempty, nonoverlapping) subsets so that $k$ or more edges
have one end in each subset?

I'm a little confused on showing how the problem is NP, in terms of a certificate and certifier.

The certificate is a coloring of the vertices into red and blue (i.e., a partition into two sets). Given such a certificate, you can iterate through all the edges and count the number of edges whose endpoints have different colors. This count you can compare against $k$ and answer accordingly YES or NO.


A context-free grammar for a language of strings with occurrence properties? Creating a context-free grammar for the language

$L_1 = \{ 0^{n} 1 ^{m} \mid m,n \in \mathbb{N} \wedge  m \equiv n \mod 3\}$

is quite easy. A grammar is

$$ S \rightarrow \epsilon \mid 0A $$
$$    A \rightarrow 1 \mid 0B $$
$$    B \rightarrow 11 \mid 0S $$

But I am now trying to create a context-free grammar for

$L_2 = \{ w \in \{0 ,1 \}^{*} \mid |w|_1 \equiv |w|_0 \mod 3 \}$

Here, $|w|_1$ denotes the number of occurrences of the character $1$ in the string $w$, and $|w|_0$ is defined similarly.

How does one construct a context-free grammar? All my attempts have lead to completely wrong results. At the moment I am stuck.

Both $L_1$ and $L_2$ are regular languages. To construct a context-free grammar for them, you can first construct a DFA or NFA accepting them, and then convert it to a regular grammar.


Grammar with same variables If a grammar has the same variable multiple times, is it the same as adding a $\mid$ between them? For example, is

$$\begin{align*}S &\to bB  \\
S &\to \varepsilon  \\
B &\to cB  \\
B &\to \varepsilon  \end{align*}$$

equal to the following?

$$\begin{align*}S &\to bB \mid \varepsilon \\
B &\to cB \mid \varepsilon \\
\end{align*}$$

Yes. (you are right, the "$\mid$" sign is a classical notation for the alternative rules for a variable.)


Words which, cyclically shifted twice, equal their reverse Let the alphabet be $Σ = \{0, 1\}$. For any string $w ∈ Σ^*$ of length at least 2, define the
operation $C_2(w)$ to be a cyclic shift of size 2 on $w$. That is, if $w = w_1w_2 \cdots w_n$ with $n ≥ 2$ and each
$w_i ∈ Σ$, then $C_2(w) = w_3 \cdots w_nw_1w_2$ if n ≥ 3, and $C_2(w) = w$ if $n = 2$. Recall that $w^R$ means $w$
written backwards.

Give a context-free grammar that generates the following language:
$$ \{w \mid w \text{ has length at least 2 and } C_2(w) = w^R\}. $$

I'm having trouble constructing the context free grammar, so any tips would be much appreciated!

Let us see which words satisfy $C_2(w) = w^R$. Write $w = \sigma \tau x$, where $\sigma,\tau \in \Sigma$ and $x \in \Sigma^*$. Then $C_2(w) = x \sigma \tau$ and $w^R = x^R \tau \sigma$, and so $C_2(w) = w^R$ iff $x = x^R$ and $\sigma = \tau$.
You should be able to use this information in order to construct a grammar for your language.


Distance queries on Tree with hotspots We are given a tree with $n$ vertices and some of the vertices act as a "hotspot".

We have to answer multiple queries of type $(a,b,c)$, which means we have to find the distance to the nearest hotspot from $c$ such that we do not travel through the edge between nodes $a$ and $b$.

I have tried many data structures like using lowest common ancestor and algorithms like mo's algorithm on a tree, I have also tried to process queries which are closer to root first, but none of these have given me the desired complexity for each query which is anywhere between $O(1)$ to $O(\log n)$.

Is there any better algorithm or perhaps some clever precomputation(in less time than $O(n\log n)$ that can be used to solve this problem?

You can use the top-tree data structure.
It maintains a forest $F$ on $n$ nodes and supports (among others) each of the following operations in $O(\log n)$ time per operation:

Given an unmarked vertex $v$ mark $v$.
Given a marked vertex $v$ unmark $v$.
Given two vertices $u,v$ that belong to two different trees in $F$, add the edge $(u,v)$ to $F$ (thus merging two trees into one).
Given an edge $(u,v)$ of a tree in $F$, delete $(u,v)$ from $F$ (thus splitting the three into two).
Given a vertex $v$, report the distance to the marked vertex that belongs to the tree of $v$ and is closest to $v$.

This allows you to preprocess your tree in time $O(n \log n)$: build the forest $F$ on $n$ nodes by adding the edges of the tree one by one (so that, at the end, $F$ contains the input tree), then mark each hotspot.

To answer a query $(a,b,c)$ in time $O(\log n)$ proceed as follows:

Delete $(a,b)$ from $F$ in time $O(\log n)$.
Find the distance $d$ to the marked vertex that is closest to $c$. This takes $O(\log n)$ time and is exactly the answer to the query.
Re-add $(a,b)$ to $F$ in time $O(\log n)$.
Return $d$.


Derandomization of an approximation algorithm for solving a linear system I was given a HW assignment that asks me the following:

Given a system of $m$ linear equations in variables $x_1,x_2,...,x_n$ over $\mathbb{F_p}$, find a randomized algorithm that find an assignment for all the $x_i$ such that the expected number of equations solved are $m/p$. Then do a derandomization that gives an efficient deterministic algorithm that solves at least $m/p$ of the equations.

A randomized algorithm is easy - assign each variable a value uniformly from $\mathbb{F_p}$, by the principle of deferred decisions each equation is satisfied with a probability at least $1/p$, since there are $m$ equations and by the linearity of the expectation we get the desired result.

I am having difficulty with the second part, I wish to use the method of conditional expectation: choosing an assignment for the first variables then choosing an assignment to the next variable etc', and the expectation at each point is at least $m/p$ so that after $n$ iterations we have assigned all variables and the expected number of satisfied equations is the number of satisfied equations. I have seen this method used for derandomization of MAX-CUT.

My problems making adjustments:

Unlike MAX-CUT - I can only bound the expected number of solved equations by $m/p$ and not calculate the exact expectancy, this gives me problems when trying to figure out the next best assignment since I can't choose one that maximizes the  conditional expectancy
Unlike MAX-CUT - Choosing an assignment for some of the variables can determine the value of another variable (e.g choosing $x_1,x_2$ when we have $x_1+x_2+x_3=1$)

I have a suggestion, but I can't manage to prove it works: At iteration $k$ choose an assignment for  $x_k$ s.t the number of equations that are false is minimal (that is equations with one free variable that is not assigned a value contradicting the equality such as $x_j=t$ when we assigned $x_j$ a different value)

I would appreciate help analyzing my suggested algorithm or a point in the right direction

In your case the method of conditional expectations devolves to a greedy algorithm. At each stage, you choose the value for the variable under consideration that satisfies the most equations (if any; otherwise choose an arbitrary value), and substitute this value.

Why does this work? Suppose that at the beginning of stage $i$, you have $N_i$ remaining equations (i.e., ones in which there is at least one remaining variable with non-zero coefficient). The greedy choice satisfies at least $(N_i-N_{i+1})/p$ equations. In total, the number of equations you satisfy is at least
$$
\sum_{i=1}^n \frac{N_i-N_{i+1}}{p} = \frac{N_1 - N_{n+1}}{p} = \frac{N}{p},
$$
where $N$ is the total number of equations, and $N_{n+1} = 0$ is the number of remaining equations at the end of the algorithm.


Why do we have to trade abstraction for speed? Why can high-level languages seemingly never reach lower-level languages in terms of speed? Examples of high-level languages would be Python, Haskell, and Java. Low-level languages would be trickier to define, but let's say C. Comparisons can be found all around the Internet$^1$ and they all agree that C is a lot faster, sometimes by a factor of 10 or more.

What is it that causes such big difference in performance and why can't high-level languages catch up?

Initially I believed that this is all the compilers' fault and that things will improve in the future, but some of the most popular higher-level languages have been around for decades and they still lag behind when it comes to speed. Can't they simply compile to a similar to C syntax tree and then follow the same procedures that generate the machine code? Or perhaps it's something to do with the syntax itself?

$^1$ Examples:

The Computer Language Benchmarks Game
Julia's benchmark page

Debunking some myths

There is no such thing as a fast langauge. A language can generally produce fast code, but different languages will excel on different benchmarks. We can rank languages on a particular set of flawed benchmarks, but cannot rank languages in a vacuum.
C code tends to be faster because people who need every inch of performance use C. A statistic that C is faster "by a factor of 10" might be inaccurate, because it might be that the people using Python just don't care as much about speed and didn't write optimal Python code. We see this in particular with languages like Haskell. If you try really hard, you can write Haskell that performs on par with C. But most people don't need that performance, so we have a bunch of flawed comparisons.
Sometimes, it is unsafety, not abstraction, that makes C fast. Its lack of array-bounds and null-pointer checks save time, and have been the cause of numerous security holes throughout the years.
Languages aren't fast, implementations are fast. Many abstract languages start slow, because speed is not their goal, but get faster as more and more optimizations are added.

The abstraction vs speed tradeoff is perhaps inaccurate. I would suggest a better comparison:

Simplicity, speed, abstraction: Choose two.

If we're running identical algorithms in different languages, the question of speed comes down to the problem of "How much stuff do we need to do at runtime to make this work?"

In a highly abstract language that is simple, such as Python or JavaScript, because we don't know about the representation of data until runtime, there end up being lots of pointer de-referencing and dynamic checks happening at runtime, which are slow.

Likewise, there are a lot of checks that need to be done to ensure that you don't wreck your computer. When you call a function in python, it needs to make sure that the object you're calling actually is a function, since otherwise you could end up executing random code that does terrible things.

Finally, most abstract languages have overhead from garbage collection.
Most programmers have agreed that having to track the lifetimes of dynamically allocated memory is a pain, and they'd rather have a garbage collector do it for them at run time. This takes time, that a C program doesn't need to spend on GC.

Abstract Doesn't mean slow

However, there are languages which are both abstract and fast. The most dominant in this era is Rust. By introducing a borrow checker and a sophisticated type system, it allows for abstract code, and uses compile-time information to reduce the amount of work that we need to do at runtime (i.e. garbage collection).

Any statically typed language saves us time by reducing the number of runtime checks, and introduces complexity by requiring us to please a typechecker at compile-time. Similarly, if we have a language that encodes whether a value can be null into its type system, we can save time with compile time null-pointer checks.


Can we use a different encoding scheme to solve an unsolvable language? Say we have a particular decision problem and that we have an alphabet and an encoding scheme, which gives us a language L that we say is not recursive (i.e. we do not have a Turing Machine that can decide (YES or NO) the problem).

Is it possible to use a different encoding scheme to make the problem solvable?

I have thought about suggesting that we can reduce all such problems to the halting problem, which would imply that no new encoding will allow us to make one solvable (since this would contradict the unsolvability of the halting problem).

Ultimately, no.

First, remember that a language is, literally, a set of strings over some alphabet. There is no coding at this level: a string (a sequence of characters from the alphabet) is either in the language or it's not.  For example, the language of even-length strings over $\{0,1\}$ is what it is; if you change it at all, it's a different language.

However, you probably don't mean for your question to be interpreted so literally, and you're presumably asking about languages such as "the set of strings that encode Turing machines with property $X$."  Strictly speaking, the description of such a language should always say, "Fix an encoding scheme $f$ of Turing machines as strings. Now consider the language of strings $f(M)$ such that $M$ is a Turing machine with property $X$." After all, if you don't say what the encoding is, you can't know if a particular Turing machine is in the language or not. So, presumably, your question is "Well, what if I use some other encoding scheme, instead?"

As long as there's a computable translation between the two encoding schemes, changing the encoding can't alter the computability of the language.  To see this, fix any set $S$ of Turing machines and consider codings $f$ and $g$ of these machines as strings. Suppose there's a computable translation between $f$ and $g$, i.e., a computable function $t$ such that, for all $M$, $g(M) = t(f(M))$.  If the language $L_g = \{g(M)\mid M\in S\}$ is decidable, then we can decide $L_f = \{f(M)\mid M\in S\}$, too.  To decide whether $w\in L_f$, just ask if $t(w)\in L_g$.  The reason people tend to be quite informal and just talk about "the language of Turing machines with some property" is precisely this: it doesn't matter what encoding you use, as long as you stick to encodings you can computably translate to the "standard" encoding, whatever reasonable encoding you want to view as standard.

In a strong sense, it's impossible to use any other encoding. For example, consider an encoding $f$ that isn't computably translatable to some standard encoding. Now, suppose I describe a Turing machine to you by listing the symbols in the alphabet, the states, the transition function and so on. You can't even compute $f(M)$, so you can't do anything useful with that encoding.

There are even encodings that make the halting problem decidable but they're a trick: they're not computable, so you can't actually use them.  For example, fix a computable encoding $g$.  Now, define $f(M)$ (uncomputably) as follows. If $M$ halts when started with a blank tape, let $f(M)$ be $2n$ written in binary, where $n$ is the number of Turing machines $M'$ such that $M'$ halts when started with a blank tape and $g(M')$ lexicographically precedes $g(M)$. Otherwise, let $f(M)$ be $2n+1$, where $n$ is the number of Turing machines $M'$ that do not halt when started with a blank tape and whose encoding $g(M')$ lexicographically precedes $g(M')$.  Now, the language $\{f(M)\mid M \text{ halts when started with a blank tape}\}$ is decidable: it's just the set of even numbers in binary.  But, as I said, this is a trick: it doesn't really let you decide the halting problem because, again, you can't compute $f(M)$ given a description of $M$.  (In particular, you can't even tell if $f(M)$ is even or odd.)


What is the sqrt(n)-approximation algorithm for set packing problem The set packing problem is :
Given a universe $U$ and a family $S$ of subsets of $U$, a packing is a subfamily $C\subseteq S$ of sets such that all sets in $C$ are pairwise disjoint, and the size of the packing is $|C|$. The goal is to find the $C$ where $|C|$ is maximum.

According to Wikipedia, there exists a $\sqrt{|U|}$-approximation algorithm for this problem. But it doesn't give a way to approach that, it seems that the way cannot be found on google as well.

See Viggo Kann's page on set packing. Viggo mentions two $\sqrt{|U|}$ algorithms:

Unweighted case: Halldórsson, M. M., Kratochvíl, J., and Telle, J. A. (1998),
"Independent sets with domination constraints",
Proc. 25th Int. Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 1443, Springer-Verlag, 176-185.
Weighted case: Halldórsson, M. M. (1999a),
"Approximations of weighted independent set and hereditary subset problems",
Proc. 5th Ann. Int. Conf. on Computing and Combinatorics, Lecture Notes in Comput. Sci., Springer-Verlag, 261-270.

I found this link on the first page of the Google search set packing approximation algorithm. I suggest that next time you spend some quality time with your favorite search engine, looking at all links in the first few pages.


Is $\{ 0^p1^q0^r \mid p \neq r \}$ context-free? Consider the following languages:
$$ \begin{align*} L_1 &= \{ 0^p 1^q 0^r \mid p,q,r \ge 0 \}, \\ L_2 &= \{ 0^p 1^q 0^r \mid p,q,r \ge 0, \; p \neq r \}. \end{align*} $$
Which one of the following statements is false?
A. $L_2$ is context-free.
B. $L_1 \cap L_2$ is context-free.
C. $\overline{L_2}$ is recursive.
D. $\overline{L_1}$ is context-free but not regular.

Doesn't the following show that $L_2$ is context-free, and so option A should be false as well?
Assume $L_2$ is context-free.
Consider the string $w = 0100 \in L_2$.
Breaking $w$ into $w= uvxyz$, where $u = \epsilon$, $v = 0$, $x = 1$, $y = \epsilon$, $z = 00$, according to the pumping lemma (with $p=r=2$), $uv^2xy^2z = 00100 \in L_2$, which is false.

The mistake in your proof is that the pumping lemma says that such a division (w=uvxyz) exists.
So in order to say $L_2$ is not context free, you have to show that for every division, you get a contradiction.

In your example we can use this division:
$u=01, \, v=00, \, x=\epsilon, \, y=\epsilon , z=\epsilon$
So for every $n \geq 0$:
$uv^nxy^nz=01(00)^n \in L_2$


Controlling overflow and loss of precision during floating point multiplication I have a large number of floating point numbers (~10,000 numbers) , each having 6 digits after decimal. Now, the multiplication of all these numbers would yield about 60,000 digits. But the double range is for 15 digits only. How can I get my product with minimum loss in precision?

I thought of storing the numbers as 6 digit long long integers and storing their exponents elsewhere. But this appears cumbersome and may not yield correct result. Is there an alternate easier way to do this?

Multiplication of floating point numbers is considered uncritical with respect to accuracy. If your input is only accurate to 6 digits, there is no point in computing the output to 60,000 digits. The expected relative error after 10,000 multiplications is $\sqrt{10,000}\epsilon=100\epsilon$ with $\epsilon<10^{-14}$ for double precision. This is more than enough precision for your case.

Overflow and underflow on the other hand can indeed happen during multiplication. In practice, I would prefer to work with numbers in a range where I know that this won't happen. However, this may not always be possible. One can use frexp to split floating-point numbers into significant and exponent, multiply the significants separately and add the exponents together, and use ldexp for putting the result back together. However, doing this naively by applying frexp for every number and multiplying all 10,000 significants together at once would be a bad idea, because it would be slow and nearly guarantee underflow. But if done intelligently (appropriate grouping), it will yield the correct result, and the speed difference will be almost unnoticeable.


Conditionals with normal order evaluation From what I've read, conditionals (like the cond statement in lisp) do not need to be primitive if normal order evaluation is used.

Using lambda calculus and normal order evaluation, how can you emulate if and cond statements?

(cond (<p1> <e1>)
      (<p2> <e2>)
      ...
      (<pn> <en>))

(if <predicate> <consequent> <alternative>)

References to SICP are welcome, though a simpler example would be helpful.

(Definitions of cond and if taken from Section 1.1.6 of SICP)

Here is the church notation:

TRUE: $\lambda ab.a$

FALSE: $\lambda ab.b$

IF: $\lambda pxy.pxy$

By passing a church boolean as a predicate to the IF function, we choose one of two alternatives. TRUE chooses the first argument passed to it, and FALSE chooses the second.

We can derive COND by folding IF across a list of (condition, result) pairs

You can find wikipedia's explanation here, as well as assorted lambda calculus derivations here.


Maximum matching in a bipartite graph Given a bipartite graph $G=(V_1 \cup V_2, E)$ and a set $V' \in (V_1 \cup V_2)$. What is the complexity of finding a maximum matching in $G$ that uses only $x$ vertices from $V'$?

Set $V_i' = V_i \cap V'$. You can solve this by finding the maximum matching using at most $k$ vertices from $V_1'$ and at most $x-k$ from $V_2'$ for all $k \in [0, x]$. This in turn can be found with maximum flow.

To find this maximum matching, we modify the usual reduction to maximum flow. Let $s$ be the source and $t$ the sink. Let $l$ and $r$ be auxiliary vertices. Add an edge from $s$ to $l$ with capacity $k$, and an edge from $r$ to $t$ with capacity $x-k$. All other edges will have capacity $1$. Add an edge from $l$ to every $x \in V_1'$, and from $s$ to every $x \in V_1 \setminus V_1'$. Add an edge from every $y \in V_2'$ to $r$, and from every $y \in V_2 \setminus V_2'$ to $t$. For $(x, y) \in E$, add an edge from $x$ to $y$. Now the maximum flow gives a maximum matching using at most $k$ vertices in $V_1'$ and $x-k$ in $V_2'$.

We can thus solve the problem in $\mathcal{O}(x \cdot M)$ where $M$ is the complexity of maximum flow. The maximum flow problems are very similar, so we can improve on this.

We can increase or decrease the capacity of any edge by $1$ while maintaining the maximum flow in $\mathcal{O}(|E|)$. First calculate the maximum matching using no vertices in $V'$. Then, increase the capacity of the edge from $s$ to $l$ by $x$. Then at every step increase the capacity of the edge from $r$ to $t$ and decrease the capacity of the edge from $s$ to $l$ while maintaining a maximum flow. Output the largest matching produced. The complexity will be $\mathcal{O}(|E| \sqrt{|V|} + x \cdot |E|)$ if we use Dinic to find the initial bipartite matching.


simulation of PDA with 2-tape Turing machine Can someone give me suggestions how can I construct a 2-tape Turing machine which simulates PDA ?

The first tape for input and the second for storing symbols (like on a stack). The first tape should be read-only so that the TM reads symbols one by one from left to right.

Every time your PDA writes a symbol on the stack, your TM moves the second head right and writes a symbol on the rightmost empty cell. When the PDA removes a symbol from the stack the TM replaces the rightmost symbol with the blank symbol (erases) and moves the second head left. On each state transition the first head should always move right.

In addition, your TM shouldn't be allowed to arbitrarily move heads right and left violating PDA rules.

Consider the following formal definition of moves for PDA (assume deterministic for simplicity):

UPDATE

Definition of PDA moves

$\delta(q, a, Z) = (p, \alpha)$: the PDA in state $q$ with input $a$ and $Z$ on the top of the stack. The PDA enters the state $p$ and replaces the top symbol $Z$ with the symbols of the string $\alpha$. So, $\delta(q, a, Z) = (p, \epsilon)$ means remove the top stack symbol (pop). Advance the input head one symbol.

$\delta(q,\epsilon, Z) = (p, \alpha)$: the PDA in state $q$ with $Z$ on the top of the stack. Independent of the input symbol, PDA enters the state $p$ and replaces the top symbol $Z$ with the symbols of the strings $\alpha$. Input head does not advance in this case.

Examples of translation of PDA moves into TM moves

Example 1.
PDA move $\delta(q_1, 0, A) = (q_2, B)$ is translated as: TM in state $q_1$, head 1 (input head on the tape 1) reads $0$, and head 2 (stack head on the tape 2) reads $A$. Replace $A$ with $B$ (head 2 writes the symbol $B$ while it is on $A$). Advance head 1 one symbol. Enter state $q_2$.

Example 2.
$\delta(q_1, 0, A) = (q_2, BC)$ is translated as: TM in state $q_1$, head 1 reads $0$, and head 2 reads $A$. Head 2 writes $B$ (replaces $A$), advances head 2 one symbol, TM enters state $q_{21}$. Then, while TM in state $q_{21}$ and head 1 reads $0$, and head 2 reads the blank symbol: head 2 writes symbol $C$, enters state $q_2$. Advance head 1 one symbol.

The basic idea: in order to write $BC$ we introduced a new state $q_{21}$.

Analogously, $\delta(q,\epsilon, Z) = (p, \alpha)$ means head 2 just writes the blank symbol and moves left.

$\delta(q,\epsilon, Z) = (p, \alpha)$ means that you define the same transition for every input symbol.

This is how a multitape Turing machine is defined.


Is my decomposition of R into 3NF is lossless and preserving all dependencies? I have a schema R = {A,B,C,D,E} and the set F of FDs:

F = {A --> BCDE, CD --> E, EC --> B}.

Candidate key = A
Non - Prime Attributes = BCDE
Prime Attributes = A

According to me, there is no partial dependency because no non-prime attribute is dependent on part of CK.

E and B are transitively dependent on A so the schema Ris not in 3NF.

Decomposing R into 3NF, I have three relations and three set of FDs :

R1(A,B,C,D)                         F1={A --> B,A --> C,A --> D}
R2(C,D,E)                           F2={CD --> E}
R3(E,C,B)                           F3={EC --> B}

My question is, Is my decomposition of R into 3NF is lossless and preserving all dependencies or not? And if not how can I decompose it into 3NF losslessly while preserving all dependencies.

So My decomposition is lossless and preserving all dependencies but there is no need for relation R3(E, C, B) because we already have A which can derive B in R1.