How to simulate a parallel computer (with certain number of processors) on a serial computer I am a novice to parallel computing. I would like to solve the traveling salesman problem (TSP) using a parallel genetic algorithm (GA). I need to write a simulator of a parallel computer (for example, a multicore workstation) that will implement the parallel version of the GA. But the simulator should run on a serial processor. I know the basics of GAs and I know how to design a GA algorithm to solve the TSP. I thought that this could be an example of an "embarassingly parallel" problem in the sense that I could assign each processor a fixed number of chromosomes (i. e, potential solutions, with solution meaning a given sequence of cities to be visited as specified by the chromosome) with the task of calculating the objective function for each of the assigned chromosomes. In this case, the objective function for a given chromosome is the inverse of the total distance described by that chromosome. The task of performing crossover and mutation would be carried out by a master processor. If this is a valid or reasonable way of parallelizing the problem, then there's no need for inter-processor communication during the objective function evaluation step and I can hardly see this as a truly parallel problem. Since minimum communication is needed, wouldn't the speed scale with the number of processors? What would we learn from such a simulation that we don't already know? I'll be grateful for any thoughtful answers.

The Traveling Salesman Problem (TSP) is a classic problem because it's hard to deterministically solve in a decent time frame, classified as NP-hard.  Genetic algorithms can get a good solution more quickly than NP-hard time, but there's no guarantee that you'll find an actual optimal solution.  This can be a good trade-off if you're programming, say, a driving-direction app, but it doesn't get around the NP-hard issue since it doesn't reliably solve the actual NP-hard problem.

Note that genetic algorithms are stochastic (probabilistic).  It's entirely possible that you could guess the exact best solution on the first go, or that you'd never guess it after a billion years.

  I would like to solve the traveling salesman problem (TSP) using a parallel genetic algorithm (GA). I need to write a simulator of a parallel computer (for example, a multicore workstation) that will implement the parallel version of the GA. But the simulator should run on a serial processor.

As others have said, this will cause your program to run slower than if you hadn't split it up.  Parallel solution techniques are inefficient compared to single-threaded solution techniques; the only reason that we use them is to leverage additional processors.  If you don't actually take advantage of additional processors, you pay the cost for it without enjoying the benefit.

That said, almost all modern computers have multiple cores, even cell phones and tablets.  In the paragraph above, "processor" refers to a processing unit, which single CPU's have multiple instances of.  Your computer probably has at least 2 if it's a laptop or 4 if it's a desktop.

Also, note that processors often claim to have twice as many "logical cores".  When doing numerical problems, you mostly just care about physical cores; ignore the additional logical cores.  With Intel processors, this means ignore Hyper-Threading.  With AMD processors, this often means dividing their claimed count by two, since I think that they share floating-point units (FPU) between cores.  Those extra logical cores are useful in common computer tasks where there are thread waits and such, but they're usually harmful in scientific computing.

  Since minimum communication is needed, wouldn't the speed scale with the number of processors?

Ideally, if you get 100% parallelization efficiency, total speed is equal to the speed of each of the individual processors working individually, combined.  Lots of things detract from that ideal, including communication time.

As much as possible, you want to split the problem up into large chunks that a processor can focus on, then combine those chunks at the end, or at least infrequently.

Too much communication will actually make a bunch of processors working together slower than a single one working alone.  For example, consider

return a + b + c + d;  // Single-threaded calculation

If you split this up into

half1 = worker1.Add(a, b);
half2 = worker2.Add(c, d);
return half1 + half2;

, your program will run much slower than in the first case, despite using multiple cores.  The problem is even calling other threads costs far more than simply adding the numbers together, so you've slowed the program down by a huge factor as soon as you do the first worker call.

The trick to remember is that you want to call workers only when you have a lot of work for them to do while the current thread does a lot of work itself.  If that doesn't hold, then it's more efficient to just do the work in the current thread.

  What would we learn from such a simulation that we don't already know?

Nothing, really.  This is a common homework problem in many college classes on optimization, so it's been done hundreds of thousands of times before.  I'm assuming that this is part of one of your homework problem sets.

Conclusion

If you're in college, you may have access to a good version of Visual Studio through Microsoft Imagine (previously called DreamSpark).  If not, you can download Visual Studio 2015 Community (noting that 2017's in RC right now).

If you use C# in Visual Studio, it should be pretty straightforward to create your parallel genetic algorithm optimizer for the traveling salesman problem.  Since your PC's probably already multi-core, you can take advantage of the speed up from it.  But, even if it's not multi-core, you can still do multi-threaded runs, and the OS will interleave the threads to simulate a multi-core process.

At the following paper [1] they are talking about some cloud simulators, and comparing them with a Raspberry Pi cluster. Basically they are saying that a Raspberry Pi cluster is the cheapest way to have a system with more than 1 CPU. They also saying that cloud simulators are not reflecting to the real network traffic.

So, regarding your question, even if you have a simulator you will not even get close to a cluster machine.

I would suggest you at first, to try threaded parallelism, and if you believe that is worth it, you can buy time at a bigger machine, and work with process parallelism. You can also try process parallelism on multi-core CPUs and then move to a bigger machine.

[1] Fung P.T., White D.R., Jouet S., Singer J., Pezaros D.P., "The Glasgow Raspberry Pi Cloud: A Scale Model for Cloud Computing Infrastructures," icdcsw, pp.108-112, 2013 IEEE 33rd International Conference on Distributed Computing Systems Workshops (ICDCSW), 2013

PS: Can you post the algorithm your going to use?


What exactly (and precisely) is "hash?" I have heard the word "hash" being used in different contexts (all within the world of computing) with different meanings. For example, in the book Learn Python the Hard Way, in the chapter on dictionaries it is said "Python calls them "dicts." Other languages call them "hashes."" So, are hashes dictionaries?

The other common usage of the word is in relation to encryption. I have also heard (& read) people using the word "hash" as a specific function within high-level programing.

So, what exactly is it?

Can anyone (with time and who is knowledgeable) kindly explain the nitty-gritties of "hash (or hashes)?"

The Wikipedia article on hash functions is very good,
but I will here give my take.

What is a hash?
"Hash" is really a broad term
with different formal meanings in different contexts.
There is not a single perfect answer to your question.
I will explain the general underlying concept and
mention some of the most common usages of the term.
A "hash" is a function $h$ referred to as hash function
that takes as input objects and outputs a string or number.
The input objects are usually members of basic data types like
strings, integers, or
bigger ones composed of other objects like user defined structures.
The output is a typically a number or a string.
The noun "hash" often refers to this output.
The verb "hash" often means "apply a hash function".
The main properties that a hash function should have are:

It should be easy to compute and
The outputs should be relatively small.

Example:
Say we want to hash numbers in the range from 0 to 999,999,999 to
number between 0 and 99.
One simple hash function can be $h(x) = x \mod 100$.
Common additional properties:
Depending on use case we might want the hash function to
satisfy additional properties.
Here are some common additional properties:

Uniformity:
Often we want the hashes of objects to be distinct.
Moreover we may want the hashes to be "spreading-out".
If I want to hash some objects down into 100 buckets
(so the output of my hash function is a number from 0-99),
then I am usually hoping that about 1/100 objects land in bucket 0,
about 1/100 land in bucket 1, and so on.

Cryptographic collision resistance:
Sometimes this is taken even farther,
for instance, in cryptography
I may want a hash function such that
it is computationally difficult for an adversary
to find two different inputs that map to the same output.

Compression:
I often want to hash arbitrarily-large inputs down into
a constant-size output or fixed number of buckets.

Determinism:
I may want a hash function whose output doesn't change between runs,
i.e. the output of the hash function on the same object will always remain the same.
This may seem to conflict with uniformity above, but
one solution is to choose the hash function randomly once,
and not change it between runs.

Some applications
One common application is in data structures such as a hash table,
which are a way to implement dictionaries.
Here, you allocate some memory, say, 100 "buckets";
then, when asked to store an (key, value) pair in the dictionary,
you hash the key into a number 0-99, and
store the pair in the corresponding bucket in memory.
Then, when you are asked to look up a key,
you hash the key into a number 0-99 with the same hash function and
check that bucket to see if that key is in there.
If so, you return its value.
Note that you could also implement dictionaries in other ways,
such as with a binary search tree (if your objects are comparable).
Another practical application is checksums,
which are ways to check that two files are the same
(for example, the file was not corrupted from its previous version).
Because hash functions are very unlikely to map two inputs to the same output, you compute and store a hash of the first file,
usually represented as a string.
This hash is very small, maybe only a few dozen ASCII characters.
Then, when you get the second file,
you hash that and check that the output is the same.
If so, almost certainly it is the exact same file byte-for-byte.
Another application is in cryptography,
where these hashes should be hard to "invert" --
that is, given the output and the hash function,
it should be computationally hard to figure out the input(s)
that led to that output.
One use of this is for passwords:
Instead of storing the password itself,
you store a cryptographic hash of the password
(maybe with some other ingredients).
Then, when a user enters a password,
you compute its hash and check that it matches the correct hash;
if so, you say the password is correct.
(Now even someone who can look and find out the hash saved on
the server does not have such an easy time pretending to be the user.)
This application can be a case where
the output is just as long or longer than the input,
since the input is so short.

I'll try just to add a short summary of what others say.

Hash function

There is a special kind of functions called hash functions.

"SHA256 is a well-known hash function that is cryptographically secure"

Three main applications are
* hash tables,
* checksums (data integrity checks e.g. in hard drives or ADSL protocols),
* and cryptography (various forms of cryptographic authentication including but not limited to digital signatures and secure password storage).

Hash table

Hash table is a data structure for fast search. It uses hash functions internally, hence the name.

"Databases use hash tables and search trees internally to speed up execution of search requests"

Hash

a dictionary abstract data type

"Hash" is the official name of built-in dictionaries in Perl.  They are hash tables internally, hence the name. "This subroutine accept a hash as its first argument". These days can be used for any associative array, not necessarily a hash table.

result of applying a hash function to some input

"MD5 hashes of the .iso images are provided to check their integrity after downloading".


Shortest path with a given condition The problem says to find the shortest way (the smallest amount of intermediary points), with given source and destination points, such that between two consecutive intermediary points there are two alternative routes. Also, all the
connections between the points on the map are given.

I understood that the problem is about a graph with given edges and that i have to find the shortest path between two given nodes, but i didn't understand how to search the right path with the given condition (2 alternative paths between every two intermediary nodes).
Is the BFS algorithm applicable in this case? And wich other algorithm could I also use?

Thanks in advance for help!

First let's look at the special condition.
For each edge $p_i p_{i+1}$ in the path $P$ the has to exists an additional path that connects $p_i$ with $p_{i+1}$. This criterion is equivalent to: no edge of the path is a bridge edge.

This means that we can determine already before the actual shortest path search, which edges we are allowed to use, and which edges we are not allowed to use.

Therefore you can construct an efficient algorithms as follows:

