How are userland programs executed? Say we have a simple OS with a filesystem, and some programs on that filesystem. How then does a program get executed by the OS?

My understanding is that the executable file gets loaded into memory, but after that I'm a little fuzzy. I understand the OS creates a process, but I'm not sure exactly how it works. How does the OS tell the machine code to run, and how does the scheduler interact with the program to start, pause and resume execution per scheduling policy?

Obviously, with the various forms of operating systems out there, this process can vary (and in some cases, be completely different) but this outlines a general overview.

Step 1: Load the program into memory.

This is pretty basic; grab the contents of the program and load it into memory. Depending on how memory is managed by the operating system and the platform, additional steps might be required. These could include configuring the memory page where the program is loaded to permit code execution as well as mapping page(s) to the application's initial stack.

Also, many operating systems won't load the entire program into memory immediately; they'll often allocate physical pages and load parts of the program into memory on-demand. This is generally an implementation detail that's transparent to the process, though.

Step 2: Begin executing the program.

Once the program is loaded into memory, the operating system will create whatever internal structures are required to manage the process (such as a struct task_struct in Linux) and do any other necessary bookkeeping. When that's through, the operating system will locate the program's entry point (often a main function or similar) and direct the processor to start executing the program at that location.

An operating system will usually start a new process in response to an interrupt (generally a system call of some sort) so in order to return to user mode, where the process will execute, a "return from interrupt" instruction (such as iret in x86 assembly) is typically used to restore the system state prior to the interrupt.

Step 3: Give control to another process.