compute all bridge edges (e.g. with Tarjan's bridge-finding algorithm)
remove all bridge edges from the graph
execute any shortest path algorithm, e.g. BFS, on the remaining graph

Some additional notes, since you wrote that you want to use multiple algorithms. However these approaches will perform a lot worse than the one described above.

of course you can also determine if an edge $p_i p_{i+1}$ is a bridge edge in other ways. E.g. remove the edge from the graph, and check if you can find a path from $p_i$ to $p_{i+1}$ with a DFS (backtracking), or with another BFS.
Also you can use Backtracking itself to find the shortest path at the end.

BFS is for tree traversal just like DFS. For the shortest path algorithms that textbook commonly used are:

Bellman Ford's Algorithm
Dijkstra's Algorithm


How to solve recurrence. T(n). = T(n-1) + T(n/2) + n? I am aware that to get a running time by recursion tree method, we need to draw a tree and find:

a) number of levels in tree.

Since left side of tree decreases by 1 in size, so it's longest path from root. Subproblem size at level i is n-i . setting n - i = 1 when it hits a size of 1, we get number of levels, i  = n - 1.

b) cost per node in tree : cn

c) Number of nodes at level i:   This is where i am stuck. Not able to find nodes at level i since left side decreases by 1, right side by half. Naturally,  tree is more dense towards left side.  Not every node will have two children.

if i can get answer to c, i can calculate T(n) = cost of level 0 + cost of level 1 + cost of level 2 +  ... cost of level n-1.
if y1 is number of nodes at level 1, y2 at level 2, etc... then
=> T(n) = cn + y1 * cn + y2 * cn + y3 * cn + .... yn-1 * cn  to get total cost.

Can anyone guide me to the approach i am taking ? is it correct ?
can i take an assumption that for sufficiently large n,  we can ignore T(n/2) and then proceed  ? .

Online searching confused me. Problem is 4.4-5 from CLRS.

Please see here

This solution says T(n) = O(2^n) and T(n) = omega(n^2) and does not explain how.

Also see here

This solution says T(n) = O(n^2).  but contradicts with above solution

Let $S(n) = T(n) - 2n - 2$. You can check that $S(n) = S(n-1) + S(n/2)$ (ignoring the fact that $n/2$ need not be an integer). This shows that the additive $n$ term doesn't make a big difference.

For large $n$, we have roughly $S(n) - S(n-1) \approx S'(n)$, and so we are led to solve the differential equation
$$
S'(n) = S(n/2).
$$
Consider $f(n) = \exp (\tfrac{1}{2}\log_2^2 n)$. Then
$$
f'(n) = \exp (\tfrac{1}{2}\log_2^2 n) \cdot \frac{\ln n}{(\ln 4)n},
$$
whereas
$$
f(n/2) = \exp(\tfrac{1}{2} (\log_2 n - 1)^2) \approx \exp(\tfrac{1}{2}\log^2 n) \exp(-\log n) = \exp(\tfrac{1}{2} \log^2 n) \cdot \frac{1}{n}.
$$
This suggests that, at the very least, $\ln S(n) = \Theta(\log^2 n)$.

Where does this come from? You can think of $S(n)$ (with an appropriate base case!) as the number of ways to go from $n$ to zero by applying two operations: subtract 1 and divide by 2. A "typical" such sequence will contain roughly $\log_2n$ many operations of the second type, out of $\Theta(n)$ operations in total, leading to the very rough estimate $\binom{\Theta(n)}{\log_2 n}$, which is also of the form $\exp \Theta(\log^2 n)$.

Consider for concreteness the following precise definition of $S(n)$: the base case is $S(0) = 1$, and for $n > 0$,
$$
S(n) = S(n-1) + S(\lfloor n/2 \rfloor).
$$
This is sequence A000123. Knuth, An almost linear recurrence, showed that
$$
\log_4 S(n) \sim \log_4^2 n,
$$
that is, the ratio of the two terms tends to 1 as $n \to \infty$. The OEIS entry contains even more precise asymptotics.

I disagree with the Fibonacci hypnosis, but I'm not hundred percent sure of my answer

You see
$ T(n)= T(n-1) +c*n = O(n ^2) $

$ T(n) = T(n/2) + c*n =O(n log n) $

However, u don't get ur T(n) by straightforward adding.

If u go one level in the recursion (u can draw a tree)

T(n) =T(n-2) +T((n-1)/2) +T(n/2-1)+ T(n/4)
+ [n + (n-1) + (n-1)/2 + (n/2-1) +n/4]

This to show u it is also not just
      $ O(n^2) $

I have to complete it, but I suspect either $ O((n^2) * log n) $
 or
   $ O((n^2) * n ^ {log n} ) = O(n^3) $

{There is a term n(1+1/2+1/4+..1/n) that decays in log n steps, I have to check again}


Are there pseudorandom number generators (PRNG) with no finite period? The typical and widely used PRNG, the linear congruential generator always has a finite (though possibly "long") period. Are there PRNGs that have no finite period?

For this question it is not necessary that it be practical or used in real-world implementations.

If the state of the PRNG is finite, then it has a finite period.  (By finite, I mean the same as we mean when we say that a finite-state automaton is finite: the set of all possible states is finite.  For instance, if the state always fits into $b$ bits, for some fixed value of $b$, then its state is finite.)

In practice, worrying about the period of the PRNG may be akin to arguing over angels on a pinhead.  A 256-bit state is large enough that a well-designed PRNG will never repeat within the lifetime of the universe.  Therefore, concerns about repetition are pretty much irrelevant for any reasonable, well-designed PRNG.