This part depends heavily upon the multitasking architecture of the operating system, if it even supports multitasking. (If it doesn't, skip ahead to Step 5.)

Step 3a: (Preemptive Multitasking) Suspend the process after a short while.

In a preemptive system, a scheduler allocates a small timeslice for each running process. This timeslice is enforced by a system timer, which will fire an interrupt once a process's time is up. The interrupt will transfer control back to the kernel.

Step 3a: (Cooperative Multitasking) Wait for the process to give up control.

Cooperative systems depend on individual processes to manually give control back to the operating system on a regular basis. Of course, if a process misbehaves and doesn't return control, it would hang the operating system.

Step 3b: Save the relevant state of the process.

Once the operating system has control back from the previously executing process, it saves whatever state is necessary to return to the process at a later time. This includes the address of the next instruction the process would have executed, as well as some or all of the processor registers.

Step 4: Return control to the process.

When it's time to resume the process, the operating system will do the reverse process of the previous step; it will restore the processor registers and start executing code where the process previously left off. Like when a process is started, this is often done with a "return from interrupt" instruction. In a preemptive system, the operating system will also start the timeslice clock again.

Step 5: Handle a process's exit.

Once the process has completed its task, it will return control to the operating system for the last time by exiting. Often, the process will provide the operating system with some exit data; the operating system can do whatever it wants with this exit data. That could include notifying the process's parent of the exit, logging the completion of the process, or any number of other things. Once that's all said and done, the operating system will remove its record of the no-longer-running process and (generally) free the memory and resources the program had allocated during its execution.

Again, your mileage may vary depending on what operating system and platform you're working with. They come in all shapes and sizes, and they all work differently.


A flawed theorem about regular languages I am struggling with this question for a very long time and just can't find the flaw. So I am given a false Theorem:

The language $\{awwa \mid w \in \{a,b\}^* \}$ is regular.

Well, that part is obvious, we can prove that the language is not regular using the pumping lemma.
The question I am asked is to find the flaw in the "proof" for this theorem:

Let
$\qquad L_1 = \{ aw \mid w \in \{a,b\}^* \}$
$\qquad L_1^R = \{ wa \mid w \in \{a,b\}^* \}$
Let $L_2 = L_1 L_1^R = \{ awwa \mid w \in \{a,b\}^*\}$ be even-length palindromes that begin and end with an $a$.
Since $L_1$ is regular, and the class of regular languages is closed under reversal and concatenation, we conclude $L_2$ is also regular.

Can you find the flaw? I could build a DFA for $L_1$ and $L_1^R$, so I know they are regular. And regular languages are closed under reversal and concatenation.
But, however, $L_2$ is still not regular, so where is the mistake in the "proof"?

The concatenation of $L_1$ and $L_1^{\mathrm{R}}$ is not $\{awwa\mid w\in\{a,b\}^*\}$.


Is a single string enough to prove regular expressions inequivalent? Which of the following regular expressions generate a language that is different from the rest?

  (a+b)$^*$a(a+b)$^*$(a+b)$^*$
  b$^*$ab$^*$a(a+b)$^*$
  (a+b)$^*$ab$^*$ab$^*$
  b$^*$ a(a+b)$^*$ab$^*$

RE 1 generates a language that contains the string 'a' which no other language among 2,3,4 contains, so can I say this language is different from all others?  Does it suffice to show that a single string is not present in the language and hence its different from the rest?

Does it suffice to show that a single string is not present in the language and hence its different from the rest?

Yes. It's actually a very neat proof.

Formally speaking, you have found $w \in \{a,b\}^*$ with $w \in L_1$ but $w \not\in L_2,L_3,L_4$. That is sufficient to show that $L_1 \neq L_2$, $L_1 \neq L_3$ and $L_1 \neq L_4$.

You have not shown that $L_2 = L_3 = L_4$. The phrasing of the question seems to suggest as much (MC questions are boring!) but you may want to prove that as an additional exercise.

   Hint: Translate into NFA, determinize, minimize, check for isomorphy.


Definition of “infix” in formal languages I've got a simple question:

Let's say we have the following definition of a language over some alphabet: $L = \{w \mid w \text{ contains the infix } aab\}$

Does that mean $aab \in L$? or does "$aab$" have to be "wrapped" on both sides by other letters?

Yes, if $A$ is the alphabet, then $L = A^*aabA^*$.

Now, what about terminology?
Lothaire in the first chapter of his book Combinatorics on words gives the following definitions. A word $v \in A^*$ is said to be a factor of a word $x \in A^*$ if there exist words $u, w \in A^*$ such that $x = uvw$. A factor is proper if $v \not= x$.

In my opinion, the word infix is also perfectly fine, since it gives a natural counterpart to prefix and suffix. Terms involving "sub" like subword and substring are also frequently used in the literature. I personally prefer to follow Lothaire and say that a word $v \in A^*$ is a subword of a word $x \in A^*$ if $v = a_1a_2 \cdots a_n$ (where $a_i \in A$ and $n \geqslant 0$) and there exist $y_0, ..., y_n \in A^*$ such that $x = y_0a_1y_1a_2 \cdots a_ny_n$. This definition makes the term subword a synonym of subsequence, which I find quite natural.

Anyway, with so many different terminology around, it is not a bad idea to remind the reader of precise definitions if there is any risk of ambiguity...


This doesn't seem like a valid regular grammar; my instructor says it is The following is a screenshot of a lecture slide from my programming language concepts course:

According to Wikipedia and other sources, a regular grammar is one that is either left linear or right linear, meaning it has at most:

one nonterminal symbol on the left end of its right hand side

e.g., A -> Ba

one nonterminal symbol on the right end of its right hand side

e.g., A -> aB
But if we follow this definition, then the "regular grammar" in the screenshot above isn't really a regular grammar because it has two nonterminal symbols on its right hand sides.
My teacher argues it "technically" is because:

Identifier -> Identifier Letter

is "essentially" the same as writing multiple things like:

Identifier -> Identifier 'a'
Identifier -> Identifier 'b'
...

More generally, my instructor says that if a grammar's production rules can be reduced to a form where they have at most one nonterminal symbol, then that grammar is regular. To me, this doesn't seem correct—because then essentially, just by substitution, we can reduce any grammar we want to a regular form. And it seems to destroy the definition/restriction imposed on regular grammars, which is that they may have at most one nonterminal.
Could someone please clarify whether this is in fact a valid regular grammar?

Your teacher is wrong, unless of course s/he does not adhere to the wikipedia definitions. It is "technically" equivalent to a regular grammar, but that is not a well defined concept. What can we allow as extensions that give us "technically" regular grammars.

There is a concept that is perhaps suited. That is self-embedding. A variable $A$ is self-embedding if $A\Rightarrow^*uAv$ for non-empty $u,v$. A grammar is non self-embedding if none of its variables is self-embedding. Every non self-embedding context-free grammar has an equivalent regular grammar, which was already observed by Chomsky. With this concept we extend the regular grammars, while we are certain to stay within the regular languages.

And, since you are asking more details, your instructor is wrong again on the single nonterminal remark. Such grammars also include $S\to aSb\mid \varepsilon$ for which every sentential form has (at most) one nonterminal, but for which the language is non-regular. In fact these languages are called linear, and form a family between regular and context-free.

Note that $S\to AB, A\to aA|\varepsilon, B\to Bb|\varepsilon$ defines a regular language (mixing leftmost and rightmost). On the other hand $A\to aB\mid\varepsilon, B\to Ab$ is nonregular. This exemplifies the non self-embedding distinction.


Expected behavior in the min max random assignment problem Consider the standard assignment problem: $n$ people are assigned to n jobs (one person to one job) so to minimize the sum of costs. When the costs are generated randomly (using the exponential (1) distribution), it is known that the expected sum of costs is $\pi^2/6$.
An alternative solution to the assignment problem is to choose an allocation that instead minimizes the largest cost incurred by any individual, in the spirit of the John Rawls fairness criteria. Is it known what is the random sum of costs in the random version of the problem?

See Michael Z. Spivey, "Asymptotic Moments of the Bottleneck Assignment Problem," Mathematics of Operations Research, 36 (2): 205-226, 2011.


Defining the halting problem for non-deterministic automata The primary definition of Turing machine (TM), at least in my own reference
textbook (Hopcroft+Ullman 1979) is deterministic.

Hence my own understanding of the halting problem is primarily for
deterministic TM, though I am aware that it may be considered for other kinds of automata.

I also noticed that determinism is often more or less implicit in the way
people often refer to TM or to the halting problem. The wikipedia page
on the halting problem is a good example of that.

But, there seem no reason for such a limitation. Given a family
$\mathcal F$ of automata that can be non-deterministic, the halting
problem for $\mathcal F$ may be defined as:

  Is there a uniform decision procedure such that, given an automaton $A\in\mathcal F$ and an input $x$, it can decide whether there is a
    halting computation of $A$ on input $x$.

(This is not quite the same as saying that the computation of $A$ with input $x$ will terminate.)

Indeed, that seem the only way to give some sense to discussions about
the halting problem for Linear Bounded Automata (LBA) which are
primarily non-deterministic automata.

So my question is whether I am correct, and whether there is a reason (and which reason)
for this apparently second class treatment of the halting problem for
non-deterministic automata.

There are a few reasons I think we put less effort into  the Halting problem for non-deterministic models.

The first is that there are, in fact, two relevant halting problems for a ND model. Given an input $x$ and a non-deterministic machine $M$:

Does there exist a valid run of $M$ on $x$ which halts?
Does there exist a valid run of $M$ on $x$ which doesn't halt? i.e. do all valid runs halt?

For deterministic machines, these are identical, since there is exactly one valid run of $M$ on an input $x$. But for non-deterministic machines, there might be multiple runs. Which one you're interested in depends on your application.

Secondly, non-deterministic models are already unrealistic: they assume that you either have a magical box telling you which path to take, or that you have some form of infinite parallelism. Since non-deterministic and deterministic Turing Machines are equivalent in power, in most cases you just convert the machine into a determinstic one before you worry about halting.

As an extension of this, we don't care because proving something about a non-deterministic machine is at least as hard as proving something about an equivalent deterministic machine. We already know that there's no solution to the deterministic Halting Problem, so all it's really useful for is proving other problems undecidable through reductions. And it's always going to be less work to reduce to the deterministic halting problem, since it's easier than it's non-deterministic counterpart.


In RSA, must $p$ and $q$ have the same number of bits? Is it necessary to take the same bit size of "p" and "q" in case of RSA algorithm? i had read that  bitsize of p and q must be same. BUT after calculating, i found that bit size could be different also. But time complexity will increase. Can anyone help me?

The RSA method works regardless of the size of the individual primes $p,q$. The reason that we would want $p$ and $q$ to be of roughly equal size is that one method of breaking RSA is factoring $n = pq$, and the running time of some factoring methods (notably ECM, the elliptic curve method) depends on the size of the smallest prime factor of $n$. Therefore to get the most "bang for the buck", you would like $p,q$ to be both as large as possible under the constraint on the size of $n$ (which determines the speed of encryption and decryption), and so of roughly equal size.


Can I use the set of "used arguments values" as a memoization key for a deterministic function? I have a deterministic function $f(x_1, x_2, ..., x_n)$ that takes $n$ arguments.

Given a set of arguments $X = (x_i)$, I can compute $U_X = \{ i \in [1, n] : x_i \text{ was read during the evaluation of } f(X) \}$

Would it be valid to use the set $K_X = \{(i, x_i): i \in U_X\}$ as a memoization key for $f(X)$?

In particular, I am worried that there may exist $X=(x_i)$ and $Y=(y_i)$ such that:

$$
\tag1 U_X \subset U_Y
$$
$$
\tag2 \forall i \in U_X, x_i = y_i
$$
$$
\tag3 f(X) \neq f(Y)
$$

In my case, the consequence of the existence of such $X$ and $Y$ would be that $K_X$ would be used as a memoization key for $f(Y)$, and would thus return the wrong result.

My intuition says that, with $f$ being a deterministic function of its arguments, there should not even exist $X$ and $Y$ (with $U_X$ a strict subset of $U_Y$) such that both $(1)$ and $(2)$ hold (much less all three!), but I would like a demonstration of it (and, if it turns out to be trivial, at least pointers to the formalism that makes it trivial).

As long as $f$ is deterministic and depends only on its arguments (not on other global variables), yes, you can safely use that as a memoization key.  The bad case cannot happen.

You can see this by thinking about what happens as it reads the $t$th argument and using induction on $t$.  Let $i_1,i_2,i_3,\dots,i_t$ be the sequence of argument indices read (i.e., $f$ first reads $i_1$ when running on input $x$, then reads $i_2$, etc.).  For each $t$, if $f(x)$ and $f(y)$ have behaved the same up until just before they read the $t$th of these, then the next index examined by $f(x)$ and $f(y)$ will be the same, say $i_t$; if additionally $x_{i_t} = y_{i_t}$, then it follows $f(x)$ and $f(y)$ will behave the same up until just before they read the $t+1$st of their arguments.  Since $i_t \in U_X$, $x_{i_t} = y_{i_t}$ is guaranteed by your assumptions. Now use induction.

This assumes everything is deterministic.  For instance, $f$ had better not be allowed to read a random-number generator, the current time of day, or other global variables.  Beware that on some platforms there can be surprising sources of non-determinism, e.g., due to aspects of behavior that are unspecified and might depend on external factors.  For instance, I have a recollection that floating-point math in Java can introduce non-determinism in some cases, and so if you want to write code that is verifiably deterministic, you probably want to avoid all floating-point math.


What is the difference between a block and a procedure? A procedure is a sequence of program instructions that perform a specific task, packaged as a unit (Techopedia).

We use block structure to make our code more readable by using indentations and spaces.

Now, is one block the same as a procedure and is vice versa true?

In programming languages I 've seen, they are not the same.

A procedure (or function) definition is a block of code with a header, that specifies 0 or more arguments, and a name. It allows the procedure to be called by specifying its name and a list of argument values. In many languages, anonymous functions or procedures can be defined, which have a block of code and a header with arguments, but no name. In some languages, a block can act as an anonymous procedure or function without arguments; in other languages, it cannot.

For instance, in C, Java and C#, a block just serves to group statements and create a scope for local variables; it cannot be used as a procedure/function.

In Perl, on the other hand, blocks can be used in contexts that expect procedures/functions (subroutines), and in PostScript, a block denotes a code object (a procedure) that can be bound to a name.

I've never used blocks in Lisp, but apparently, the situation is much the same there: a Lisp procedure (function, in Lisp) contains a block, implicitly, but a block by itself does not constitute a procedure. It cannot be called by giving its name and values for its arguments, if I understand correctly.


Decoding cyclic code, assuming we have no errors Assuming the coded data is errorless and given generator polynomial coefficients. By what algorithm can I decode the data coded by matrix constructed by given generator polynomial?

Let us start with generator matrix $G$, a matrix of $k$ rows and $n$ columns where $n\ge k$. Given any input row vector $s$ of $k$ characters, we can generate the codeword for $s$, a row vector of $n$ entries by
$$w=sG$$
If given $s$, how can we get back $w$? Suppose we can find a matrix $G'$ of $n$ rows and $k$ columns such that
$$GG'=I_k$$
where $I_k$ is the identity matrix of $k$, we will have
$$s=sI_k=s(GG')=(sG)G'=wG'$$

So the question becomes how to find such matrix $G'$ from $G$. You should be able to find in your course material the procedure or technique to accomplish that. Note that $G'$ is not a square matrix. In general $G'$ is not unique, either.

Now suppose you are given a generator polynomial instead. You can form the generator matrix from the generator polynomial and proceed as above. There might be a shortcut procedure for generator polynomial because of its special form.


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.


Information Systems (IS) and Data Warehouse I'm working on a research project about the adoption of DWH systems and doing some literature review I find many documents that refer to Information System. I tried to find the right definition of information system and if a data warehouse can be considered an IS or not, or is just a subset of it.
In the wider definition IS comprises also persons and policy and not only the technology (software or hardware). So it become complicated in my opinion to define it. From my personal work experience a DWH is an IS, the hearth of IS. But what about from the academic and computer science point of view?
If any system with data can be an IS, the extent is that an spreadsheet might be considered as an IS.

Yes, I'd say that a data warehouse is an information system.  It stores information, using information technology; it's an information system.

That said, I think focusing too much on trying to obtain a precise definition of "Information System" and "Data Warehouse" is not likely to be super-helpful.  Those are just phrases.  "Information system" is a broad phrase that doesn't have an especially precise definition -- it gets used in whatever way the author finds helpful.  And that's OK.  It doesn't need a precise, universally-agreed-upon definition.  It's just an aid to communication.  Ultimately, it just doesn't matter that much how we classify data warehouses; if I told you they are (or aren't) an information system, that wouldn't really change how you should think about them.

My advice would be not to worry too much about terminology and trying to classify things into some taxonomy.  Instead, think about what are the relevant characteristics and properties of the kinds of data warehouse systems you are looking at.  Figure out what is your actual goal, and then identify what characteristics are relevant to that goal, and use that to hone in on the aspects of the system that are relevant.  Not all information systems are alike -- the range of issues that arise in information systems is incredibly broad.


Increasing entropy of random walk Let $P$ be a transition matrix of a random walk in an undirected (may not regular) graph $G$. Let $\pi$ be a distribution on $V(G)$. The Shannon entropy of $\pi$ is defined by

$$H(\pi)=-\sum_{v \in V(G)}\pi_v\cdot\log(\pi_v).$$

How do we prove that $H(P\pi)\ge H(\pi)$ ?

Is this even true? Consider an undirected graph which is a star. That is, a central vertex $V_0$ is connected to all other vertices $V_1, V_2, \dots, V_{n-1}$, and there are no other edges in the graph. Then, if you start with an equal distribution on $V_1, V_2, \ldots, V_{n-1}$, after one step all the weight is on the central vertex $V_0$. So in one step the entropy has gone from $\log (n-1)$ to $0$.


Good "serializer" ADT implementations for Synchronization I am looking for a library which provides a "serializer" ADT for synchronization.
(http://courses.cs.vt.edu/~cs5204/fall99/Summaries/Concurrency/serializers2.html)

Googling leads me to nowhere, unlike monitors,semaphores and other constructs, serializers are hardly discussed over the web in depth.

Any other pointers are welcome. :)

This is the first I've ever heard of serializers, and I don't know of any libraries that implement them.  From reading the course notes you pointed to and the paper by Hewitt and Atkinson referenced in the course notes, there seem to be two differences between serializers and monitors.  The first is that serializers have a more "elegant" but less efficient way of waiting for invariants to become true, the second is that a notion of reader/writer locks seems to be built-in to serializers, but wasn't built in to the original notion of monitors.

The present-day conception of a monitor largely follows Lampson and Redell. "Experience with processes and monitors in Mesa," Comm. ACM 23(2):106-117, 1980.  A monitor is an object (some private data with public methods that act as the interface to the abstract data type that the object implements) with a private mutex.  Every public method starts by acquiring the mutex, and releases the mutex on exit.  In Java this would be equivalent to marking every public method "synchronized".  In C++11 this would be equivalent to declaring a private mutex, m, and having every public method begin with a declaration std::unique_lock<std::mutex> lock(m) (an RAII-style critical section).

While in monitors the notion of condition variables is explicit, in a serializer the condition variables are implicit in the enqueue...until statement.  In a monitor you could implement something similar by associating a condition variable, cv, with each monitor.  Then the enqueue...until (<invariant-test>) statement is written cv.wait(m, []{return <invariant-test>;}) (that's C++ syntax for an anonymous function that returns true when the invariant is satisfied.)  And you would then need to make sure that you cv.notify_all() at the end of each public procedure (in C++ I would do this by subclassing unique_lock, giving it a destructor that calls cv.notify_all() in addition to releasing the mutex.)

Finally, the serializer has this bizarre join_crowd/leave_crowd operation.  It took me a while to figure this one out, but as best I've been able to determine it is a slightly weird way of implementing a reader-writer lock.  In a serializer when you want a reader-lock you join the crowd and you release the reader-lock by leaving the crowd.  (The "crowd" is the set of readers.)  I think monitors make this operation much clearer.  You can protect a monitor by a reader/writer mutex instead of a normal mutex.  The rule for when you can acquire the read lock instead of the write lock is completely clear in monitors: a method that does any mutation of the data structure must be protected with a write-lock.  Only if the method is completely immutable (const in C++ parlance) can you protect it with the read-lock.  (Note though that C++11 didn't include reader/writer locks for very good reasons, so if you wanted to do this in C++ you'd need to use Boost's reader/writer locks.)

I can hazard some guesses about why serializers never got much notice.  The first reason is that they were proposed by Carl Hewitt, who was the primary proponent of the Actor model of concurrent programming, and the Actor model uses different terminology than most people in the systems programming community are used to.  The second reason is that the serializer enqueue...until statement requires you to add a notify_all() at the end of each public method.  This in turn causes every thread waiting on an invariant to wake up and retest its invariant.  Standard condition variables allow you to put notify_one() statements only where they are actually useful, which can lead to real performance benefits.  Finally, it is not clear (to me) how to use the join_crowd/leave_crowd operation correctly, while it is at least easy to state what you must not do with a reader/writer lock (and even then reader/writer locks are one of the most common causes of bugs in multi threaded programs, so who knows what horrors would have been perpetrated in a world where serializers were standard practice.)


Find two numbers in array $A$ such that $ |x-y| \leq \frac{\max(A)-\min(A)}n$ in linear time I'm struggling with the following question:

  Let $\langle a_0, a_1,\dots,a_n\rangle$ be a sequence of real numbers, and  let $ M =
\max\{a_0, a_1, .... a_n\} $ and $ m = \min\{a_0, a_1, .... a_n\} $.

  a. Prove that there are two numbers in the sequence $x,y$ such that $ |x-y| \leq
 \frac{M-m}n$.

  b. Write an algorithm that finds those numbers in linear time.

I've manage to prove part a, but am struggling with part b. I've tried to find a way to find the two element in the array that have the smallest difference, but couldn't find a way to do it in $\Theta(n)$. It should be something related to select algorithm and medians.

This is an interesting question.

Here is an algorithm.

Iterate through the array to obtain $m$ and $M$. If $m=M$, we are done. Otherwise, let $\delta=\frac{M-m}n$.
For $i=0,1,\cdots,n+1$, let $L_i$ be an empty list of numbers.
Iterate through the array again. For each $a_j$, if $\lfloor (a_j-m)/\delta\rfloor=k$, then append $a_j$ to $L_k$ and $L_{k+1}$.
Iterate through $L_0, L_1, \cdots, L_{n+1}$. Skip $L_k$ if there is at most one number in it. Otherwise process $L_k$ as follows.

If there are two numbers, compute their difference. If it is not more than $\delta$, we are done.
If there are three numbers or more, select arbitrarily three of them. Compute all three differences between each pair of them. There must be one pair of numbers whose difference is smaller than $\delta$. Select that pair and we are done.

It is not difficult to see the above algorithm is correct and its time-complexity is $\Theta(n)$.

The above algorithm could be sped up if $L_k$ or $L_{k+1}$ is processed just as in step 4 while we are still running step 3. It would be an interesting but hard problem to determine when will be the optimal time to start processing, assuming for example, $a_j$'s are uniformly and independently distributed in $[m,M]$. Starting from $a_{n//2}$ (or $a_{\lfloor n/\log n\rfloor}$ or even $a_{\lfloor n/\sqrt n\rfloor}$?) should improve the speed in general, I believe. However, the worst time-complexity cannot be better than $\Omega(n)$.

Instead of step 3, we could also put $a_j$ to $L_{k}$, $L_{k+1}$ and $L_{k+2}$ if $\lfloor 2(a_j-m)/\delta\rfloor=k$ and adapt step 2 and 4 accordingly.

It might be interesting how I found this algorithm. I literally recited Polya's principle, "do you know a related problem?". I recalled that finding duplicate elements in an array using hash table takes linear time of $n$. Could I apply that conclusion? Or the way of using hash table? What is a hash table and how can I create a hash here? If I can put nearby numbers in the same slot, I can considered them as the same, then the algorithm might work. The it dawned on me that I could use the location of $a_j$ as "its hash". However, two numbers that are very close could be mapped to different hashes, which breaks the promise. If one hash is not enough, how about two hashes? I could almost see the light on the other side of the tunnel. After a few minor adjustments, I arrived at the current answer. (Somehow I missed Yuval's nice method by divide and conquer, which, in hindsight, should not have been difficult to find.)