In practice, the real challenge is to make the PRNG unpredictable (or close enough for the application's purposes); ensuring it won't repeat is much easier, relatively speaking.

To try and answer your question as posed, one possible way to build a PRNG with "no period" would be to have a generator that re-seeds itself periodically by using a subroutine that stores randomly selected output bits and then uses this block of bits as a "new seed" for the generator. So any given seed is only used for a period much smaller than its mathematical potential . So technically the output string is a concatenation of an endless series of generators with "small seeds" that goes on forever. The notion of a period, like the period of a shift register sequence, only has meaning if you assume a fixed seed for the register. If the seed is constantly changing, the notion of a "period" becomes meaningless no matter what the length of the shift register is.


Can two neighbors in a graph be at the same depth in a DFS tree? In an undirected graph, can two nodes at an identical distance n from the root of a DFS tree be neighbors in the original graph? I'm thinking no, but I'm not sure (because of back edges)

I think you are correct:

All neighbors of a node will be of rank one less (the node we got here from) or one more (or two more, etc) because we will rank them before we back out of the node.

Your question does not stipulate how the DFS tree is generated.  Naive implementations simply list nodes in the order they are visited, but most practical implementations rebuild the output tree as the search progresses and the ranks of the nodes are adjusted.

Consider three nodes, A B C, connected to each other.  A naive DFS will visit A B C, with ranks of 0 1 2, and the tree will have a back edge from C to A.  A more useful implementation will backtrack from C to B to A, and then from A will travel to C again and assign it a rank of 1, then decline to travel to B at rank 2 because B is already rank 1, this tree will have both B and C at rank 1 below A, with a cross edge between B and C.


CPU and GPU differences What is the difference between a single processing unit of CPU and single processing unit of GPU?
Most places I've come along on the internet cover the high level differences between the two. I want to know what instructions can each perform and how fast are they and how are these processing units integrated in the compete architecture?
It seems like a question with a long answer. So lots of links are fine.

In the CPU, the FPU runs real number operations. How fast are the same operations being done in each GPU core? If fast then why is it fast?
I know my question is very generic but my goal is to have such questions answered.

This are not Real numbers as $\mathbb{R}$, but at this point - CPU has double precision floating point numbers, GPU very low number of units processing them, floats on GPU are halfs.
This is due to graphics (this was the main goal before parallel processing), where results are rounded to display, so speed vs accuracy tradeof went that way.
GPU core frequencies are smaller than CPUs, number of operations is very limited on GPU (boosted by video decoder), and there is a huge difference in branch prediction - CPU has very long and complex prediction, while GPU just recently got it added.

Single core on GPU: it is Streaming Multiprocessor (there are about 4 - 16 per card), it includes cuda cores (which is about 32-64), and they work in lock-step, so it differs from CPU threads (not locked).

It is hard to compare like this, but in short - single core on GPU is still parallel unit working slower than CPU core, less memory, registers and instructions than CPU, with very short branching prediction and preferable half floats, nowadays normal floats but having about one-two processing units for double precision, some time ago integer operations were slower on GPU (not onlu by frequency) - but this changed recently.

The same operation on floats - they are slower on GPU than CPU due to frequency.

You might be interested in AMD architecture, Nvidia architecture and Intel architecture to compare instructions set and hardware differences further.

To be simpler with the words CPU (central processing unit- a purpose processor) has always been called the brains of the PC. But nowadays, that brain is being improvised by another part of the computer i.e the GPU (graphics processing unit).

Basically GPU's advanced features were only used in 3D and high end gaming. But these days GPU plays a vital role more importantly in speeding up computational workloads. Read more at NVIDIA CEO Jen-Hsun Huang’s latest blog post for more deeper knowledge of GPU.

CPU: it contains fewer number of cores with a lot of cache memory and can handle few threads at a time.
whereas GPU has power to handle thousands of threads.A CPU generally has higher operating frequency and is designed for general purpose use and vice versa with GPU.But the combination of both the features will contribute to better performance and efficiency.


Merge two sorted arrays without using additional memory We have two sorted arrays of integers.
Without using additional memory we need to merge these two arrays such that the smallest numbers are in the 1st array and the remaining numbers are in the second array.

For instance, if your two arrays are $A=[1,3,9,14]$ and $B=[2,4,15]$, the result should be $A=[1,2,3,4], B=[9,14,15]$. Entries are integers, and you can use only $O(1)$ extra memory for auxiliary variables.

Here, great solution, from: http://www.geeksforgeeks.org/merge-two-sorted-arrays-o1-extra-space/

Below is C++ implementation of above algorithm.

// C++ program for implementation of Sieve of Atkin
#include <bits/stdc++.h>
using namespace std;

// Merge ar1[] and ar2[] with O(1) extra space
void merge(int ar1[], int ar2[], int m, int n)
{
    // Iterate through all elements of ar2[] starting from
    // the last element
    for (int i=n-1; i>=0; i--)
    {
        /* Find the smallest element greater than ar2[i]. Move all
           elements one position ahead till the smallest greater
           element is not found */
        int j, last = ar1[m-1];
        for (j=m-1; j >= 0 && ar1[j] > ar2[i]; j--)
            ar1[j+1] = ar1[j];

        // If there was a greater element
        if (j != m-1)
        {
            ar1[j+1] = ar2[i];
            ar2[i] = last;
        }
    }
}


Showing $2^x$ is a lower bound How do I show that $2^x - x^2 \in \Omega(2^x)$?

Basically, I know that this means that $\exists a, x_0 \in \mathbb{R^+}, \forall x \in \mathbb{N}, a.2^x \leq 2^x - x^2$.

I worked around a bit with this and I seemed to have gotten something that makes sense for the case of an upper bound;
$$2^x -x^2 < 2^x + x^2 < 2^{x+1} = 2.2^n $$
Now, if I were trying to find an upper bound, I'd have chosen $a = 2$ and $x_0 = 1$. How do I work the other way around(basically less than or equal to $2^x - x^2$ and prove this lower bound?

Here is the hint or outline of a proof.

Show that by mathematical induction, that $2x^2< 2^x$ for $x>7$.
Show that $\dfrac12\cdot2^x< 2^x-x^2$ for $x>7$


Closure of Deterministic context-free languages under prefix For a formal language $L \subseteq \Sigma^{*}$ I define the set Pref(L) to be:

$\text{pref}(L) = \{\alpha \in \Sigma^{*} : \exists \beta \in \Sigma^{*} \text{ such that } \alpha \beta \in L\}$

ie. the set of all (not necessarily proper) prefixes of words in $L$. I know that if $L$ is context-free then pref(L) is context-free but if $L$ is deterministic context-free then is pref(L) deterministic context-free?

I am sure this is known but I cannot find the answer anywhere and it's not in Hopcroft and Ullman.

DCFL are known to be closed under quotient with regular languages, but the quotient of $L$ with $\Sigma^{*}$ is precisely $\text{pref}(L)$ so yes, if $L$ is a DCFL then $\text{pref}(L)$ is a DCFL.

According the concept of context free language very context can be represented in the form of "CHOMSKY NORMAL FORM".so if in the rule we made change like
if
A->BC
change it to the
A->BC/B
now this type of replacement will generate the context free language of prefix language of the given


Algorithm challenge: build a pile of 'n' cubes whose total volume adds up to 'm' I'm working on solving an algorithm problem defined as follows (important parts in bold):

  Your task is to construct a building which will be a pile of n cubes. The cube at the bottom will have a volume of n^3, the cube above will have volume of (n-1)^3 and so on until the top which will have a volume of 1^3.

  You are given the total volume m of the building. Being given m can you find the number n of cubes you will have to build?

  The parameter of the function findNb will be an integer m and you have to return the integer n such as n^3 + (n-1)^3 + ... + 1^3 = m if such a n exists or -1 if there is no such n.

Okay, so here's how I've been approaching the problem from a theoretical standpoint:

The summation 1^3 + 2^3 + ... + n^3 is equal to [n(n+1)/2]^2 = m.
Taking the square root of both sides yields |n(n+1)/2| = sqrt(m). We can disregard the absolute value sign because n will always be positive. So n(n+1)/2 = sqrt(m).
Therefore, n(n+1) = 2*sqrt(m). This problem is essentially asking us to find two consecutive numbers, n and n+1, such that their product is equal to 2*sqrt(m).

My code

def find_nb(m):
    target = 2*math.sqrt(m)
    for n in range(1, int(math.sqrt(target))+1):
        if n*(n+1) == target:
            return n
    return -1

Here, I've defined target to be 2*sqrt(m). I'm looping from n=1 to n=sqrt(target) (inclusive) because there is no point in going beyond the square root of the target when trying to find two numbers, n and n+1, whose product equals the target.

The issue...

This code runs into floating-point precision issues that are fairly consistent across all tests that failed. Here are some screenshots of tests that failed:

Notice that in all of these cases, the value I end up returning is 1 less than the value I stopped looping at. This is quite odd, and I'm not sure what could be causing this behavior.

If you compute the values using a good calculator, you'll find that it is indeed an issue of floating-point imprecision. I'm not sure how to deal with that. My code fails for 33/69 test cases.

Alternative approach

In yet another attempt, I tried doing the most straightforward solution possible: looping from n=1 to n=m and calculating [n(n+1)/2]^2 for each iteration, then comparing this to m. And, unsurprisingly, that solution is not accepted because it takes too long to execute for very large values of m!

So I tried looping from n=1 to n=sqrt(m) to at least simplify the range of values I'm working with. But clearly, the exponentiation, division, and multiplication add up in terms of complexity, and thus this revised approach also results in an execution timeout.

Question

How am I supposed to solve this problem? Is it possible to solve this problem without introducing floating-point errors and without the algorithm taking an unreasonable amount of time for large input values?

Here is a Python function that is about as simple as possible and as fast as possible, assuming the input is valid.

def find_nb(m):
    return int(math.sqrt(2 * (math.sqrt(1.0 * m))))

If the input can be invalid, such as 10252519345963644753026 in the question, and the function should return None accordingly, the Python program can be the following.

def find_nb(m):
    # Use float since math.sqrt is wrong for big integers.
    target = int(math.sqrt(2 * (math.sqrt( 1.0 * m))))
    # or target = int(1.4142135623730951 * m ** 0.25)

    if (target * (target + 1) // 2) * (target * (target + 1) // 2) == m:
        return target
    else:
        return None

What is happening? According to Daniel Castle's comment, for $m\ge1$,

$$ n=\frac{-1+\sqrt{1+8\sqrt{m}}}{2}=\frac{-1}2+\sqrt{\frac14+2\sqrt{m}} $$
It can be checked easily that  $$ n + 0.4 < \sqrt{2\sqrt m} < n + 0.5$$

That means, $n = \lfloor \sqrt{2\sqrt m} \rfloor$ with plenty of room to prevent an error.

Use the ideas of your first approach, but complete them with binary search in order to avoid floating point computations. Start with a large enough interval such as $[a,b] = [0, \lceil m^{1/3} \rceil]$ in which you search for the correct value of $n$ (if it exists). Test $n = \lfloor (a+b)/2 \rfloor$:

If $n^2 (n+1)^2 > 4m$ then you need to look in $[a,n-1]$; update $b$.
If $n^2 (n+1)^2 < 4m$ then you need to look in $[n+1,b]$; update $a$.
If $n^2(n+1)^2=4m$ you are done.


Reduction from TSP to ATSP does not imply constant factor approximation algorithm As I understand there is a constant factor approximation algorithm (e.g Christofides algorithm) for the symmetric TSP problem. This is however not the case for the asymmetric TSP problem (I am assuming we are talking about the metric case for both).
According to Wikipedia there is a reduction from ATSP to TSP, which then can be solved to obtain a solution for the ATSP instance - so why does a solution on this reduction not imply that there is a constant factor approximation for ATSP?

I think the reduction they showed is incorrect. Where it falls is when you connect a node to its "ghost" with 0 cost and add a positive $w$ to all other edges. We will take a look why such a behavior can change the optimal path.
Indeed, take a look at a graph with nodes $v_0,\dots,v_{10}$ where we want to find the shortest path between $v_0$ and $v_{10}$.
The graph's edges will connect $v_i$ to $v_{i+1}$ with weight $1$, and will additionally connect $v_0$ to $v_{10}$ with weight $15$.
Clearly, the path between $v_0$ to $v_1$ and so on until $v_{10}$ has the lowest cost, of $10$.
But now assume we added to all edges a weight $w=1$. Then, this path's value will double to $20$, and the edge between $v_1$ and $v_{10}$ will have weight $16$.
Obviously, the shortest path now is the direct path $v_0,v_{10}$ with cost $16$, hence the optimal path changed.
Important note: Its possible to find a small enough $w$ that will not change the optimal path, but I believe finding one is NP-hard.


Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value GIven a number N, Threshold T and an array A. Find the lexicographically smallest order of N numbers from A such that the total of these N numbers is <= T.

This question is a simplification of this dynamic programming question:

  It’s Tushar’s birthday today and he has N friends. Friends are
  numbered [0, 1, 2, …., N-1] and i-th friend have a positive strength
  S(i). Today being his birthday, his friends have planned to give him
  birthday bombs (kicks :P). Tushar’s friends know Tushar’s pain bearing
  limit and would hit accordingly. If Tushar’s resistance is denoted by
  R (>=0) then find the lexicographically smallest order of friends to
  kick Tushar so that the cumulative kick strength (sum of the strengths
  of friends who kicks) doesn’t exceed his resistance capacity and total
  no. of kicks hit are maximum. Also note that each friend can kick
  unlimited number of times (If a friend hits x times, his strength will
  be counted x times)

  Example:

  R = 11, S = [6,8,5,4,7] Ans = [0,2]

Clearly, the maximum number of kicks = R/ min_element(S) = 11/4 = 2

So the question reduces to find the lexicographic smallest order of 2 elements in the Array such that the total of N elements is less than or equal to 11.

I am having a tough time thinking about a solution for this. Any leads/ ideas would be appreciated!

You are on the right track.

It turns out the original question can be solved by a greedy algorithm. (A full blown solution by dynamic programming as I tried a while ago is both an overkill on coding and short of performance.)

Let us use the notation in the original question. $R$ is for the resistance capacity. $S$ is for the array of strengths.

Let the index of the first minimum strength be $m$. Then the maximum number of kicks is $n = R/S[m]$. So $O=[m, m, \cdots, m]$, where the number of $m$'s is $n$, is a kick order with maximum number of kicks, with total strength $n*S[m]$.

How can we get a lexicographically smaller order with the same number of kicks? If we can find an index $i$ smaller than $m$ such that we can replace a kick of strength $S[m]$ by a kick of strength $S[i]$ without overpassing the resistance capacity $R$, then we can replace the first element in $O$ by $i$, making the order lexicographically smaller. To make it as lexicographically as small as possible, we would like the index $i$ as small as possible and, then, we would like to use it as many times as possible.

For example, $R = 11, S = [6, 8, 5, 4, 7, 4]$. Then the first minimum strength is the first 4 whose index is 3. So $n=11/4=2$ and $O=[3,3]$ with total strength $4*2=8$. To make it smaller, we will check the strengths before 4 in order. The first one is $6$. Since $8-4+6=10<11$, we find a smaller order $[0,3]$. If we apply 6 again, we would get $10-4+6=12 > 11$. So we go ahead to check the next strength 8, which is too large. So we go ahead to check 5. Since $10-4+5=11\le 11$, we find a smaller order $[0,2]$. Since the room left for replacement, $11-11 =0$, we stop our effort. The final answer is [0,2].

I have verified that my program wrote along the above approach works. Hopefully, I have written enough to encourage you to go ahead. Hopefully, I have not written too much to spoil the fun for you.

This problem is a variation of the unbounded knapsack problem.

`c++ solution

#define deb(x) cout<<#x<<" : "<<x<<"\n"
vector<int> Solution::solve(int A, vector<int> &B) {
map<int,int> s;

  for(int i=0;i<B.size();i++)
  if(s[B[i]]!=0)
  s[B[i]]=min(s[B[i]],i);
  else
  s[B[i]]=i;
  int idx=min_element(B.begin(),B.end())-B.begin();
  int mini=*min_element(B.begin(),B.end());
 int x=A/mini;
 vector<int> ans;
 for(int i=0;i<x;i++)
 ans.push_back(mini);
 int sum=mini*x;
 int j=0;
 for(int i=0;i<idx;i++)
  {  //  deb(sum);
   while(j<ans.size() && sum+B[i]-mini<=A)
   {
       ans[j]=B[i];
       sum=sum+B[i]-mini;
       //deb(sum);
       j++;
   }
  }
  for(int i=0;i<ans.size();i++)
  {
    ans[i]=s[ans[i]];
   }
    return ans;

}

`


Start learning about Theory of Distributed Systems? What's the best way that anyone can do to have a good introduction to the theory of distributed system, any books or references, and topics should be covered first and requirements to start learning in this topic.

Roger Wattenhofer's Principles of Distributed Computing lecture collection is also a good place to start.

It is freely available online, it assumes no prior knowledge on the area, and the material is very well up-to-date — it even covers some results that were presented at conferences a couple of months ago.

The book Distributed Systems: Concepts and Design by George Coulouris, Jean Dollimore, Tim Kindberg and Gordon Blair.


Proving a certain superset the halting language is not recursive Let $\Sigma =\{ 0, 1\}$. Let $val:\Sigma^* \rightarrow \mathbb{N}$ be a function that given a string returns its decimal value, and $L_{halt} = \{\langle M\rangle \langle w\rangle \mid M $ halts on $w \}$.

I define the following language:

$L=\{ x \mid x\neq x^R \wedge (x\in L_1 \vee x\in L_2 \vee x\in L_3)\}$

where:

$L_1=\{ x \mid x\in L_{halt} \wedge x^R \in L_{halt} \wedge val(x)<val(x^R) \}$
$L_2=\{ x \mid x\notin L_{halt} \wedge x^R \notin L_{halt} \wedge val(x)<val(x^R) \}$
$L_3=\{ x \mid x\in L_{halt} \wedge x^R \notin L_{halt} \}$ (in this language there is no requirement on $val$ function)

That is, a string in $L$ has 3 options how to look like.

Intuitively I can feel that $L\notin R$, but I do not know how to approach a formal proof for this.

I tried using a reduction $L_{halt} \leq L$, and then since $L_{halt}\notin R$ I can deduce that $L\notin R$, but I could not find a reduction that will work.

The closest thing I could come up with is using an intermediate reduction, first defining $L_{halt}^{'} =\{ 1  x 0 \mid x \in L_{halt} \}$ and then easily $L_{halt} \leq L_{halt}^{'}$ and all I have to do is $L_{halt}^{'} \leq L$, so my idea for reduction was given $x=1y0$ then $f(x)=y$ (the reduction returns $y$), but then this reduction has a problem if $y\notin L_{halt}$ and $y^R\notin L_{halt}$ then it might be possible that $val(y) < val(y^R)$ and then $f(x)=y\in L$ but $y\notin L_{halt}^{'}$...

I'm kind of stuck at how my reduction should work?

I'm also assuming that any string from $\Sigma^*$ is a possible encoding of a $<M><w>$, that is I cannot assume something about the encoding itself and also every word is a possible encoding of $\langle M\rangle \langle w\rangle$...

Main idea of the proof is since $L$ is kind of superset of $L_{halt}$ we select reduction in such a way that we always deal with only that subset of $L$ which resembles $L_{halt}$.

First let us choose any encoding such that if $\langle M,w \rangle \in L_{halt}$ then $\langle M,w \rangle^R \not\in L_{halt}$. $L_{halt}$ is undecidable in every reasonable encoding so this is okay. Also this will be true for most of the encodings if we include $\langle \rangle$ also in the encoding. (Reverse will be $\rangle w^R, M^R \langle$). Also we should have $val(\langle) > val(\rangle)$. I assume that $val$ is calculated as a number with base $|\Gamma|$ where $\Gamma$ is the tape alphabet. In the question decimal base is mentioned, which means the same. We need to add extra 4 bits (= 1 decimal digit) in each cell if we do not have enough space for new symbols.

For this encoding we can have an identity reduction for valid input of the form $\langle M,w \rangle$. For invalid input not of the form $\langle M,w \rangle$ we shall reduce the input to $\langle\epsilon,\epsilon\rangle$ which does not belong to $L$. Let us call this reduction $f$. We assume that in our encoding $\langle\epsilon,\epsilon\rangle \not\in L_{halt}$.

We can now easily prove $x \in L_{halt}$ if and only if $f(x) \in L$.

($\Rightarrow$)
Let $x = \langle M,w \rangle \in L_{halt}$.
Then clearly $val(x) > val(x ^R)$.
And $\langle M,w \rangle^R \not\in L_{halt}$.
Therefore $\langle M,w \rangle \in L_3$ and hence $\langle M,w \rangle \in L$ as naturally $x \neq x^R$, Symbols $\langle,\rangle$ ensures that $x \neq x^R$.

($\Leftarrow$)

Note it $f(x) = \langle \epsilon, \epsilon \rangle$ then it does not belong to $L$. So take the other valid cases.

Let $f(x)= y =\langle M,w \rangle \in L$.
Then $\langle M,w \rangle \in L_3$, as $val(y) > val(y^R)$.
This gives us $\langle M,w \rangle \in L_{halt}$ straight away.

The idea of this proof holds even if we are given a specific encoding for $L$ as well.

1) If the encoding for $L$ is such that we do not have begin symbol $\langle$ and end symbol $\rangle$. Also assume $x_{reject}$ is a string such that $x_{reject} \not\in L$. We can easily find such a string as $L \neq \Sigma^*$. In this case the strings got by reduction will not be necessarily in $L_3$. We also assume our encoding of turing machines is such that we can find a string $\alpha$ such that $0^*\alpha$ is never a proper prefix.

To always get strings in $L_3$ we define the reduction as follows. All invalid input strings which are not of the form $\langle M,w \rangle$ are reduced to $x_{reject}$, and all valid input strings which are of the form $\langle M,w \rangle$ are reduced to $\langle M',w\alpha^R0^{|M'|+1}\rangle$. $M'$ will remove suffix $\alpha^R0^*$ and then behave as $M$.