Motivated by Yuval's emphasis on randomization and practice, I would like to ask the following question.

Let $n+1$ numbers be (uniformly and) independently distributed in $[0,1]$. Is there an algorithm that finds two elements whose absolute difference is not greater than $1/n$ with sublinear average time-complexity? (I believe the naive algorithm that inserts $a_j$ into a (balanced) binary search tree works. Who has a proof?)


Recognizability of machines which halt in $n$ steps on some input We define the following language:
$$L = \{M \mid \text{$M$ is a TM and there exists an input $x$ on which $M$ halts in at most $|x|$ steps}\}.$$
Following this question I understand that $L$ is not decidable, but I know that it is recognizable, and therefore I'm looking for a reduction from the HALTING problem to $L$.
I thought of the following reduction:
On input $M$ for $L$, create a Turing machine $M'$ that for input $y$ for the HALTING problem runs $M$.
If $M$ halts, then $M'$ halts too, but I'm having problems proving the reduction.
Another way of proving this problem in my opinion is by building an $M'$ that recognizes the language by running $M$ all inputs for their length.
If $M'$ halts on some input it accepts, otherwise it keeps going.
Does this solution work?

This could be proven without reduction. The proof is straightforward: given $M$ run through all strings, say over $0$ and $1$, in canonical order and for each string $x$ simulate $M(x)$ for $|x|$ steps and check if it halts. If there is such $x$, then you will eventually find this $x$ and so accept $x$.


Does programming language detection need more input than natural language detection? I wonder which one of the two needs a larger input to achieve a decent accuracy:

programming language detection or natural language detection?

More details:

Definition of Language detection:

  In natural language processing, language identification or language
  guessing is the problem of determining which natural language given
  content is in. Computational approaches to this problem view it as a
  special case of text categorization, solved with various statistical
  methods.

The question I was asking can be written bit more formally as: let $x$ be a substring from some text $X$ written in natural language, and $y$ a substring from some source code $Y$ written a programming language. Assume a $X$ and $Y$ are each written in one language only (natural language or programming language).

Let $f(X)$ be the size of $x$ so that on average (i.e. trying on a bunch of different X) I correctly predict the language with accuracy $p$. Does $f(X) < f(Y)$ or $f(X) > f(Y)$ ?

Answering knowingly this question would require experiments. I am sure
there is some data for natural languages, where it is a common
problem. I recall from memory that one study gave ridiculously small
figures for natural language, which is not too surprising. If you take
5 consecutive word in a sentence (the figure I recall, without being
sure), there is a good chance that one of them belongs to a single
language, and even more that the fragment can syntactically belong to
only one language (parsing fragments without context is possible with
existing technology). To me the problem is not so much the size of the
input as the size of the recognition program and its data. There is a
compromise there. Actually my guess is that keeping all the relevant
data is far too costly, and that the actual techniques are statistical
ones, such as checking n-grams of letters. (see Wikipedia), which are
extremely effective.

Regarding programming languages, the problem is a bit different. The
size of the vocabulary is ridiculously small, and identifiers do not
give any indication (or very little with the allowed mophology: a
language could forbid to use dask inside identifiers, for example).
Furthermore, what fixed vocabulary there is (keywords) is often the
same in many programming languages.  However, programming languages
have a very strict syntax, which will certainly distinguish them
rather quickly.  It is not so much how long a fragment as the kind of
fragment. A long succession of assignments might look the same in many
programming languages. Buit I would not venture any figure, and I am
not even sure statistics would make sense.

Then there is the issue of parenthood. A fragment of Pascal may look
very much like a fragment of Algol 60 or Simula 67. Is American
English to be distinguished from British or Autralian English?

To conclude, without any hard knowledge on facts:

The problem should be stated with a word regarding the space cost (and
possibly time-cost) of the identification program.

Identification for natural language is essentially morphology or
lexically based, and will use statistical techniques if space costs
are to be acceptable. They can recognize fairly short sequences (a few
words as I recall) with good accuracy.

Identification for programming languages is essentially syntax based,
and probably needs larger fragments in number of tokens, in order to
have enough syntax substance, despite the intentional similarities
between programming languages. But it can probably be 100% accurate,
without excessive size of the identification program. I would however
be more confident if I had actual data to back my guesswork. I do not know of any work on this topic.

Considering only fragments is not an issue. It is obviously not an
issue when only lexical information is used. It is not an issue either
when syntactic information dominates, as the technology to parse
fragments is working well.

Afterthoughts, after the question was completed.

One minor remark concerns the concept of substring size: is it measured in
characters, in bytes, in lexical elements? Size of character encoding
is variable. Characters take diacritical marks. Lexical elements have
different average size in natural and programming languages.