With this reduction the proof given above can be modified slightly to prove that $L$ is undecidable.

If the encoding for $L$ is such that $\langle$ and $\rangle$ are always included and $val(\langle) < val(\rangle)$ then in the reductions given above we will always get strings from set $L_1$ and $L_2$. In this case by using $\alpha^R0^*$ suffix it is easier to get reduced strings from set $L_2$. Then it is better to reduce language $\overline{L_{halt}}$ which is also undecidable to $L$ to prove undecidability of $L$.


Describing the asymtotic complexity of processing two-dimensional data structures Consider the following Python function:

def count_chars(list_of_strings):
  chars = 0
  for s in list_of_strings:
    for c in s:  # intentionally avoiding len() here for the sake of example
      chars += 1;
  return chars

Clearly this is a linear operation, since we iterate over every element/character once. But I've often seen the Big-O of this function as $O(n*k)$ where $n$ is the length of the list, and $k$ is the length of the longest string. In a sense, that's polynomial or quadratic (at a minimum, I've heard people refer to this type of algorithm as such).

What is the appropriate way to refer to this type of function? Is there an intuitive way to understand this is linear, despite multiple variables?  In particular, how can we discuss that this is worse than a solution that uses len() (which is $O(1)$) without getting hung up on the fact that, in practice, both are linear?

Context: I'm posing an interview question that, while more complex than this example, involves identifying and eliminating $k$.  I've had candidates struggle to see that and it's felt like a communication issue more than a understanding problem.

I'm looking for ways to help guide a discussion, and to recognize that while this is linear, it is still asymptotically worse than an operation that avoids hitting each character individually.

The solution is that you shouldn't just ask whether it is "linear" -- ask what variable it is "linear" in.

Your example code has running time that is linear in the total length of the input strings.  There's a long history of characterizing the running time of an algorithm as a function of the length of the input to the algorithm, and that's an entirely valid thing to do.

It's also true that its running time is $O(nk)$ where $n$ is the number of strings and $k$ is the length of the longest string.  This might be a looser bound.

Both statements are true, and don't contradict each other.  It's just a matter of identifying which upper bound on the running time is more useful.

This algorithm does not have linear complexity and as posed, provides (and uses) two separate variables, as you described n and k.  From the candiates perspective, there is no indication that the list length or the string length is bounded in any manner.

Remember:  f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k.  The values of c and k must be fixed for the function f and must not depend on n.

I am going to ignore the n ≥ k for the rest of this argument.

What this means is that we are defining an upper bound to the complexity for f(n) (to less than g(n)) that can only grow as a scalar multiple of c in relation to the complexity of g(n).

In your example there are two variables so any attempt to define an upper bound based on one, can easily be violated by changing the other.

The inner loop is clearly bounded by the length of the longest string O(k) which is really saying there exists constants where 0 ≤ f(k) ≤ cg(k) for all k.  However, that isn't the end of the problem, there is an arbitrary number of strings in the list that violates this.  Simply speaking, if the list length is greater than c then the assertion  0 ≤ f(k) ≤ cg(k) becomes incorrect.  The problem is that for any c provided, defining a list length of c+1 will cause this assertion to fail. (and changing c makes it no longer a constant).

The answer is O(n*k)


What is the difference between storage media and storage devices I am having a rather distressing confusion about whether storage media and storage devices are the same terms. I found on this yahoo answers page that there is a subtle difference but very tricky to understand.

I have googled a lot but cannot find the satisfying answer.

Can anyone kindly explain the difference between these two terms with easy-to-understand examples.

Regards

Media is what holds the information, e.g. disk platen, CD, magnetic stripe.
Device is what uses the media and provides a physical interface.

For devices that have removable media, such as CD/DVD players the distinction is easy. For other devices where the media is an integral part of the device, the distinction is not so easy because the media is not designed to be removed, e.g. hard drive, thumb drive.

Media is a medium on which data is saved. e.g CD
Devices are something which run a Media on it. eg CD player.


Is equivalence of CFGs decidable for finite sets of grammars? Is there a way to show that for all finite sets $S$ of context free grammars, there exists a Turing Machine $M$ such that for all grammars $G_1, G_2 \in S$, we have that $M(G1,G2)$ terminates and answer yes if and only if $L(G_1)=L(G_2)$? Is that even true?

I know that this problem is in general undecidable, but I also know that a finite set is in general decidable. I just can't figure out how to determine the answer for this problem.

A problem is decidable if there is a TM which decides instances of the problem.

Given two arbitrary CFGs $G_1$ and $G_2$, we know this for certain: either $L(G_1) = L(G_2)$, or $L(G_1) \neq L(G_2)$. Consider the first case: a TM that accepts on the input $(G_1, G_2)$ correctly decides this problem. Consider the second case: a TM that rejects on the input $(G_1, G_2)$ would be correct in that case.

Now, consider a finite set of grammars $\{G_1, G_2, ..., G_n\}$. For any two grammars $G_i$ and $G_j$ in this set, we know that either $L(G_i) = L(G_j)$ or $L(G_i) \neq L(G_j)$.

Consider the following TMs:

TM #1:

if input is (G_1, G_1) then accept
if input is (G_1, G_2) then accept
...
if input is (G_n, G_n) then accept

TM #2:

if input is (G_1, G_1) then accept
if input is (G_1, G_2) then accept
...
if input is (G_n, G_n) then reject

...

TM #N

if input is (G_1, G_1) then reject
if input is (G_1, G_2) then reject
...
if input is (G_n, G_n) then reject

Each TM can either accept or reject for each of the $n^2$ (ordered) inputs; so there are $N = 2^{n^2}$ different TMs (as many as binary strings of length $n^2$).

One of these TMs is guaranteed to correctly decide your problem. I can't tell you which one, but one of these gives all the correct answers. Since there is a TM for your problem, it's decidable.

It is undecidable if two grammars generate the same language (see here), so this (more general)  question is undecidable too.


Can an algorithm that yields $O(n^2)$ answers run in $O(n)$ time? My question may actually be more broadly described as: can I use the fact that an algorithm is expected to return $(O(f(n))$ answers to show that it may never run better than $O(f(n))$? I would intuitively assume yes, but I am not sure.

Examples of what I'm talking about is algorithms to calculate all the paths that pass through a set of points. I can easily calculate a higher bound $O(f(n))$ on how many those paths are. Will that tell me the algorithm must be no better than $\Omega(f(n))$?

Thanks

Can an algorithm that yields $O(n^2)$ answers run in $O(n)$ time?

Yes.  The following algorithm yields $O(n^2)$ answers (remember what $O(\cdot)$ means!) but it runs in time $O(n)$.

halt;

You probably meant to ask if an algorithm that yields $\Theta(n^2)$ answers can run in time $O(n)$. The answer to that is no. Whatever exact definition you choose for "yielding an answer", yielding one answer must take at least one computation step in any reasonable model of computation, so writing $\Theta(n^2)$ answers must take $\Omega(n^2)$ steps.

In essence, the running time depends on the size of the data and the format in which data is provided to the algorithm.

Otherwise, there seems to be a little correlation between the complexity of algorithm under different set of inputs.


How to find middle element of linked list in one pass? One of the most popular question from data structures and algorithm, mostly asked on telephonic interview.

By cheating, and doing two passes at the same time, in parallel. But I do not know whether the recruiters will like this.

Can be done on a single linked list, with a nice trick. Two pointers travel over the list, one with double speed. When the fast one reaches the end, the other one is half-way.

By using 2 pointers . Increment one at each iteration and other at every second iteration. When 1st pointer points to end of linked list, went 2nd pointer will point to the middle mode of linked list .


is determinism = non determinism for one counter automata? This language I think is not accepted by a deterministic one counter but accepted by a non-deterministic one counter :

$L = \{a^{i}b^{j}c^{k} \mid (i=j) \vee (j=k) \text{ such that } i\geq0, j\geq0, k\geq0\}$

But how to prove this claim?

Or is it the case that they are equivalent?

You are right: the language $L$ from your question is accepted by a (nondeterministic) one-counter automaton.

Now for the deterministic case. Counter automata are a special case of push-down automata, where one only uses a single stack symbol (apart from a bottom-of-stack). Every (deterministic) one-counter language is also a (deterministic) push-down language. So in order to demonstrate it is not a deterministic one-counter language, I show a stronger result: it is even not accepted by a deterministic PDA.

According to Ogden, in his paper introducing Ogden's Lemma, that same language $L$ is inherently ambiguous context-free, meaning that every possible context-free grammar for the language is ambiguous, i.e., it has a string with two different succesful derivation trees.
On the other hand, it is known that every deterministic PDA can be transformed into a non-ambiguous CFG. In fact I believe the standard construction PDA to CFG does the trick (but that is not obvious).
Hence as there is no non-ambiguous CF grammar for $L$ (Ogden), there can be no deterministic PDA for $L$, and in particular no deterministic one-counter automaton.

Conclusion: for one-counter automata determinism is less powerful than the general model, using your example.

(In an edit I moved info from comments into this text.)
Reference, see also Wikipedia: Ogden, W. (1968). A helpful result for proving inherent ambiguity. Math. Syst. Theory 2, 191–194.

All non-deterministic finite-state automata (NFA) can be represented with an equivalent deterministic finite-state automata (DFA). If you can make a NFSA that recognizes the language, you can convert it to a DFA. Have a look here for more information on how to do that.

In this particular case, I believe that that language cannot be represented even by a NFA, as it would require an infinite number of states to represent the different values of i, j and k (as FSA do not have "memory" so a machine cannot remember that it's counted i a's to count that many b's).


Is there any proof that quantum computers are more efficient than classical computers? Shor's algorithm is often used as the argument. It can solve the factorization problem faster than any known algorithm for classical computers. Yet, we have no proof classical computers can't also factor integers efficiently.

Is there any actual proof quantum computers can solve some problems faster than classical computers?

Yes, Grover's algorithm shows you can use a quantum algorithm to find an element in an unordered database of size $N$ with high probability by querying the database only $O(\sqrt{N})$ times. Any classical solution that succeeds with high probability requires $\Omega (N)$ queries to the database.

you ask about "proof" which might be limited to a mathematical level, but the basic question goes much deeper than that. theoreticians will acknowledge its basically still an open question in general about the relative performance of quantum vs classical algorithms and there is probably no simple/ general answer, but with some expert consensus that Shors algorithm seems to be "unusually fast compared to expected best classical speed." fast factoring in a classical computer will break widely held cryptographic security assumptions such as the RSA system.

some of this is captured formally in the open complexity class question BPP =? BQP question. these are the analogous classical and quantum classes and the separation is unknown and an active area of research.
a closely related question is whether physically QM computers can be built that match the theoretical specifications and a few/ minority of scientists (aka "skeptics") are arguing that there may be noise or scaling laws that prevent QM scaling as envisioned in the theory. in a sense the ultimate "proof" of a QM computer speed must be a physical implementation. (this is similar to the way the Church-Turing thesis is theoretical but seems to ultimately tie into an assertion about physical implementations.) some researchers are talking about Church-Turing analogs in QM computing. see eg Church Turing thesis in a quantum world by Montanaro.
relevant to/ impinging on this question/ debate are ongoing substantial/ "heated" (scientific) attempts to benchmark the worlds current "largest" quantum computer by DWave. this is a big topic with a lot of related material, but for a relatively recent overview try D-Wave disputes benchmark study showing sluggish quantum computer / the Register


Difference between regular expressions: $(0^*1^*)^*$ and $(0+1)^*$ Can anyone tell me what is the difference between the following regular expressions: $(0^*1^*)^*$ and $(0+1)^*$ ? To me they look like generating the same string.

The language of both regular expressions is the same, $L((0+1)^*)=L((0^*1^*)^*)$. This follows from the following three claims:

Claim 1:

  if $L_1 \subseteq L_2$, then $L_1^* \subseteq L_2^*$.

Claim 2:

  $L(0+1) \subseteq L(0^*1^*)$

Claim 3:

  $ (0^*1^*)^* \subseteq (0+1)^* \equiv \Sigma^*$

The 2nd and 3rd claims are trivial. Prove the first claim and you're done.

Note however, that the two regular expressions are not the same (ie., they are different!). They are equivalent in the sense of the language they generate. They are different in the way they generate it.

They are not the same. When we say $0+1$ it signifies a union operation, which is "either or". So either $0$ or $1$ can be present and the ${}^*$ indicates that it can be present any number of times.

On the other hand, $01$ is a concatenation of the symbols $0$ and $1$.
So $(0^*1^*)$ means $0$ can occur any number of times followed by $1$ occurring any number of times and the outer asterisk denotes that such a sequence can occur in the string $n$ times.


What properties of a programming language make compilation impossible? Question:

"Certain properties of a programming language may require that the only way to get the code written in it be executed is by interpretation. In other words, compilation to a native machine code of a traditional CPU is not possible. What are these properties?"

Compilers: Principles and Practice by Parag H. Dave and Himanshu B. Dave (May 2, 2012)

The book gives no clue about the answer. I tried to find the answer on Concepts of Programming Languages (SEBESTA), but to no avail. Web searches were of little avail too. Do you have any clue?

The distinction between interpreted and compiled code is probably a
fiction, as underlined by Raphael's comment:

the claim seems to be trivially wrong without further assumptions: if there is
an interpreter, I can always bundle interpreter and code in one executable ...

The fact is that code is always interpreted, by software, by hardware
or a combination of both, and the compiling process cannot tell which
it will be.

What you perceive as compilation is a translation process from one
language $S$ (for source) to another language $T$ (for target). And, the
interpreter for $S$ is usually different from the interpreter for $T$.

The compiled program is translated from one syntactic form $P_S$ to
another syntactic form $P_T$, such that, given the intended semantics
of the languages $S$ and $T$, $P_S$ and $P_T$ have the same
computational behavior, up to a few things that you are usually trying
to change, possibly to optimize, such as complexity or simple efficiency (time, space,
surface, energy consumption). I am trying not to talk of functional equivalence, as it would require precise definitions.

Some compilers have been actually used simply to reduce the size of
the code, not to "improve" execution. This was the case for language used in the Plato system (though they did not call it compiling).

You may consider your code fully compiled if, after the compiling
process, you no longer need the interpreter for $S$. At least, that is
the only way I can read your question, as an engineering rather than
theoretical question (since, theoretically, I can always rebuild the
interpreter).

One thing that may raise problem, afaik, is meta-circularity. That
is when a program will manipulate syntactic structures in its own source
language $S$, creating program fragment that are then intepreted as if
they had been part of the original program. Since you can produce
arbitrary program fragments in the language $S$ as the result of arbitrary computation manipulating meaningless syntactic fragments, I would guess you can
make it nearly impossible (from an engineering point of view) to
compile the program into the language $T$, so that it now generate
fragments of $T$. Hence the interpreter for $S$ will be needed, or at
least the compiler from $S$ to $T$ for on-the-fly compiling of
generated fragments in $S$ (see also this document).

But I am not sure how this can be formalized properly (and do not have
time right now for it). And impossible is a big word for an issue that is not formalized.

Futher remarks

Added after 36 hours. You may want to skip this very long sequel.

The many comments to this question show two views of the problem: a
theoretical view that see it as meaningless, and an engineering view
that is unfortunately not so easily formalized.

There are many ways to look at interpretation and compilation, and I
will try to sketch a few. I will attempt to be as informal as I can manage

The Tombstone Diagram

One of the early formalization (early 1960s to late 1990) is the T or
Tombstone diagrams. These diagrams presented in composable graphical
elements the implementation language of the interpreter or compiler,
the source language being interpreted or compiled, and the target
language in the case of compilers. More elaborate versions can add
attributes. These graphic representations can be seen as axioms,
inference rules, usable to mechanically derive processor generation
from a proof of their existence from the axioms, à la Curry-Howard
(though I am not sure that was done in the sixties :).

Partial evaluation

Another interesting view is the partial evaluation paradigm. I am
taking a simple view of programs as a kind of function implementation
that computes an answer given some input data. Then an interpreter
$I_S$ for the language $S$ is a program that take a program $p_S$
written in $S$ and data $d$ for that program, and computes the result
according to the semantics of $S$. Partial evaluation is a technique
for specializing a program of two arguments $a_1$ and $a_2$, when only
one argument, say $a_1$, is known. The intent is to have a faster
evaluation when you finally get the second argument $a_2$. It is
especially useful if $a_2$ changes more often than $a_1$ as the cost
of partial evaluation with $a_1$ can be amortized on all the
computations where only $a_2$ is changing.

This is a frequent situation in algorithm design (often the topic of
the first comment on SE-CS), when some more static part of the data is
pre-processed, so that the cost of the pre-processing can be amortized
on all applications of the algorithm with more variable parts of the
input data.

This is also the very situation of interpreters, as the first argument
is the program to be executed, and is usually executed many times with
different data (or has subparts executed many times with different
data). Hence it become a natural idea to specialize an interpreter for
faster evaluation of a given program by partially evaluating it on
this program as first argument.  This may be seen as a way of
compiling the program, and there has been significant
research work on compiling by partial evaluation of a interpreter on
its first (program) argument.

The Smn theorem

The nice point about the partial evaluation approach is that it does
take its roots in theory (though theory can be a liar), notably in
Kleene's Smn theorem.  I am trying here to give an intuitive
presentation of it, hoping it will not upset pure theoreticians.

Given a Gödel numbering $\varphi$ of recursive functions, you can
view $\varphi$ as your hardware, so that given the Gödel number $p$
(read object code) of a program $\varphi_p$ is the function defined
by $p$ (i.e. computed by the object code on your hardware).

In its simplest form, the theorem is stated in wikipedia as follows
(up to a small change in notation):

  Given a Gödel numbering $\varphi$ of recursive functions, there is a primitive recursive function $\sigma$ of two arguments with the following property: for every Gödel number $q$ of a partial computable function $f$ with two arguments, the expressions $\varphi_{\sigma(q,x)}(y)$ and $f(x,y)$ are defined for the same combinations of natural numbers $x$ and $y$, and their values are equal for any such combination. In other words, the following extensional equality of functions holds for every $x$:
      $\;\;\varphi_{\sigma(q,x)} \simeq \lambda y.\varphi_q(x,y).\,$

Now, taking $q$ as the interpreter $I_S$, $x$ as the source code of a
program $p_S$, and $y$ as the data $d$ for that program, we can write:
   $\;\;\varphi_{\sigma(I_S,p_S)} \simeq \lambda d.\varphi_{I_S}(p_S,d).\,$

$\varphi_{I_S}$ may be seen as the execution of the interpreter $I_S$
on the hardware, i.e., as a black-box ready to interpret programs
written in language $S$.

The function $\sigma$ may be seen as a function that specializes the
interpreter $I_S$ for the program $P_S$, as in partial evaluation.
Thus the Gödel number $\sigma(I_S,p_S)$ may be seen has object code that is
the compiled version of program $p_S$.

So the function $\;C_S = \lambda q_S.\sigma((I_S,q_S)$ may be seen as
a function that take as argument the source code of a program $q_S$
written in language $S$, and return the object code version for that
program. So $C_S$ is what is usually called a compiler.

Some conclusions

However, as I said: "theory can be a liar", or actually seem to be one. The problem is that we
know nothing of the function $\sigma$. There are actually many such
functions, and my guess is that the proof of the theorem may use a
very simple definition for it, which might be no better, from an
engineering point of view, than the solution proposed by Raphael: to
simply bundle the source code $q_S$ with the interpreter $I_S$. This
can always be done, so that we can say: compiling is always
possible.

Formalizing a more restrictive notion of what is a compiler would
require a more subtle theoretical approach. I do not know what may
have been done in that direction. The very real work done on partial
evaluation is more realistic from an engineering point of view. And
there are of course other techniques for writing compilers, including
extraction of programs from the proof of their specification, as
developed in the context of type-theory, based on the Curry-Howard
isomorphism (but I am getting outside my domain of competence).

My purpose here has been to show that Raphael's remark is not "crazy",
but a sane reminder that things are not obvious, and not even
simple. Saying that something is impossible is a strong statement
that does require precise definitions and a proof, if only to have a
precise understanding of how and why it is impossible. But building
a proper formalization to express such a proof may be quite difficult.

This said, even if a specific feature is not compilable, in the sense
understood by engineers, standard compiling techniques can always be
applied to parts of the programs that do not use such a feature, as is
remarked by Gilles' answer.

To follow on Gilles' key remarks that, depending on the language, some
thing may be done at compile-time, while other have to be done at
run-time, thus requiring specific code, we can see that the concept of
compilation is actually ill-defined, and is probably not definable in
any satisfactory way. Compilation is only an optimization process, as
I tried to show in the partial evaluation section, when I compared
it with static data preprocessing in some algorithms.

As a complex optimization process, the concept of compilation actually
belongs to a continuum. Depending on the characteristic of the
language, or of the program, some information may be available
statically and allow for better optimization. Others things have to be
postponed to run-time. When things get really bad, everything has to
be done at run-time at least for some parts of the program, and
bundling  source-code with the interpreter is all you can do. So this
bundling is just the low end of this compiling continuum. Much of the research on compilers is about finding ways to do statically what used to be done dynamically. Compile-time garbage collection seems a good example.

Note that saying that the compilation process should produce machine
code is no help. That is precisely what the bundling can do as the
interpreter is machine code (well, thing can get a bit more complex
with cross-compilation).

I feel the original question is not well formed. The authors of the question may have intended to ask a somewhat different question: What properties of a progamming language facilitate writing a compiler for it?

For example, it's easier to write a compiler for a context-free language than a context-sensitive language. The grammar which defines a language can also have issues that make it challenging to compile, such as ambiguities. Such issues can be resolved but require extra effort. Similarly, languages defined by unrestricted grammars are harder to parse than context-sensitive languages (see Chomsky Hierarchy). To my knowledge most widely used procedural programming languages are close to context-free, but have a few context-sensitive elements, making them relatively easy to compile.


Finding the kth element of a permutation Is there a way to generate a random permutation of the numbers 1 to N such that I can find the k-th element of the permuted list without needing to either 1) store the entire permuted list, or 2) compute the elements 1..k-1?

Problem statement

Your question is unclear, but here is how I interpret it:

  Input: a positive integer $n$, and $k$ distinct values $x_1,\dots,x_k \in \{1,2,\dots,n\}$
  Output: the values $\pi(x_1),\pi(x_2),\dots,\pi(x_k)$, where $\pi$ is a random permutation on $\{1,2,\dots,n\}$

You are looking for an efficient algorithm to solve this problem.

An efficient solution

If that is indeed what you are looking for, there is a very efficient way to solve this problem.  Basically, all you need to do is randomly choose $k$ distinct integers from the set $\{1,2,\dots,n\}$.  This is sampling without replacement.  Here is a simple algorithm:

Initialize $S$ to be the empty set.
For $i=1,2,\dots,k$:

Pick $r$ uniformly at random from $\{1,2,\dots,n\}$.  If $r\in S$, pick a new $r$ (and keep repeating until $r \notin S$).
Set $x_i$ to $r$, and add $r$ to $S$.

You can use any number of data structures for storing the set $S$; it could be a bitvector of length $n$, or a hashtable.  (A bitvector is probably better if $k$ is not too much smaller than $n$, say $k \ge n/64$ or so; a hashtable is probably more efficient if $k$ is small compared to $n$.)

Performance analysis

If $k \le n/2$, the expected running time is linear in $n$, so this is very efficient.

If $k \ge n/2$, there are better algorithms.  For instance, once you reach $i \ge n/2$, then rather than choosely uniformly, you can choose uniformly at random from $\overline{S}$ (the complement of $S$).  If you use the right data structures, you can make the expected running time be linear in $n$.  (Basically, once $i\ge n/2$, you compute $\overline{S}$ and throw away $S$.  In each step, you choose a random element of $\overline{S}$, then remove it from $\overline{S}$.  Choosing a random element of a set can be done in $O(1)$ expected time.)

If you rank all the n! Permutaions in some order, such as the lexicographic order, then you can unrank a number to a permutation. The procedure is simple. So given a random number in [1..n!], you can compute a random permutation.


Does the 'difference' operation add expressiveness to a query language that already includes 'join'? The set difference operator (e.g., EXCEPT in some SQL variants) is one of the many fundamental operators of relational algebra. However, there are some databases that do not support the set difference operator directly, but which support LEFT JOIN (a kind of outer join), and in practice this can be used instead of a set difference operation to achieve the same effect.

Does this mean that the expressive power of a query language is the same even without the set difference operator, so long as the LEFT JOIN operator is maintained? How would one prove this fact?

In relational algebra, we shall first provide an informal definition of left (outer) join, and proceed to prove that it, renaming, selection, join and projection can construct difference, as well as that difference, selection and union can be used to construct left (outer) join. Actually, we'll end up doing it in the reverse order: we'll show how to construct left joins using differences, and then we'll show how to construct differences using left joins.

Let $R$ and $S$ have schemata $(R', T)$ and $(T, S')$, respectively, where $R'$ and $S'$ are the sets of attributes in one schema but not the other, and $T$ is the set of common attributes.

Let $w = (\epsilon, \epsilon, ..., \epsilon)$ be the null tuple for schema $S'$. That is, it is the tuple consisting of all null values for each attribute of $S'$. Then, we define left outer join as follows: R LEFT JOIN S is the set of all tuples $(r, t, s)$ belonging to schema $(R', T, S')$ where...

$(r, t)$  is a tuple in $R$;
(a) $(t, s)$ is a tuple of $S$ or (b) $s = w$;
If $(r, t, s)$ is in the set for $s \neq w$, then $(r, t, w)$ is not in the set.

Example: $R$'s schema is $(A_{1}, A_{2}, A_{3})$, $S$'s schema is $(A_{2}, A_{3}, A_{4})$, and we have that $R = \{(1, 2, 3), (4, 5, 6)\}$ and $S = \{(2, 3, 4), (2, 3, 6)\}$. By (1) and (2) we get the intermediate result $\{(1, 2, 3, 4),(1, 2, 3, 6), (1, 2, 3, \epsilon),(4, 5, 6, \epsilon)\}$. By (3) we must remove $(1, 2, 3, \epsilon)$, since we have (for instance) $(1, 2, 3, 4)$ and $s = 4 \neq \epsilon = w$. We are thus left with $\{(1, 2, 3, 4), (1, 2, 3, 6), (4, 5, 6, \epsilon)\}$, the expected result for a left join.

Theorem: R LEFT JOIN S is equivalent to (R EQUIJOIN S) UNION ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w).

Proof: (R EQUIJOIN S) gives us everything required by (1) and (2a). We claim that ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w) gives us everything of the form (r, t, w) required by (2b) and (3).