A more important remark concerns the mode of measurement. Natural
language will use statistical methods to avoid the problem of natural
language huge specification. Hence the answer is accordingly accurate
with some probability that may depend on substring length (different
techniques produce different types of mis-detection).

In the case of programming languages, the specifications are small
enough that they can probably be used exactly. Hence the answer could
possibly be always 100% exact at acceptable cost. The problem would
not be with the detection procedure inaccuracies as in natural
language, but in the question itself. If a string does not
discriminate two languages because it can belong to both, no amount of
technology will help you solve the problem. In such a case, the
detection software should not guess, which would be meaningless, but it should just list, with a 100% accuracy, all the
programming languages the substring can belong to.

In other words, the case of natural language and the case of
programming languages are very different technically. I am not sure it
makes sense to compare them.


What exactly representational bottleneck in InceptionV3 means? I am trying to understand the concepts behind the InceptionNet V3 and got confused with the meaning of representational bottleneck. They said

  One should avoid bottlenecks with extreme compression. In general the
  representation size should gently decrease from the inputs to the outputs
  before reaching the final representation used for the task at hand.

and one thing I get from this is that we should not use polling or convolutions with large strides. But when I arrived in the section 5 (Efficient Grid Size reduction) they said that doing polling before the convolution violates that mentioned principle but doing polling after convolution don't violate.

Doing the left one we decrease the number of features by a factor of one quarter and then the features are doubled. In other words a decrease of 35*35*320*0.75 = 294K features and then an increase of 17*17*320 = 92.48K features. And doing the one in the right the features are doubled and then decrease by the same factor of one quarter. And doing this one, the real decrease in the pooling phase is bigger: 35*35*640*0.75 = 588K.

So, why one approach violates the principle and the other don't? What am I missing here?

Another thing that confused me is the solution found by them to avoid the computational cost of doing conv. before polling.

The polling part of the solution is not violating the principle of representational bottleneck once it make the exactly same operation with dimensionality reduction mentioned earlier?

Cool question! I managed to start thinking about its meaning thanks to your asking.

I believe you would like to consider it in the sense of information flow. As the information is compressed to a same size in both cases, the question is which one is more effective. Information with amount of 35*35*640 can flow through a wider pipe more freely. A pooling layer just prunes information directly in the left solution, while doing Inception in the right case expands the representation to a more sparse space and makes meaningful inferences before get pruned. Think of the pooling operation in left as a neck or a narrow path, and the middle representation in right as a broad lake. The pooling layer in right can also select better output since the source has more abstract (semantics) information.

As to figure 10, I consider it as a balance between the representation size and the computation burden.


Adaptive arithmetic coding confusion I'm confused about the point of adaptive arithmetic coding.
I understand that static arithmetic coding involves using preset probabilities of symbols that remain static during the whole process. I also understand that adaptive arithmetic coding involves change all probabilities after each symbol encountered.
However, what is the point of changing the probability after each symbol? Why wouldn't you just go through an entire file first and determine the probabilities and then do the arithmetic coding as a second pass?
Additionally, I don't understand how changing the probability of symbols impacts the compression? If we know the true probabilities of the symbols in the file we are compressing, then will it make the file smaller?

First, consider "going through an entire file". There are a few assumptions worth thinking about here.
Files can be very big, and traversing them twice can be expensive. This is one reason why most real-world compression standards are based around blocks or windows.
There are situations where you don't have "the entire file" to begin with, such as a communication channel. TLS (prior to 1.3, at least) supports compression, for example.
Files are not always homogeneous. Archives (e.g. tar) are a case in point. A statistical model that is appropriate for one part of a file may not be appropriate for another part. Adaptive coding adapts to this, too.
As to your final question, if both the encoder and decoder knew the true probabilities of the symbols in the file we are compressing, then that wouldn't need to be transmitted. And, indeed, we sometimes do this in the real world. The JPEG standard, for example, specifies default coding tables for those times when they are appropriate, and lets an encoder supply their own when they are not.
Transmitting a static coding table efficiently (i.e. compressing it) is a nontrivial problem, especially for a large code alphabet. For a well-designed scheme, the cost of transmitting the table should be equal to the "learning cost" of using an adaptive code.


Memoized Palindrome Subsequence I am trying to find the maximum palindrome sub-sequence and after going through some tutorials, I came up with a memoized version.But I am not sure about the runtime.I want to know if the following algorithm will work.Could also someone explain what the runtime will be?

Memoized-Palindrome(A,n)
initialize longest [i][j] =0 for all i and j
then return Memoized-Palindrome1(A,1,n,longest)

Memoized-Palindrome1(A,i,j,longest)
if longest[i][j]>0 return longest [i][j]
if (j-i) <=1 return j-i
if A[i]==A[j]
      then longest[i][j] = 2 + Memoized-Palindrome1(A,i+1,j-1,longest)
    else
      longest[i][j]= max(Memoized-Palindrome1(A,i+1,j,longest),Memoized-Palindrome1(A,i,j+1,longest)
return longest[i][j]

This kind of approach is more often called dynamic programming than memoization but they are, indeed, related.

In dynamic programming, however, you usually write the order in which your function is called. (This is one key difference between them.) In this case, you will clearly see that you will compute $n$ longest[i][i] first, then $n-1$ longest[i][i+1], then $n-2$ longest[i][i+2] etc. each computation being in constant time. Giving a complexity of $n+(n-1)+\dots+2+1$=$n(n+1)/2$ i.e. $O(n^2)$.


What if a formal grammar cannot be terminated? I'm currently in a class on Computability and we just finished looking at formal grammars before moving onto finite automata. We were given an several examples of a formal grammar, and one stuck out in particular:

V: { S, A, B, C }
T: { a, b, c }
P: {
    S -> aA | λ | ASA
   AA -> aA | a
}

My professor described the result as "any number of as". This makes sense if you never use the first S or AA rule; you can simply replace S with ASA as many times as you like, then replace each S with λ (getting some even-length string of As); you can then replace all AAs with as.

But what if I picked the first rule? So, I start with S, then replace S with aA. I now have a string that contains neither S, nor AA, so the final terminal string should be aA. (This could also be done with S -> ASA -> AA -> aA.)

Is this allowed? If so, what is the result called? Since it still contains a variable, is this just a rejected/invalid result?

NB: I did ask my professor about this. He explicitly said to "ignore the first rules of each 'S' and 'AA'", and could not give me any further explanation on why to do this.

When you are given a grammar $G$, then the language it produces, $L(G)$, is all the (finite) words it can generate. All the other "derivations" that don't yield any legal word, can be ignored.

For instance, for the grammar $G_1$:

  S -> SS | Sa | aS

the language that the grammar produces is $L(G_1)=\emptyset$, as no derivation ever terminates.


Which one of the following string is DCFL Is odd length pallindrome DCFL or NCFL?

Like

1) $L=\{w1w^R\mid w \in \{0, 1\}^*\}$

or

2) $S\rightarrow aSa\mid bSb\mid a$

or

Suppose odd length String like

3)$S\rightarrow aSa\mid bSb\mid aSb\mid bSa\mid a\mid b$

We get information about even length palindrome, that it can never be DCFL, but what about odd length?

Hint: The DCFL among the three alternatives is not only a DCFL, it is a regular language.

(Recall that the regular languages form a subset of the DCFLs.)

Hint no. 2: The other two alternatives are essentially the same language, only over different alphabets.


Reducing independent set to triangle-free subgraph The INDEPENDENT-SET problem is a well-known NP complete problem that takes in a graph $G$ and an integer $k$. It returns true if $G$ has an independent set of size $k$.

An instance of the TFS (triangle-free-set) problem takes in a graph $G$ and an integer $k$ and it returns true iff $G$ has a subset of size $k$ whose induced subgraph is triangle free.

I want to perform a polynomial-time reduction of IS to an instance of triangle-free-set. So I start off with an instance of INDEPENDENT-SET, and I want to reduce it to an instance of TFS. But I'm not quite sure how to do this. I tried many things, like adding additional vertices for each pair of vertices, but I don't think this is right. I also saw a similar question here: NP Complete Proof - Polynomial Reduction, but I cannot quite figure out the approach from just that one person's question.

I would greatly appreciate any help.

Let $\langle G=(V, E), k \rangle$ be an instance of Independent Set, and call $n=|V|$.
Let $N$ be a set of $n+1$ new vertices (not in $V$), and construct a new graph $G' = (V', E')$ where $V' = V \cup N$ and $E' = E \cup (N \times V)$.

If $G$ has an Independent Set $S$ of size at least at least $k$ then $G'$ has a Triangle-Free set $S'$ of size at least $n+k+1$.

Select $S' = S \cup N$.
To see that the subgraph of $G'$ induced by $S'$ is triangle free consider any triple $(a,b,c)$ of distinct vertices in $S'$.
Clearly, if more than one of $a$, $b$, and $c$ is in $N$, the triple cannot induce a triangle since $G'$ has no edges between vertices in $N$. On the other hand, if at least two distinct vertices $u,v \in \{a, b, c\}$ are in $S$, then $(u,v) \not \in E$ and hence $(u,v) \not\in E'$.

If $G$ has a Triangle-Free set $S'$ of size at least $n+k+1$ then $G'$ has an Independent Set $S$ of size at least at least $k$.

Let $S=S' \setminus N$.
Since $|S| \ge n+k+1$ and $|N|=n+1$, the cardinality of $S$ is at least $k$.
To see that $S$ is an Independent Set of $G$ notice that $S' \cap N \neq \emptyset$ and let $v \in S' \cap N$. Let $a$ and $b$ be any two distinct vertices in $S$. Since the subgraph of $G'$ induced by $S'$ is triangle free and $\{(v,a), (v,b) \} \subseteq E'$, we must have $(a,b) \not\in E' \supseteq E$.


Asymptotic notation and random variables I have two random variables $X$ and $Y$ and I want to bound the value of one in terms of the other (for now, I don't care about the actual distribution of their values).

Suppose that the two variables can have different distributions with values chosen from $[1, n]$. But $X$ is always upper bounded by $Y \cdot c\log{n}$ for some constant $c$. Can I write this as $X = O(Y\log{n})$ (if I care about the behavior for large $n$). I'm not sure what is the convention wrt to random variables and asymptotic notation.

On first look, the notation $X = O(Y\,\log{n})$ seems intuitively reasonable since $X$ is always upper bounded by $c (Y\,\log n)$ for some constant $c$. ($c$ must be positive since $X,Y\ge1$).
Can we formalize the exact meaning of that notation?
Here is one natural definition.

Let $(\Omega,S,T)$ represents a set of 2-dimensional random vectors on $\Omega$ parameterized by $n$, i.e., for all $n$, $(S_n, T_n)$ is a random vector from $\Omega_n$ (which is a set of possible outcomes) to ${\Bbb R}^2$. We write
$$S=O(T){\text{ as }}n\to \infty $$
if and only if there is a positive constant $c$ such that for all sufficiently large values of $n$, for all $\omega\in\Omega_n$, the absolute value of $S_n(w)$ is at most $c\,T_n(w)$.

We can apply the above definition to $(I, X, Y\,\log n)$ where $I_n=[1,n]$.


Is this a correct application of Rice-Shapiro theorem? Let $\langle M\rangle$ be the encoding of a Turing machine as a string over $\Sigma=\{0,1\}$, and consider the language $L=\{\langle M\rangle| \text{ $M$ is a Turing machine that accepts a string of length 2014} \}$
I want to use The Rice-McNaughton-Myhill-Shapiro Theorem (page 14 in this) to prove that $L$ is acceptable:
Say $\mathcal{L}$ is the set of all acceptable languages that contain strings of length 2014.

This set is monotone: every superset of a $L \in \mathcal{L}$ also contains strings of length 2014 so belongs to $\mathcal{L}$

This set is compact: for every language in $\mathcal{L}$ I can choose the finite subset with strings of length 2014.

This set is finitely acceptable: this is the part I'm confused about. Given every finite language of $\mathcal{L}$ is there a TM that can accept this set of finite languages?

The application of the theorem is not correct. Note that $\mathcal{L}$ is a set of acceptable languages, and consider your first point. If you take an acceptable language $L$ that contains a string of length 2014, then it is not necessarily that every superset of $L$ is acceptable.
Regarding the last point, the answer is yes. Given an encoding $\langle L\rangle$ of a finite language $L \in \mathcal{L}$, it is easy to check whether $L$ contains a string of length $2014$. Indeed, we're assuming that the encoding encodes all the words of $L$ in some order, so you can simply traverse the encoding to look for a word of length 2014. Specifically, quoting from the link you attached:

If $L$ is a finite language over $\Sigma$, then you can assume that $\langle L\rangle$ is the unique string over the alphabet $\Sigma \cup \{ \{,•,\}, \epsilon\}$ that contains the strings in $L$ in lexicographic order, separated by dots • and surrounded by braces {}, with $\epsilon$ representing the empty string. For example, if $\Sigma = \{ 0, 1\}$, and $L = \{\epsilon, 0,01,0110,01101001\}$, then $\langle L\rangle =  \{ \epsilon•0•01•0110•01101001\}$.

So given such an encoding as input, you can go over it and check whether there is an infix of legnth 2014 between two consecutive dots •.
Finally, you can simply show that $L$ is acceptable directly by defining a TM that accepts it. Indeed, you can simply simulate the run of $M$ on all strings of length 2014 in parallel, and accepts iff $M$ accepts at least one of them.


Does an RL agent need to experience a complete episode in order to learn? Suppose we have a game where there is no good measure of how "far" the target is (that we could use to nudge the agent towards the goal via the immediate returns).

If the agent gets only -1 reward per time step and experiencing a full episode where it reaches the goal is extremely improbable (it's equivalent to just blind search at this point), can it still learn?

If the agent gets no feedback whatsoever and has no information about the structure of the search space (just blind search, hoping to get lucky), then no, it can't learn.  It has nothing to learn from.  In your scenario, it has no information to enable it to improve: the feedback is always the same -- always an unending stream of -1,-1,-1,-1,-1,... unless it happens to get lucky.  Without feedback, there's no basis for learning.


Suggest a Data Structure To Manage 2 Sets I was given the following problem which really baffled me, and I would like some guidance in solving it.

I want to make a data-structure which represents two sets $A,B\subseteq \mathbb{R}$, so that I can Insert an element to a set of my choosing in $O(\log n)$ (where $n$ is the number of elements existing in both sets).

However, it is also required to be able to find in $O(1)$ some $x \in A\cup B$ such that the amount of elements in $A$ lesser than $x$, equates to the number of elements in $B$ greater than $x$, if exists:

$$\left | \left \{ y\in A: y<x \right \} \right | = \left | \left \{ y\in B: y>x \right \} \right |$$

Now the obvious direction is to use balanced trees (say AVL). I can use the same tree for both sets or separate to 2 different trees. I also presume I should store more data in the nodes, However I'm not sure which. I thought about storing the number of elements smaller and greater but that would make the Insert method $O(n)$, since I have to update many nodes in the respective tree.

You are on the right approach to attach "more data" to a balanced search tree.

For all $x\in A\cup B$, let $$d(x)=\left | \left \{ y\in A: y<x \right \} \right | - \left | \left \{ y\in B: y>x \right \} \right |,$$ which is an increasing function on $x$.

For simplicity, let us assume all elements are distinct first. We can use a balanced search tree $T$ to store all elements in $A$ and $B$, keeping track of whether each element comes from $A$ or $B$.

We will also store $(x_\ell, \delta_\ell)$ , where $x_\ell$ is the largest element $x$ in $T$ such that $d(x)\le0$ and where $\delta_\ell=d(x_\ell)$.
We will also store $(x_r, \delta_r)$ , where $x_r$ is the smallest element $x$ in $T$ such that $d(x)\ge0$ and where $\delta_r=d(x_r)$.

Either pair might not exist. However, at least one pair must be available, which is enough to identify the wanted $x\in A\cup B$, i.e., $d(x)=0$, if exists.

Suppose $v$ will be inserted into $T$. Here is a sketch of what to do to maintain the data structure. The idea is simply to move $x_\ell$ or $x_r$ to its neighbor one or two times.  Several obvious boundary cases such as when $d(x)>0$ for all $x$ in $T$ before or after $v$  is inserted have been skipped.

Insert $v$.
Update $(x_\ell, \delta_\ell)$ as the following.

Do the following.

find $x_{-1}$, the predecessor of $x_\ell$. Compute $d(x_{-1})$.
find $x_{-2}$, the predecessor of $x_{-1}$. Compute $d(x_{-2})$.
find $x_{1}$, the successor of $x_\ell$. Compute $d(x_1)$.
find $x_{2}$, the successor of $x_1$. Compute $d(x_2)$.

Let $x_{\text{new}}$ be the largest element $x$ among $x_{-2}, x_{-1}, x_\ell, x_{1}, x_{2}$ such that $d(x)\le0$. Update $(x_\ell, \delta_\ell)$ to $(x_{\text{new}}, d(x_{\text{new}}))$

Update $(x_r, \delta_r)$ similarly, which should take $O(\log n)$ time as well.

Any kind of balanced search trees can be used as long as the insertion, finding the predecessor and finding the successor can be done in $O(\log n)$. In particular, we can use AVL tree or red-black tree.

Step 1 takes $O(\log n)$ time.
Each search for predecessor or successor in Step 2 takes $O(\log n)$ time. Each computation of $d(*)$ takes $O(1)$ time, as we know $d(x_\ell)$. For example, $d(x_{-1})=d(x_\ell)-\lambda_A(x_{-1})-\lambda_B(x_\ell)$, where $\lambda_A(x_{-1})$ is 1 if $x_{-1}\in A$ and 0 otherwise. $\lambda_B(x_{\ell})$ is 1 if $x_{\ell}\in B$ and 0 otherwise. Similarly, $d(x_1)=d(x_\ell)+\lambda_A(x_\ell)+\lambda_B(x_1)$. So step 2 takes $O(\log n)$ tims.
Similarly, step 3 takes $O(\log n)$ time.

When there are duplicated elements in $A$ and $B$, the idea is similar but somewhat more complicated. A balanced search tree $T$ will store all distinct elements in $A$ and $B$. Each node will store

a distinct element $x\in A\cup B$,
how many time that element appears in $A$,
and how many time that element appears in $B$.

The order of the node is determined by the order of that element. Attached to the whole $T$ are the two pairs $(x_\ell, \delta_\ell)$ and $(x_r, \delta_r)$ defined the same as above.

Exercise 1. Refine the algorithm so that at any point of time, only one of the pairs $(x_\ell, \delta_\ell)$ and $(x_r, \delta_r)$ is maintained.

Exercise 2. Refine the algorithm so that only 1 or 2 cases in step 2.1 are needed by considering $v<x_\ell$ or not, $v=x_{-1}$ or not, $v\in A$ or $v\in B$, etc.

Exercise 3. Consider using one balanced search tree for elements in $A$ and another one for elements in $B$ instead of using one for both of them. Will it work?


Is $E_{LBA}$ turing-recognizable? I have seen a proof that $E_{LBA}$ is not decidable. But is it  at least turing recognizable? How to prove it?

NOTE: $E_{LBA}$ is defined as the emptiness problem for Linear bounded automaton

I just read the definitions, hence I am not an expert on LBAs, but I think that the non-emptiness problem $\overline{E_{LBA}}$ is r.e., so the emptiness problem $E_{LBA}$ can not be r.e., otherwise it would be decidable.

To see why $\overline{E_{LBA}}$ is r.e., notice that to certify that an $LBA$ has nonempty language it suffices to exhibit a word $w$ and a trace $t$ proving that $w$ is accepted by the $LBA$. So, a semidecider only has to enumerate all such pairs $(w,t)$, and (effectively) check for each pair if it proves the $LBA$'s language nonempty.


Describe a TM through denotation of the transition function I'm trying to describe a TM through denotation of the transition function. Given is a TM that recognizes the language

$$
L ={\{w\#w} \mid w \in {\{0,1}\}^*\}
$$
over the input alphabet:
$$
\displaystyle\sum = {\{}0,1,\#\}
$$

My guess is first to place a word
$$
w \in {\sum}^*
$$

on the tape, and in every cell a symbol one after the other:

and the rest would be denoted with squares. Something like this
$$
...w|\#|w|\square...
$$
the head would be on the first Symbol from $w$

So I guess now I know that
$$
\Gamma = \{w,\#,\square\}
$$

I could probably try to make a table using what I have now:

for $w$:

$q_0 = (q_0,w,\#,R)$  R would be the direction the head is going

$q_1 = (q_{yes},w,\#,N)$ N means the head doesn't move and $q_{yes}$ means that the TM accepts w

Im not sure if what I'm doing is correct. I would appreciate if someone could tell me if I'm on the right track.

You are making way too many guesses, and seem to be confused on the difference between words (elements of $\Sigma^*$, or $\Gamma^*$) and letters (elements of $\Sigma$ or $\Gamma$). This is basic stuff and need to be understood before even pretending to think about transition functions.

Indeed, the Turing machine gets a string on its input tape (with letters from $\Sigma$) flanked by $\Box$'s. To be precise $w$ is not an element of the tape alphabet, but a string over the input alphabet $\Sigma$. The tape alphabet equals $\Gamma = \{ 0,1,\#,\Box \}$ plus all the additional symbols that you need for the task you have to perform.

The task is: check whether the input is in fact a string of the form $w\#w$, i.e., two copies of the same string separated with $\#$. The Turing machine may write on the tape and use a little bit of memory, but cannot read stings $w$ in one go (which is what your question suggests). It makes steps on single letters like $(p,0,p_0,\bar 0,R)$: "in state $p$ I read letter $0$, switch to state $p_0$ [to remember $0$] write $\bar 0$ on the tape [replacing $0$ to indicate I have seen it] and move to the position on the right". (Now you have to add $\bar 0$ to $\Gamma$.)

So check your lecture notes on the technical details again, and start thinking how to do the comparison letter-by-letter. It is not that hard: just pretend you are the machine and analyse your steps on a simple example input.


Fastest square root method with exact integer result? I am dealing with the problem of computing $ s = \lfloor sqrt(x)\rfloor$ with $x \in [0,30000^2]$. The common sqrtf(x) on C language is too slow for this case, however it always gives me the correct result. I've tried with the Newton's method but I get very small errors when the square root of a number is exact. This leads to an uncertain pattern of $s-1$ results along the interval. If I increase the number of iterations the method becomes too slow but more exact.

Does anyone know of faster methods or directions on the latest research done in the area?

note to clarify: input is idealy a real number (i.e floating point) but i also accept solutions with integer as input.

You do not need an exact method, anything with error less than 1 is OK. Say you want to compute $\lfloor \sqrt{x} \rfloor$. This is the largest integer $y$ such that $y^2 \leq x$. Say you have an algorithm $\mathcal{A}$ which on input $x$ outputs $z = \mathcal{A}(x)$  such that $|z - \sqrt{x}| < 1$. You can just:

Compute $z = \mathcal{A}(x)$
Let $z_0 = \lfloor z \rfloor$
Let $S = \{z_0 - 1, z_0, z_0 + 1\}$
Output  $y = \max\{y \in S: y^2 \leq x\}$ (in words: output the largest integer among $z_0 - 1$, $z_0$, $z_0 + 1$ whose square is at most $x$).

You can also verify you have the correct number by checking that $(y+1)^2 > x$.

Correctness follows from the fact that if $|z - \sqrt{x}| < 1$, then $|\lfloor z \rfloor - \lfloor \sqrt{x} \rfloor| \leq 1$.

I think Newton's method with a small number of iterations is the best thing you can do. Since you only need error smaller than 1, I believe a few iterations will indeed suffice. Doing extra three integer multiplications and comparisons at the end cannot slow you down so much.


Converting to Chomsky normal form Im having some problems with a qeuestion regarding converting a context free grammar to chomsky normal form.

I have
        S -> abC | babS | de
        C -> aCa |b

I know what to do with the case of aCa and de and b but im not sure how to handle the abC case or the babS case. I believe that chomsky normal form is supposed to have outputs of only 2 characters. so with something like aCa you make and output aa and have A->a and create another nonterminal? X -> SA but I dont know how im supposed to handle the abC case or the babS case.

Let's work it out through the conversion algorithm given in
Wikipedia.

input:
$S \to  abC \mid  babS \mid de$
$C\to aCa \mid b$

Introduce $S_0$:
$S_0 \to S$
$S \to  abC \mid  babS \mid de$
$C\to aCa \mid b$
remove $\epsilon$ rules: there are no $\epsilon$ rules, so nothing changes.
eliminate unit rules: Originally, there are none, but we added one, namely $S_0\to S$. Since it's the only one, we'll deal with it later (after $S$ is already in CNF). This will be done by adding, for any rule $S\to V_iV_j$, the  rule $S_0 \to V_iV_j$. But let's first complete the conversion.
replace all other rules into normal form: we take each transition which is not in the correct form and replace it with $N\to V_iV_j$, introducing new non-terminals $V_1, V_2,...$ as needed:

$S\to ab C$ $\Longrightarrow$ $S\to V_1 C$
setting $V_1 \to ab$. The new $V_1$ is not in CNF, but can easily be converted to CNF by re-defining it as $V_1\to AB$ with $A\to a$, $B\to b$.
$S\to babS$ $\Longrightarrow$ $S\to V_2S$ adding $V_2 \to bab$. Now $V_2$ is not in CNF, so we change it to $V_2 \to V_3B$ adding $V_3\to BA$. (skipping a trivial step here)
$S\to de$ is almost CNF. We change it to $S\to DE$ and add $E\to e$, and $D\to d$.
$C\to aCa$ $\Longrightarrow$ $C\to AV_4$ where $V_4 \to CA$.
$C \to b$ is already in CNF.

so we end up with:
$S_0 \to S$
$S\to V_1 C$
$S\to V_2S$
$S\to DE$
$C\to AV_4$
$C \to b$
$V_1 \to AB$
$V_2 \to V_3B$
$V_3 \to BA$
$V_4 \to CA$
and $A\to a$, $B\to b$, $D\to d$, $E\to e$.

Finally, we need to deal with the unit rule $S_0 \to S$. As said, we will replace the $S$ in the right-hand-side with the "content" of S. That is, we remove that unit rule and add instead:
$S_0 \to V_1C \mid V_2S \mid DE$.


what is a good source for learning how to design a programming language? I am trying to find a good resource for learning on how to design and create a new programming language. It seems like a search for books in amazon raises some difficulties, because the vast majority of results are about programming languages, not on how to design them.

This was a bit too long for a comment. And in a way it is an answer.

I fear that if you have to ask that question, you are not yet mature
enough in the field to actually do the job. Furthermore, the kind of
things you need to learn and do depends very much on what the language
is for. If it is for general programming, you have to understand the
various kinds of structural choices that have to be made. The best
source is a general course on programming, not just programming in
one specific language. To understand what is scope (it varies), what
are variables (they come in different brands), what is environment and
binding, to distinguish between functional, imperative or logical
paradigms, and so on.

Designing a language is highly dependent on what you want to say
(program) and how you want to do it. Look for "programming paradigms."

Learn several advanced programming languages (Haskell, CAML or
others), not just what is commonly used by programmers. When you know
enough languages, you will naturally know how you would want to design
one, if you still do.

And of course, you have to learn all the implementation techniques for
theses structures and features. But that you will largely find in
books on compiler and interpreter writing. Maybe you can start with that.

You do not have to do that. But cemeteries are full of programming
languages that no one ever looked at.

Creating a language is a long, long work, with slim chances of success. Make sure it is worth spending a significant part of your life doing it.


How is the rule 110 Turing complete? I've read the wikipedia page for rule 110 in cellular automata, and I more or less know how they work (a set of rules decides where to draw the next 1 or 0).

I've just read they're Turing complete, but I can't even fathom how would you  'program' in 'rule 110'?

Universality is a somewhat informal notion. What it roughly means is that for each computable function $f$ there is a "program" $P$ in the model so that "running" $P$ on any input $x$ always "halts", and "outputs" the correct answer. (Note that Turing machines don't make an appearance here: they are just one example of a universal computation model.)

The quoted words are those that need to be defined. For Turing machines:

A program is specified as a list of states, a tape alphabet, an initial state, final states, and transitions.
Running a Turing machine $T$ on an input $x$ means that we initialize the tape with an encoding of $x$ and run the machine $T$ on this tape according to the usual rules.
A Turing machine halts if it reaches a final state. (There are some variants here.)
What the Turing machine outputs (if it halts) is the contents of the tape.

Rule 110, as a computation model, needs to be defined formally in the same way. A definition is reasonable if one can computably simulate the computation model, in the following sense: there is a computable function $S$ such that for every program $P$ and input $x$ (both encoded as natural numbers), $S(P,x)$ halts iff $P$ halts on $x$, and if $S(p,x)$ halts then its output is identical to the output of $P$ on $x$.

If you're curious as to the particular setup of Rule 110 as a computing system, I suggest you take a look at Matthew Cook's paper which proves the universality of Rule 110 (or rather, of a computing system built around Rule 110).

As for other rules, such as Rule 30 and Rule 90, we don't know that they are not universal. There might be convincing computing systems built around them which is universal, but we are just not aware of any.


Why Minimum circuit size problem is important? Given a truth table, find the smallest size circuit computing it. Recently it was shown that for multiple output function the problem MSCP (Minimum Size Circuit Problem) is NP-Complete. The article is available online see.

Question: What will be the impact of this problem? or I am not able to follow why this problem MSCP is so important?

I didn't read the article completely, only the introduction part, it seem to me that problem is related to many other problems of interest.

Finding the minimum size circuit is not important in practice for large circuits. Finding small size circuits is of course important because it directly impacts the cost of building a circuit.

Finding minimum size circuits for small circuits that are used as building blocks is quite important. For example, you'd want to know how to build the smallest possible full adder if you end up having a million of them in a processor. And you really want a minimum size circuit for a bit of memory in your L3 cache when your processor has 36MB of L3 cache or 288 million of these cells.

However, minimising the delay of a circuit is also important, and sometimes more important or even far more important than minimum size.


How to extract parent, child and grandchild from a treeview fomatted string? I have a long string that contains data formatted in the following way:

var str = "parent /n /t child /n /t child /n /t /t grandchild /n parent";

If you print this out you get a tree structure like directories. I am trying to figure out a way/algorithm to individually extract every parent and child and children of the aforementioned and store them in an array for each of them so that I can access them later for other useful purposes. I was thinking of using a regular expression to extract the substrings since there is some sort of pattern but I am not an expert in that field and do not know if it is worth the time. Any other ways to approach this problem or is this the best way?

Notes:

A child is always preceded with \n\t

A child's child "" "" "" \n\t\t (possibly spaces between the literals)

If the string is searched the substrings that have been searched should be stored somehow for compiling the node later.

Don't use regexes.  A tree is a recursively defined structure, and regexes don't do recursion (they can't match nested parens for the exact same reason).

You can easily build a tree structure by using a LIFO stack of nodes and maintaining an integer currentDepth, initially 0.  For each line, pop nTabsAtStartOfLine - currentDepth - 1 nodes off the stack, create a new node, make it the child of the current top-of-stack, push it on the stack, and set currentDepth = nTabsAtStartOfLine.


Complexity of Estrin polynomial evaluation The Estrin model for polynomial of degree $n$ is well known. But the reading of the Knuth (vol 2) or the original's paper Estrin do not help (or I miss it). I am not able to determine the complexity of the algorithm for the number of multiplication. The main equation is:

$$
\begin{align}
c_i^{(0)} &= a_i + x_0  a_{i+1}, \\
c_i^{(n)}     &= c_i^{(n-1)} + x_0^{2^n} c_{i+2^n}^{(n-1)}, \\
P(x_0)    &= c_0^{(n)}.
\end{align}
$$

and it leads for a polynomial of degree 10 to

$$
\begin{align}
P(x_0) &=  a_0 + a_1 x_0 \\
               &+  x_0^2(a_2  + a_3 x_0) \\
               &+  x_0^4(a_4  + a_5 x_0 + x_0^2 (a_6 + a_7x_0)) \\
               &+  x_0^8(a_8  + a_9 x_0 + x_0^2 a_{10}) \\
\end{align}
$$

For the additions: $n$

For the multiplication, it could be $n + \lfloor \log_2 n \rfloor$.

Can somebody confirm?

Best,

++t

The question is not particularly clear, but if I'm correct to assume that you're asking about Estrin's scheme for polynomial evaluation then Wikipedia confirms that it uses $n + \lfloor \lg n \rfloor$ multiplications.


Shamos-Hoey Line segment intersection runtime In the Shamos-Hoey algorithm for finding whether or not any two of $n$ line segments intersect, which is available at this site: http://geomalgorithms.com/a09-_intersect-3.html, there is use of "nearest line above" and "nearest line below". The algorithm is supposed to run in time $O(n\log n)$. Here is their pseudocode:

Initialize event queue EQ = all segment endpoints;
Sort EQ by increasing x and y;
Initialize sweep line SL to be empty;

While (EQ is nonempty) {
    Let E = the next event from EQ;
    If (E is a left endpoint) {
        Let segE = E's segment;
        Add segE to SL;
        Let segA = the segment Above segE in SL;
        Let segB = the segment Below segE in SL;
        If (I = Intersect( segE with segA) exists)
            return TRUE;   // an Intersect Exists
        If (I = Intersect( segE with segB) exists)
            return TRUE;   // an Intersect Exists
    }
    Else {  // E is a right endpoint
        Let segE = E's segment;
        Let segA = the segment above segE in SL;
        Let segB = the segment below segE in SL;
        Delete segE from SL;
        If (I = Intersect( segA with segB) exists)
            return TRUE;   // an Intersect Exists
    }
    remove E from EQ;
}
return FALSE;      // No  Intersections

If one studies the C++ code provided at the bottom of the webpage, we see that this is simply a "next" and "previous" in a BST, however, I can't seem to tell which information is being used as the BST key.

My issue is the following: if we are considering all $y$-values at the current $x$-value of the sweep line, this is not merely a check for next or previous endpoint value in a BST, and can not take $O(\log n)$ time. However, if we are checking per endpoint coordinate, this could not possibly be correct, since the following situation would lead to an incorrect execution:

The algorithm should find that $B$ and $C$ intersection on insertion of $B$ into the search tree ("SweepLine" / "SL") while sweeping. However, if we are ordering by endpoint coordinates, $A$ is $B$'s previous, $C$ is not, and this would run into problems.

The BST is ordered with a "above/below" relationship. The idea is that for any "event", the BST is ordered by the y-value where each line segment intersects the x-value of that "event".

When a segment is inserted or deleted, the comparisons in the BST are between the y-value of each line segment at the x-value of the current event. This can be computed with geometry in constant time given the slope of each line. The ordering only requires a single update at each event (a little subtle); the BST requires no other maintenance.

In your example, at the 2nd event when C is added, it is actually inserted above A. Then the B/C intersection would be found correctly.


Concatenation of two regular languages In a question, it is given that L is a finite language over the unary alphabet and L+ is not regular.
We know that L+ = LL*
Since L is finite, it must be regular because all finite languages are regular.
If L is regular L* is also regular.
Then how can be L+ not regular? It is the concatenation of two regular languages. Where am I wrong?

it is given that L is a finite language over the unary alphabet and L+ is not regular.

That's impossible.  Since $L$ is finite, it is regular.  Since $L$ is regular, $L^+ = L L^*$ is regular.  See, e.g., https://en.wikipedia.org/wiki/Regular_language#Closure_properties.

You're not wrong; you are right.


What is the time complexity of generating n-th prime number? Say I want to find the n-th prime. Is there an algorithm to directly calculate it or must I do with sieving? I know always calculate the next prime with a sieve principle, but what if I want the n-th prime?

Duplicate:

https://math.stackexchange.com/questions/1257/is-there-a-known-mathematical-equation-to-find-the-nth-prime

What do you mean by "directly"? This is not well-defined. Arguing that an algorithm doesn't do something during its computation is not a nice well-defined concept (when that something is a semantic condition).

It is probably one of the most common mistakes that people make when thinking about algorithms because they look at obvious cases and think it is simple to formalize the concept that algorithms for a problem does performs some task like computing some other things during its computation but that is not simple at all!

Moreover why would we care? What we care about in practice is not that the algorithm computes all previous primes, but rather time and space efficiency. So I guess a better way of asking your question is asking if there is more efficient way of computing $n$th prime number than sieve-based methods.

If you are asking if there is a provably correct and efficient algorithm to find $n$th prime given $n$ in binary the answer is that is an open question. We don't know if there is any such algorithm, and we don't know if there isn't one. AFAIK, it is consistent with our current state of knowledge that there are algorithms for generating the $n$th prime that run in linear time in $n$. In fact, it can even be the case that we can generate the $n$th prime from bits of $n$ using a polynomial-size constant-depth circuit with threshold gates ($\mathsf{TC^0}$), in simplified non-technical terms: there can be a parallel algorithm with polynomial number of processors that generates the $n$th prime number in constant time and each processor computes very simple functions. So there is big gap between algorithms that we have (upper-bounds) and lower-bounds we can prove for the problem.

However we have algorithms that work efficiently and correctly assuming conjectures like conjectures about how primes are distributed.

See the Wikipedia article on generating prime numbers if you haven't. Also you may want to check this question: Which is the fastest algorithm to find prime numbers?


Optimal strategy for an abstract game I've been given the following problem in an interview (that I've already failed to solve, not trying to cheat my way past): The game starts with a positive integer number $A_0$. (E.g. $A_0 = 1234$.) This number is converted to binary representation, and $N$ is the number of bits set to $1$. (E.g. $A_0 = b100\ 1101\ 0010$, $N = 5.$)

Player 1 chooses a number $B_0$ lesser than $A_0$. $B_0$ must have only one bit set to 1. (E.g. $B_0 = b10\ 0000\ 0000 = 512$.) Let $A_1 = A_0 - B_0$. (E.g. $A_1 = 1234-512 = 722 = b10 1101 0010$.) A move is valid if $B_0$ satisfies the previous constraints, and if the number of bits set in $A_1$ is still equal to N.

Player 2 continues from $A_1$ by choosing a valid $B_1$, then player 1 continues from $A_2$, and so forth. A player loses if they have no valid moves left.

Assuming both players play optimally, determine the winning player using a reasonably efficient method. (In my problem definition, the constraints on this were that the program has to be able to deliver a solution for a few million input numbers that fit into a signed 32-bit integer.) That is, the solution doesn't need to be fully analytical.

My personal interest here is figuring out whether the expectation of me to have found and implemented the correct solution with no way feedback on correctness in the 120 minutes I was given was reasonable; or if this was one of those "let's see if they've seen this puzzle before" questions.

I'd failed because I chose to implement what seemed like a reasonable strategy, that gave me correct results for the few test cases that I've been given up front, wasted too much time making this run fast, and ended up handing in incorrect full output as my time ran out.

In retrospect I should've implemented a brute-force search and memorized partial solutions for small starting numbers, but hindsight is always 20/20. I'm curious however if there's a different common approach that eluded me as a flunkee.

Take a moment for yourself to realize that if we can only substract a power of two, and the popcount can't change we have to subtract $01$ in a position where the other number is $10$. The result of that is always $01$ in that position, and the number doesn't change anywhere else.

In other words, the game is a series of swaps of $10 \rightarrow 01$, and the game ends if all ones are on the right hand side. Note that it's impossible for this game to end early - you can not get stuck. You will always end up at a position where all zeroes are on the left, and all ones are on the right.

So the only determining factor in a game is how many swaps it takes to get to the state where all ones are on the right, and there is no winning or losing strategy. The parity of the number of swaps it takes is the only determining factor.

So how many swaps does it take? Note that $1$s can't cross eachother, so if we numbered them and tracked them through swaps they'd remain in the same order in the final state. Each swap brings them one closer to their final position.

So if the $i$th $1$ (counting from the right, the rightmost $1$ is the $0$th $1$) is in position $k$ from the right, it needs $k - i$ swaps to get to its correct position. This gives us an algorithm to count the amount of swaps required:

i = 0
k = 0
total = 0
while n > 0:
    if n & 1:
       total += k - i
       i += 1
    n >>= 1
    k += 1

We now can just look at the parity of total to see who wins. Time complexity is $O(\log n)$.


Isn't software needed from programs to run? I am a student who has entered a game programming competition called FBLA at school, and I sent them an email because I had a few questions about how the competition is ran.

The main question I had, since I'm a Java programmer was in short:
"Does the program need to be an executable, and if a java update/install is needed to run my program, will they install it?"

Their response was (quote):
"The file does need to be a .exe and the entire program needs to be able to run independently on the judges’ machines. Installing JAVA then running your program is not the intent of this competition. I understand your concern as a JAVA programmer, but this competition is set specifically to this format so that all the programmers know, up front, what is expected."

I can understand the file needing to be an Executable file, but when they said, "Installing JAVA then running your program is not the intent of this competition." really angered me.

If I'm going to make an application in C++, doesn't it require a version of C++ Redistributable? What about DirectX, that's software needed for some C++ programs, isn't it? What about programming in C, and C#?

My argument to them is doesn't all programming languages have a necessity to some form of software in one way or another? Without it, wouldn't applications be very limited, or not run at all?

If someone could please help me settle this issue for installing Java on a machine being no different to making game applications in other languages, I would really appreciate it.

Languages like C and C++ can be compiled to include all libraries they use statically (as part of the executable). This means that the executable will be able to run by itself. Of course, even in this case the executable is supported by the operating system, but this is "for free".

You are right that practical applications normally use dynamically linked libraries and even external data files, but programs arising in programming competitions are usually more low-key and can stand on their own.

The judges have a very practical reason in requiring that the executable be self-sufficient, namely it makes it much easier for them to run it. Java environments are not standard, take up a lot of space, and are time-consuming to install. In principle (and perhaps in practice) you could compile your Java code to Java bytecode and thence to an actual executable, and if you link the appropriate runtime libraries statically, you would get a standalone executable.


Why this greedy algorithm does not return the optimal solution to this NP-hard problem? Problem:
In the generalized assignment problem with unit-value items, there are $m$ bins of capacity $C$ each. There are $n$ items where each item $i$ has weight $w_{ij}$ with bin $j$. The objective is to assign the items to the bins (while respecting the bins capacities) such that the number of assigned items is maximum. I know that this problem is NP-hard.

Question: why the following algorithm is not optimal?

Algorithm:

For each bin $j$, assign the maximum. Here, assign the maximum means to iterate the items such that $w_{1j}\leq w_{2j}\leq\cdots\leq w_{nj}$ and add to bin $j$ the items in that order until the capacity $C$ is filled.
Take the union. This means that, if bin $j$ is assigned a set $S_j$ of items, then the result would be: $\bigcup_j S_j$.

So for example if I have this instance: $C=4$ and $m=3$ and $n=7$. The weights are given by:
$$\begin{pmatrix}
2 & 4 & 4\\
2 & 1 & 4\\
4 & 1 & 2\\
4 & 1 & 4\\
4 & 1 & 4\\
4 & 4 & 4\\
4 & 4 & 2
\end{pmatrix}.$$

So the algorithm gives the following assignment:

bin 1: items 1 & 2,
bin 2: items 2, 3, 4, & 5
bin 3: items 3 & 7

Finally, we choose the following assignment:

bin 1: items 1 & 2,
bin 2: items 3, 4, & 5
bin 3: item 7

Maybe I choose the bad example, can you show me how this algorithm fails?

One thing (which has been pointed out in the comments) is that it is unclear what you mean when you say "union". It appears that what you're doing is simply excluding items assigned to previous bins (but perhaps I do not understand, because "union" is a strange word for this). For example, when you've assigned 1,2 to bin 1 and 2,3,4,5 to bin 2, in the first step, in the final output you only assign object 2 to bin 1, and not bin 2.

Under this assumption, here is a simple example that shows that your greedy algorithm is not optimal. Assume we have two bins, both with capacity 5. Assume we have four items, with weights w_1 = 1, w_2 = 2, w_3 = 3, w_4 = 4 (we'll assume each item has the same weight for both bins). Then if you start assigning from smallest weight upwards until the bins are filled, your assignment is:

bin 1: items 1 and 2
bin 2: items 1 and 2

and after you exclude previously assigned items you end up placing items 1 and 2 in bin 1 and nothing in bin 2 (which is clearly not optimal, since you can place either of the other items in bin 2).

Perhaps you mean a different greedy algorithm, where first you assign 1 and 2 to bin 1, and then (since 1 and 2) are already assigned, you skip those and start again from lightest to heaviest weight, assigning item 3 to bin 2 (upon which there is no space for item 4). This assigns items 1, 2, and 3, and gets a score of 3.

But of course, it is possible to assign all the items, by assigning 1 and 4 to bin 1, and 2 and 3 to bin 2. The greedy algorithms miss this assignment.

As you've mentioned, this problem is NP-hard; in fact, it is hard even for the version where there are only two bins and the item weights are the same for all bins, where it reduces to the Subset Sum problem.


Difference between hypervisor and exokernel An hypervisor (1st type) is a software that creates and run virtual machines, managing guest's operative systems's requests to the hardware.
An exokernel is an operative system kernel, that let's programs access directly to the hardware or, with the support of specific libraries that implements abstactions, run different types of executables for that architecture.

Both the two are an abstraction layer between hardware and application software.
Both the two let you run on the same machine different executables/software/operative systems/whatever

So what's the difference between the two?

The thing that runs on top of a hypervisor is one or more full operating systems.  A hypervisor virtualizes the hardware, so that each operating system is "tricked" into believing that it has an entire machine to itself.  The engineering genius that goes into hypervisors is how to provide this virtualization at little or no cost (compared to running one operating system directly on the physical hardware.)

The thing that runs on top of an exokernel is a bunch of user-level processes.  The processes each attach to a library (maybe the same library maybe different libraries) that provide various services and policies.  The goal of the exokernel is to provide only protection (keeping one process from using the resources devoted to a different process,)  and leave user-level programs to select the policies that were most efficient for them.  Exokernel was really a research project whose main output was a series of studies about different kinds of operating system services and the barriers to implementing those services efficiently.  Another way to view the Exokernel project was that it was a project to investigate how to make a microkernel that isn't dreadfully inefficient and slow.

One of the big problems with microkernels is that they are constantly "crossing process boundaries" and/or switching back and forth between user mode and kernel mode more frequently than would a monolithic kernel (like Linux.)  The cost of switching from user mode to kernel mode or from kernel mode to user mode is surprisingly high (in the 1000s of machine cycles per switch).

It's not clear to me to what degree the Exokernel project succeeded or failed.  There are certainly several cases where they came up with surprising new ways to provide resource protection (like their disk model where the operating system manages permissions for disk blocks and the entire file system is managed at user level).  They also were able to leverage several of the good ideas from around that time, for example, Carl Waldsburger's Lottery Scheduling techniques.  And there were some cases in which capability-based protection turned out to be pretty efficient.

There were other cases where providing policy flexibility dramatically increased the number of kernel boundary crossings and they had to resort to other techniques.  For example, in network packet filtering instead of doing the filtering at user level they did it in the kernel, but gave the user program the ability to submit a little program (in a limited (and therefore safe) programming language) that would run in the kernel.  Similar ideas in this domain were being investigated around the same time by University of Washington's SPIN operating system project.


Can I make last part of counting sort become to be starting from lowest index? Counting sort is originally like below code.

for (int i = 0; i <= 5; i++) c[i] = 0;
for (int i = 1; i <= 8; i++) c[a[i]]++;
for (int i = 1; i <= 5; i++) c[i] = c[i] + c[i - 1];
for (int i = 8; i >= 1; i--) {
    b[c[a[i]]] = a[i];
    c[a[i]]--;
}

In the above, last for loop iterates from last index because of stability of counting sort.

But, I want to iterate from first index 1 as well as maintaining the stability of sorting.

I'm trying and thinking lots of time, I cannot do. How can I do?

Prior to the last loop, c[i] holds the index of last element of bucket i plus 1. It's why when you use c[i] to address items in bucket i you need to go back. But c[i-1] contains index of the first element of bucket i, so you can just use it... except that you need index for bucket 0 too.

So the simplest way is to modify third cycle making it to write initial index of bucket i to c[i]. It may be done f.e. with extra temporary (note that i in revised loop starts from 0):

sum = 0;
for (int i = 0; i <= 5; i++)
{
    sum += c[i];
    c[i] = sum - c[i];
}

Note that since indexes in b starts from 1, you need to pre-increment c[a[i]] in new version of last loop (if indexes in b should go from 0, do post-increment instead):

for (int i = 1; i <= 8; i++)
{
    c[a[i]]++;
    b[c[a[i]]] = a[i];
}


What is an intuitive way to explain and understand De Morgan's Law? De Morgan's Law is often introduced in an introductory mathematics for computer science course, and I often see it as a way to turn statements from AND to OR by negating terms.

Is there a more intuitive explanation for why this works rather than just remembering truth tables? To me this is like using black magic, what's a better way to explain this so that it makes sense to a less mathematically inclined individual?

Insert real-world predicates and read aloud, for instance:

  It can not be both winter and summer (at any point in time).

and

  (At any point in time) It is not winter or it is not summer.

Clearly, the two statements are equivalent.


Issue triangulating a font glyph for a specific scenario I am trying to triangulate TTF glyphs for drawing in opengl. The below image shows an example glyph (Taken fron FontForge application). The X represent control points of a bezier spline, circular and square points represent points on the glyph but they can also be the start / end points of the bezier splines.
I have a triangulation process that can take all these points and render them in opengl, I'd like to render the bezier curves in a shader, I have something that does this and it works. They way I split things up is to take the control points, the start points and end points of the bezier spline and pass those to the bezier shader. For the curves that curve out side the shape I need to remove the control points from the triangulation routine (because I don't want to fill in these triangles completely, I leave that to the bezier shader). For the control points that curve in to the shape I keep them for the opposite reason to above.

For the example above I have shown some additional red lines showing what the new outline would look like with the outer control points removed. That can be seen below.
This shows an example of the issue I am having, I can no longer triangulate this because the red lines at the bottom cross outside the shape and then back in again.
Is there a better algorithm I can use to do this to avoid situations like this?

The points and control points define a spline curve. Your graphics hardware is usually not capable of handling splines directly, so you convert the spline into a polygon. You'll add enough points to the polygon so that the difference between spline and polygon is negligible. Control points are NOT part of the spline! So adding them to your straight line segments is a massive mistake. Don't do that, and your problem goes away.
I'd start with the points that are given to be on the curve, then figure out how many points you need to add between these points to keep the error low enough. You might want to add points just in the middle, so the same letter at a bigger size will contain all the points of a smaller size letter plus additional ones, and the curves will look the same.
For best quality, make sure that the area where the polygon is to the left of the spline and the area where it is to the right is about the same. That's because this could affect line thickness, and that is something very, very easy to spot by the naked eye.