To see this, first notice that (((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) is the set of all tuples in $R$ for which there is no corresponding tuple in $S$. To see that, it suffices to note that by projecting the common attributes out of $R$ and $S$ (the attribute set $T$) and taking the difference, one is left with all and only those tuples (with schema $T$) which are represented in $R$ but not $S$. By the EQUIJOIN with $R$, we recover all and only those tuples in $R$ which have values for attributes in $T$ which are present in $R$ but not in $S$; namely, precisely the set of tuples we have so far claimed.

Next, notice that the schema of (((PROJECT_T R) DIFFERENCE (PROJECT_T S)) is the same as that of $R$ (namely, $(R', T)$), while the schema of $w$ is $S'$. The JOIN operation is therefore a Cartesian product, we we get all tuples of the form $(r, t, w)$ where there is no $(t, s)$ in $S$ corresponding to $(r, t)$ in $R$.

To see that this is precisely the set of tuples we needed to add to R EQUIJOIN S in order to construct R LEFT JOIN S, consider the following: by construction, (3) is satisfied, since R EQUIJOIN S cannot contain $(r, t, s)$ if ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w) contains $(r, t, w)$ (if it did, then the second part's containing $(r, t, w)$ would be a contradiction); if we were to add another $(r, t, w)$ not in ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w), then there would be a $(t, s)$ in $S$ corresponding to $(r, t)$ in $R$, and by the definition of EQUIJOIN, $(r, t, s)$ would also be in R LEFT JOIN S, a contradiction of (3). This completes the proof.

Now we show that left join can be used to construct difference:

Theorem: R DIFFERENCE S is equivalent to PROJECT_T(SELECT_{t'=w}(R LEFT JOIN (SELECT_{s=s'}(((S JOIN RENAME_{T->T'}(S)))))))

Proof: Notice that here, $R'$ and $S'$ are empty, since all attributes are shared for DIFFERENCE to make sense. First, we create a new relation from $S$ by duplicating the attribute set in $S$ (handled by RENAME and JOIN) so that it consists of tuples $(t, t')$ on attribute set $(T, T')$ where $t = t'$ (handled by the SELECT). The left join leaves us with tuples of the form $(t, t')$ where $t=t'$ or $t'=w$. Now, to get rid of entries which do also appear in $S$, we must keep only the tuples of the form $(t, w)$, which is handled by the outermost SELECT. The last PROJECT gets rid of the temporary attribute set $T'$ and leaves us with the difference in terms of the original schema.

Example: Let $R = \{(1, 2), (3, 4), (5, 6)\}$ and $S = \{(3, 4), (5, 6), (7, 8)\}$. We first get $S$ with the RENAMEd attribute set $T'$: $\{(3, 4), (5, 6), (7, 8)\}$. The JOIN operation gives us the Cartesian product with all nine possible pairings; this set is not written here for reasons of formatting. The SELECT then pares this down to $\{(3, 4, 3, 4), (5, 6, 5, 6), (7, 8, 7, 8)\}$. The LEFT JOIN with $R$ gives $\{(1, 2, \epsilon, \epsilon), (3, 4, 3, 4), (5, 6, 5, 6)\}$. The SELECT gives $\{(1, 2, \epsilon, \epsilon)\}$. The PROJECT gives $\{(1, 2)\}$, the desired answer.

LEFT JOIN as implemented by SQL, does not produce relations as its result (because some attributes of the result will not have a value).

Ergo, LEFT JOIN as implemented by SQL, is not a direct counterpart of any relational algebra operator.

Ergo, The relational difference operator cannot be expressed in terms of LEFT JOIN (because LEFT JOIN cannot possibly be part of the relational algebra, this being because LEFT JOIN produces something that is not a relation, thus violating closure of the algebra).

Any set of primitive operators of a relational algebra that satisfies closure that I know of, always includes either relational difference or else relational semidifference.


Can a DFA have two symbols on one arrow? I know that a DFA has to have exactly one transition for each symbol in the alphabet, but is it allowed to have two symbols on the same arrow? If, for example, I have a DFA with states $q_0$ and $q_1$, can I have one arrow from $q_0$ to $q_1$ with both $a$ and $b$?

This may be a stupid question, but I need to be completely sure that this is allowed (I believe it is).

The transition graph (as a drawing) is merely a representation of an Automaton, which is a well-defined model.

Formally, an DFA is a tuple $(Q,\Sigma,\delta,q_0,F)$, where the "type" of the transition function is $\delta:Q\times \Sigma\to Q$.

Thus, if you have $\delta(q_0,a)=\delta(q_0,b)=q_1$, that's fine.
In the graphic representation, you will either have two arrows from $q_0$ to $q_1$, labeled $a$ and $b$, or you can just put both letters on the same arrow, it's not a formal thing anyway.

As long as the starting and ending  of respective states are same you can add as many symbols.


How to write an EBNF grammar for Java float literals? I've got this question on my study guide: "Write an EBNF grammar description for Java float literals and one for Java double literals."

I've browsed the Oracle site and found the grammar for java float literals, but I'm not entirely sure how to convert that to EBNF grammar. I understand EBNF notation but for some reason I'm stuck on this.

I was hoping/wondering someone would be able to get me started? It would be highly appreciated.

You could try answer the question "How do I define double and float literals?"

doubles are usually defined as:

double a = 12d;
//or
double b = 12.1;
//or
double c = 12.1d;
//or
double d = 12;

while floats could be defined as:

float m = 10;
//or
float n = 10.4f;
//but this is invalid:
float p = 10.4;

Note that by default a literal like 10.123 is considered to be double, so if you really want to assign it to a float variable, you need to append a f
character in the end. However, f is optional when the literal is 10.

Let's also list the properties of both types:

float: 32 bits (4 bytes) where 23 bits are used for the mantissa (up to 9 decimal digits). 8 bits are used for the exponent, so a float can move the decimal point to the right or to the left using those 8 bits. There is 1 bit used as the sign bit. The max long value that double can hold is $10_18$

double: 64 bits (8 bytes) where 52 bits are used for the mantissa (up to 19 decimal digits). 11 bits are used for the exponent and 1 bit is the sign bit.

So, double and float could be defined like:

digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";

double = 19 * digit, [ [, | .]  18 * digit]["d" | "D"];
float = 19 * digit, [ [, | .]  18 * digit, "f" | "F"];


Solving recurrence relation with square root I am trying to solve the following recurrence relation :-

$T(n) = T(\sqrt{n}) + n$ using masters theorem.

We can substitute $n = 2 ^ m$

$T(2^m) = T(2 ^ {\frac{m}{2}}) + 2^m$

Now we can rewrite it as

$S(m) = S(\frac{m}{2}) + m$

The big $O$-notation for $S(m)$ will be $O(m)$.

Hence, $T(n) = T(2^m) = S(m) = O(m)$.

So we can say that $T(n) =O(\log n)$ as $n=2^m$.

But the answer is $O(\log\log n)$ . What is wrong with my approach ?

The answer cannot be $O(\log\log n)$. Already without applying any recursion we have the inequality $T(n) = T(\sqrt{n}) + n \ge n$. So the complexity cannot be smaller than $O(n)$.

But now to your computation.  Setting $n=2^m$, we obtain as you did
$$ T(2^m) = T(\sqrt{2 ^ m}) + 2^m=T(2 ^ {\frac{m}{2}}) + 2^m.\tag{1}\label{eq1}$$ You defined $$S(m) = T(2^m).$$ Then equation $\eqref{eq1}$ should become the following equation,
which is different from $S(m)\,$$= S(\frac{m}{2})\,$$ + m$, the wrong equation in the question.

$$S(m) = S\left(\frac{m}{2}\right) + 2^m.$$

The equation above falls into the third case of the master theorem, therefore $S(m) \in \Theta(2^m)$. And from this follows $T(n) \in \Theta(n)$.

Complexity of above recurrence is O(m) which is O(log m) and now n = 2 ^m so m = log n and hence complexity is
O(log log n).


Is this language Context-Free? Possible Duplicate:
  Is this language Context-Free?

The language is defined by
$$(a+b)^*-\{(a^nb^n)^n\mid n \geq1 \}$$

is Context-Free Language? I believe that the answer is that it is not a CFL's, but I can't prove it by Ogden lemma or pumping lemma.

chazisop, (a+b)* means {a,b}*. That's all strings that you can form with the symbols a or b or both.

If I understand the notation correctly, only $ab$ can fit both $(a+b)^{*}$ and $(a^{n}b^{n})^{n}$. I see no other way of stacking more $b$'s after the a's, since $a+$ suggest you should have at least one $a$ in every repetition of the expression in parentheses.

$(a+b)^{*}-ab$ seems like a regular language to me, since $ab$ rejects, $a+b$ just consumes one or more $a$'s before a $b$. If we can construct a DFA for $a+b$, we can construct one for $(a+b)^{*}$ as well.


Why is Computer Architecture in $2^n$ bits? I have always wondered why is computer architecture in $2^n$ bits. We have 8 / 16 / 32 / 64-bit microprocessors or for that matter other parts of computer are also in power of 2 bits.

The only logic I could understand from my reasoning is that usually computer design process starts from lower amount of bits. For example : Say I want to design a Full adder to add 16 bit numbers. So I would first design a digital circuit to add 2 bits (one from number A and other form number B). Then I would replicate this circuit 16 times. So this will give me 16-bit full adder.

Is my reasoning correct ? Is there some other reason also ?

Not necessarily, for instance, look at the memory bus width in modern day GPUs, they would have values of 192, 384, 768(while 128, 256.... are common).

One could argue that 192 is a sum of powers of 2 (2^7+2^6), sure, but what number isn't?

That being said, any memory modules directly associated with a microprocessor or a microcontroller will have capacities in powers of 2. Traditionally registers will be 8,16, 32 or 64 bits long (though 10-bit and other non conventional widths exist).

A processor (or controller) with an n-bit register can address upto 2^n addresses (i.e, 0-(2^n)-1 bytes). Hence without changing the processor, one can extend the memory associated with it although exceeding the addressing space beyond what the processor can manage will be redundant.

In many DSPs, the memory associated with the processor is in 2^n multiples as many of the signal processing algorithms can be made very efficient when calculating this way.

Some say that the IBM STRETCH (1961) introduced 8bits bytes :

http://en.wikipedia.org/wiki/IBM_7030_Stretch

Until the late 70s, computers used other sizes and multiples, for example 36bits = 8 characters of 6 bits.
Early computers used only uppercase letters and numbers, using 6bits per character was more efficient.

Anyway, ask wikipedia : http://en.wikipedia.org/wiki/12-bit, http://en.wikipedia.org/wiki/18-bit...

There can be several explanations for the fact that all modern computers use 8bits bytes and multiples thereof. All monolithic microprocessors used that (8080, 6502...), 7 or 8bits ASCII was necessary for making text in uppercase and lowercase with internationalisation. Using powers of two all the way down must be appealing for computer designers...


How can I decide manually whether two CTL formulae are equivalent? Assume I have two formulae $\Phi$ and $\Psi$ (over the same set of atomic propositions $AP$) in CTL. We have that $\Phi \equiv \Psi$ iff $Sat_{TS}(\Phi) = Sat_{TS}(\Psi)$ for all transition systems $TS$ over $AP$.

Given that there are infinitely many transition systems, it's impossible to check them all. I thought about using PNF (Positive Normal Form, allowing negation only next to literals) because judging from its name it should give me the same formula for $\Phi$ as for $\Psi$ iff they are equivalent, but I'm not convinced this works in all cases (you could say, I'm not convinced PNF is actually a normal form).

For example, take $\forall \mathrm{O} \forall \lozenge \Phi_0 \stackrel{?}{\equiv} \forall \lozenge \forall \mathrm{O} \Phi_0$ (where $\mathrm{O}$ is the next operator and $\lozenge$ is the eventually operator). I'm looking for a way do do this by hand.

It seems to me that "$\Phi≡\Psi$" is equivalent to "Neither $(\Phi ∧ ¬\Psi)$ nor $(\Psi ∧ ¬\Phi)$ is satisfiable".

Therefore deciding equivalence is as difficult as deciding satisfiability, since "$\Phi$ satisfiable" is equivalent to "not ($¬\Phi≡\top$)".

In this article there is a mention of a an exponential procedure to decide satisfiability in CTL, so it should be enough to run the algorithm on the two formulas I wrote above.

PS: I am not at all an expert in this field, so please check what I wrote. If this makes sense, I will remove the various "seems" and "should".

Could you express this in the fixpoint characterization for CTL formulas? That might help you prove their equivalence.
http://www-2.cs.cmu.edu/~modelcheck/ed-papers/VTfFSCS.pdf


Banker's Algorithm and deadlocks So we have the following table of processes , where A, B and $\Gamma$ are the resources.

Here is a pic that i drew with the processes and the resources.

So the exact question is this: Using banker's algorithm, calculate the minimum values of $x$ and $y$ in order the system is Deadlock free.

I have done pretty much huge paper work and found that $x,y$ should be the numbers 2 and 3. But in order to find this I run the algorithm on paper several times ; for $[x,y] = [0,0],[0,1],[1,0],[1,1],[1,2]$ etc. until I found that for pair $[x=2, y=3]$ the system is deadlock free!

So, I think that I am missing the point. All this took me like 1 hour or so. Is there a simple method with less paperwork?

Thanks a lot in advance!

A "shortcut" to the solution; first calculate the NEEDED = MAX - ALLOCATEDresources:

    ALLOCATED MAX      NEEDED
    A B C     A B C    A B C
P1  0 1 0     7 5 3    7 4 3
P2  2 0 0     3 2 2    1 2 2
P3  3 0 2     9 0 2    6 0 0
P4  2 1 1     2 2 2    0 1 1
P5  0 0 2     4 3 3    4 3 1

AVAILABLE: x y 2

In order to complete P1 we need 4 Bs. But if you observe the column B of ALLOCATED, we see that we can only gain a single B if P4 is executed before P1. So whatever the execution order is, we need more than 3 new Bs (y >= 3).

Furthermore in order to complete P3 we need 6 As, but if you look at column A of ALLOCATED, we see that we can only gain 4 Bs if P2 and P4 are executed before P3. So whatever the execution order is, we need more than 2 new As (x >= 2).

So we have:

AVAILABLE: 2+x' 3+y' 2

and we can start completing processes that need less than (2 3 2) (P4 and P2)

P4: (2 3 2) - (0 1 1) + (2 2 2) = (4 4 3)
P2: (4 4 3) - (1 2 2) + (3 2 2) = (6 4 3)
now also P3 can be completed:
P3: (6 4 3) - (6 0 0) + (9 0 2) = (9 4 5) which are enough resources for
both P1 and P5

So the state is safe even with x'=0 and y'=0 and the solution is x=2, y=3

For $[x,y] = [2,2]$, we get the result. Therefore the minimum is $[x,y] = [2,2]$.
We get the correct sequence as
$P_3 P_4 P_1 P_2 P_0$ is the safe sequence with $[x,y] = [2,2]$.


What does the symbol "::" mean in computer science? What does the symbol $::$ mean in the following statement?

$\forall{x}\in K :: x \longrightarrow x$

A cycle in a graph is a path that starts and ends on the same node.
Clearly, if nodes in K lie on a cycle, then $\forall{x}\in K :: x \longrightarrow x$.

Look at page 56 in the following.

https://books.google.co.in/books?id=nel4vdeLcqkC&pg=PR7&source=gbs_selected_pages&cad=2#v=onepage&q&f=false

It is a delimiter between to parts of expression. You can think of it as notation for the English phrase 'such that'.
Read your formula as $`` \forall x\in K \text{ such that } x \longrightarrow x"$.


Master method recurrence question This is specifically a question pertaining to solving reccurences via the Master Theorem/Method, particularly for a specified $f(n)$ (as denoted below).

For a recurrence of $$T(n) = a T(\frac{n}{b}) + f(n)$$

where f(n) is $\Theta{(n)}$, would we be comparing $n^{\log_b(a)}$ with $n^{1}$ - meaning we would be comparing $log_b(a)$ with 1? Since the rate of growth is linear?

what about where f(n) is $\Theta{(1)}$ (aka some constant?), would we be comparing $n^{\log_b(a)}$ with $n^{0}$? '0' since there is no rate of growth for a constant?

I think the question is asking how to translate $f(n)$ into Big-Theta notation to be used for the Master Theorem. You have the right idea about switching between notations.

Another way to write the Master Theorem is as follows:

$T(n) = aT(n/b) + \Theta(n^d)$

So, yes, if you have a linearly growing function, then $f(n)$ may be substituted with $\Theta(n)$.

Then you may proceed with your comparisons.


Can a Turing machine decide the language $L_\emptyset$ of machines with empty language? Let $$L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\}.$$
Is there a Turing machine R that decides (I don't mean recognizes) the language $L_\emptyset$?

It seems that the same technique used to show that $\{A \mid A \text{ is a DFA and } L(A)=\emptyset\}$ should work here as well.

By marking, you probably mean reachability analysis - looking for a path from the initial state to an accepting state. Indeed, the language of a DFA is empty iff there is no such path.

Let's start with an example as to why this fails in TMs. Consider a TM that, in $q_0$, ignores it's input, but writes $a$ on it's tape, moves the head right and goes to state $q_1$, then in $q_1$ it again ignores the input, writes $a$, moves the head left and goes to $q_2$. In $q_2$, if it reads $a$, then it writes $a$, moves the head right and goes back to $q_1$.

That is, the machine just writes $a$ and alternates between two states ($q_1$ and $q_2$) and always has two adjacent $a$'s on the tape.

We now add a transition from $q_2$ that when reading $b$ goes to an accepting state and halts.

The language of this machine is empty. Indeed, the run always gets stuck in the $q_1-q_2$ loop, and will never get to the accepting state. Yet, there is a state-path to an accepting state. So what went wrong?

Well, intuitively, the ``state'' of a TM is not informative enough to describe the continuation of the run. In order to have all the information, you need the configuration of the TM, which includes the state, the position of the head, and the contents of the tape. If you find a configuration-path (which is called a run) to an accepting configuration, then indeed the language is non-empty, and it is an iff condition.

The problem with using reachability analysis on the configuration graph, is that it may be infinite. This is why deciding language emptiness is undecidable.

This is also why language non-emptiness is recognizable - you can perform a BFS on the infinite configuration graph. If there is a path to an accepting state, you will find it eventually. If there isn't, however, then you may get stuck in an infinite search.

E={ | M is a TM and L(M)=Φ}. Is E Turing-recognizable?

E is a language, to accept language E we construct a Turing Machine. Suppose we create a Turing EM for the language E.

EM will be provided as input the encoding of another Turing machines, If that inputted machine M accepts an empty language then it will be a member of language E, else it will be not a member of language.

Suppose we have a Turing Machine M, we need to check if it accepts an empty language. Turing Machine EM have M and strings eps, a, b, aa, bb, ..... EM will check if M can reach a final state for at least on a single input, and if it accepts at least a single input it will be discarded and not included in language E.
Now, see a possibility T.M M gets into a loop so M will keep on running and we couldn't decide whether it can accept or can't accept anything.
Hence, this given language E is NOT RE.

PS: I think the complement of this given Language E will be RE.


Relational algebra and indexes How might indexes be represented in the context of relational algebra?

How would an optimizer transform a query to use indexes?

Indices must not appear in relational algebra. That is because relational algebra is just a formal language which describes what you must do, but not how you must do it.

It is comparable to the multiplication and other operations of the elementary arithmetic.
There is a definition of what multiplying is but not of the way how you have to do it. There are several algorithms to multiply two numbers but the results are all equal. For further information see Wikipedia (What does it mean to multiply two natural numbers?).

Relating to your question that means that the result of an operation is the same with or without indices. The only difference is the increasing performance if you use indices.

@Elastic Lamb's answer is so terribly wrong in so many ways, I have to respond.

Relational Algebra is a practical/executable implementation of a system of logic, expressively equivalent to First Order Predicate Logic. In FOPL, you can state truths about the subject matter -- that's the what. RA corresponds to FOPL and -- exactly -- formulates the how. That's exactly the purpose for RA established by Codd's Theorem at the dawn of Relational Theory 1972

As well as truths like 'Employee E123 works in Department D456 ...' -- that is represented by a tuple in the Employee relation; or 'Employees in Departments D450 to D459' -- a query; you can state truths like 'Employee number uniquely identifies an Employee'; 'for all Employees, the Department each works in must be uniquely identified by a Department number which has a name'.

Those what we might call 'structural' truths are typically expressed in the database schema; and you can see those example truths express keys (uniqueness contraints/Functional Dependencies) and foreign keys (Inclusion Dependencies). Constraints/Dependencies are merely queries that return a Boolean result, and must always return True for the database content to be valid according to the business rules expressed in the schema.

So a practical implementation of RA would build indexes for rapidly validating updates, and give faster response to queries (which typically JOIN across FKs).

Most SQL engines under the hood convert your query to an algebraic form much more like RA. Then they can transform the RA expression using well-known equivalences; and how to transform will depend on what indexes are available, together with statistics about the content of relations and the clustering of keys around indexes. You can see that in practice by getting the query engine to explain its query plan. RA is crucial to the how, because SQL is not an algebra, not structured, barely a language.


NLP: Automatically categorize words semantically into non-predefined classes I am looking for a method to categorize a given word into semantically into classes. A simple example would be:

chair -> furniture

The most reasonable way to do so that comes to my mind, would be to create a tree containing words, where chair is a predecessor of furniture. Then one could define a threshold that describes the level of the tree predecessor that should be taken as the result.

Is there some existing research/tools or even trees that fulfill the described task? I cannot find anything in google because I do not know the specific term for my problem. Keyword Clustering as a technique seems a little different, because is works on existing data and return multiple matches.

You're looking for Wordnet https://en.wikipedia.org/wiki/WordNet ...


In the "tall cache assumption" what does $\Omega$ represent? Within the field of cache-oblivious algorithms the ideal cache model is used for determining the cache complexity of an algorithm.  One of the assumptions of the ideal cache model is that it models a "tall cache".  This is given by the statement $Z = \Omega(L^2)$.  Where $Z$ is the size of the cache and $L$ is the size of the cache line.  What does $\Omega$ represent?

It's the lower bound counterpart to O($\cdot$). Z is larger than some constant times $L^2$

It's called "asymptotic lower bound" - https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-omega-notation