The Gas Station Problem - fast implementation Recently I was asking about the algorithm to solve The Gas Station Problem and I got useful answer. Unfortunately solution with transforming a graph to complete graph and then preparing another one to find the shortest path (as described in paragraph 4) is really slow in case of my constraints.

I figured out how to implement much faster version. It's way better, but has a bottleneck :-(. Let me first describe my implementation. It's really simple:

I use BFS and relaxation method to calculate D[destination][0]:

D[v][f] - minimum cost to get from u to v with remaining f units of fuel at this city.

minFuel - minimum remaining fuel at v = max(0, f1 - distance(u,v))
maxFuel - maximum remaining fuel at v = tankCapacity - distance(u,v)

D[source][0] = 0
D[v][f] = min((u,v), f1, f2 | u->v in Edges and f1 in 0..tankCapacity and f2 in minFuel..maxFuel)
             { D[u][f1] + (f2 - f1 + distance(u,v)) * fuelRate[u] }

The bottleneck is because of going through all possible values (f1, f2).

Pseudocode:

queue.push(source);
D[source][0] = 0
visited[source] = true

while(!queue.empty)
    current = queue.pop

    foreach (current,v) in Edges
       if !visited[v]
           queue.push(v)
           visited[v] = true

        for f1 in 0..tankCapacity
           if D[current][f1] == infinity
              continue

            minFuel = max(0, f1 - distance[current,v])
            maxFuel = tankCapacity - distance[current,v]

            for f2 in minFuel..maxFuel
                toRefill = f2 - f1 + distance[current,v]
                newCost =  D[current][f1] + toRefill * fuelRate[current]
                if (newCost < D[v][f2])
                   D[v][f2] = newCost

return D[destination][0]

Constraints (only integers):

maximum vertices:      1000
maximum edges:         10000
maximum distance:      100
maximum fuel rate:     100
maximum tank capacity: 100

Does anybody have an idea how to improve this algorithm to make it faster?

Your recurrence relationship isn't quite right -- you need to relate the input parameter f to f1 and f2 somehow.  I think you can get rid of f2 completely:

checkTank(f) = if f <= U then f else INF
D[v][f] = min(u, f1 | u->v in Edges and f1 in 0..tankCapacity)
             { D[u][f1] + checkTank(f - f1 + distance(u, v)) * fuelRate[u] }

Entries D[v][f] for values of f which would imply putting more gas in the tank than it can hold will correctly get assigned INF by the above.  (Here I assume that adding any nonnegative value to or multiplying any positive value with INF yields INF again; in an actual implementation you might want to specially check and avoid further processing of such values.)

But in any case, the algorithm in the paper is fast because they exploit a dominance rule (Lemma 2.1) that implies that an optimal solution can always be found even if you only look at O(n) particular different gas tank levels at each node, and you aren't making use of that here.  If you don't make use of that same property, I think your algorithm will be at best pseudopolynomial (they say this in the paper; BTW that doesn't necessarily make it a terrible algorithm in practice) and in effect usable only with integer-weight fuel amounts.

Regarding adding the missing edges: For the case where you don't limit the number of stops, the running time is O(n^3), so it's safe to run Floyd-Warshall at the beginning to calculate the minimum path distance between all pairs of vertices that lack an edge, as it's also only O(n^3) and therefore doesn't increase the running time asymptotically.

At first glance it seems possible to accept an incomplete graph, and allow "fill stops" at which 0 fuel is filled.  But this invalidates Lemma 2.1, since now there can be graphs in which an optimal path involves filling up less than the full amount at some node w, before travelling to some node u with higher cost, "filling up" with 0 fuel there, and then travelling on to reach (on an empty tank) some other node v with cheaper fuel than w.  You can play around with Lemma 2.1 to allow arbitrarily long strings of special "0-fill" stops between "real" stops, and this works, but it doesn't buy you anything: for each vertex u, instead of having to consider all possible neighbours w of u and their distances d(w, u) to u, you'll have to consider all possible vertices w and the lengths of their shortest paths to u, which means that you might as well calculate them all at the start and make edges with their weights.

Finally you can discard/ignore/avoid calculating any edges longer than U or which violate the Triangle Inequality (in fact these constraints also apply to any edges already in the original graph).


How would Computer Science help the world in the novel coronavirus outbreak This may seem off-topic question but I am really wondering how CS folks could help in situations like coronavirus. What novel problems arise from such disease? From CS and ML/AI perspectives, is there anything that Computer Scientists could do to better combat the coronavirus?

During a recent Hackathon I witnessed, a team prepared a gadget like a smart watch. The goal is to check how many times does a person cough, to track fever and such. A really cheap piece which can be worn by everyone. The data that can be attained would yield geo-coordinates of the societies and getting affected and need attention. It can help prioritize areas of immediate concern.


Big O relation between $2^n$ and $2^{2n}$ I know that:

If $f(n) = O(g(n))$ , then there are constants $M$ and $x_0$ , such that

$f(n) <= M*g(n), \forall n > n_0$

The other, plain English way of defining it is,

If $f(n)=O(g(n))$ then for large $n$ , $f(n)$ would grow as fast as $g(n)$.

I got confused when comparing $2^n$ with $2^{2n}$. Here , $f(n) = 2^n$ and $g(n) = 2^{2n}$. Clearly , $f(n)$ is smaller than $g(n)$ by a factor of $2^n$. So there will be constants $A$ and $x_0$ such that the first definition above is met.

However, for large $n$ , $2^{2n}$ would grow much faster than $2^n$, leaving $2^n$ far behind. That is $2^{2n}$  won't be an asymptotic/tight bound for $2^n$ .

So, is $2^n = O(2^{2n})$ or not? (or did I just create a confusing situation out of nothing)

The more strong estimate is correct:

$2^n = o(2^{2n})$

Just look at definition of the little-o. For any constant $c \gt 0$ you need to find a constant $n_0$, such that for all $n \ge n_0$ you get $2^n \le c \cdot 2^{2n}$. Apparently, the following inequality will give you this $n_0$:

$n_0 \ge ln(1 / c)$


Restricted Integer Programming The integer feasibility problem is NP-complete:

$Ax=b, x \geq 0, x \mbox{ integer}$

$A$ contains elements in $\mathbb{R}$

If we restrict this:

$A$ contains only elements in:

$\{1,0\}$
$\{1,0,-1\}$
$\mathbb{N}$
$\mathbb{Z}$

Does this change anything in term of hardness?

Can all these problems be reduced to each other?

(Can it be for example that there is polynominaltime-algorithm for 1. but not for 4.?)

All four problems are NP-complete.

Let me start by proving two easy results:

Your problem #3 is NP-complete, even when the matrix has only a single row, as explained here: Complexity of a subset sum variant.
This implies that #4 is NP-complete as well, as #3 is a special case of #4.

Now for the strong result: Your problem #1 is NP-complete.  The proof of this is a bit more involved, but I'll show a reduction from ZOE to your #1, where ZOE is a problem that is known to be NP-complete.

In particular, here is the definition of ZOE:

ZERO-ONE EQUATIONS (ZOE)
Input: a $m\times n$ matrix $A$, all of whose entries are 0 or 1
Goal: Find a $n$-vector $x$, all of whose entries are 0 or 1, such that $Ax=1$, where $1$ denotes the all-ones vector

The ZOE problem is NP-complete.  This is proven in Chapter 8.3 of Algorithms (Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani).  The proof proceeds by reducing 3SAT to 3D Matching, and then reducing 3D Matching to ZOE.

Now we can reduce ZOE to #1, as follows.  If we have an instance of ZOE $A$, we transform it as follows.  For each variable $x_i$ of the ZOE instance, we add another variable $x^*_i$ and an equation $x_i + x^*_i = 1$.  (This has the effect of forcing $x_i$ to be either 0 or 1, since we'll require $x_i \ge 0$ and $x^*_i \ge 0$ and $x_i,x^*_i$ are integers.)  Thus, if the ZOE instance had a $m\times n$ matrix $A$, we now obtain $m+n$ equations in $2n$ unknowns, corresponding to some matrix $A'$.  In other words, we obtain a problem instance $A'x' = b$ where $b=1$ is the all-ones vector, and where every entry of $A'$ is 0 or 1.  This is now an instance of your problem #1.  This instance of your problem #1 has a feasible solution if and only if the original ZOE instance has a feasible solution.  This proves that any efficient algorithm to your #1 in turn yields an efficient algorithm for ZOE -- but since ZOE is NP-complete, it follows that #1 is NP-complete as well.

It follows from this result that #2, #3, and #4 are NP-complete as well, as #1 is a special case of them.


Why is deciding regularity of a context-free language undecidable? As I have studied, deciding regularity of context-free languages is undecidable.

However, we can test for regularity using the Myhill–Nerode theorem which provides a necessary and sufficient condition. So the problem should be decidable.

Where is my mistake?

Myhill–Nerode does indeed provide a characterization of the regular languages but that isn't enough to show that the problem is decidable.  "Decidable" means that there is an algorithm (more formally, a Turing machine) that terminates for every input and, of course, always gives the correct answer.  So, in this case, you would need to give an algorithm that, given a language as input, determines whether the Myhill–Nerode relation has a finite number of equivalence classes.  It turns out that this cannot be done for context-free languages; details in your favourite formal languages textbook.

If you want to decide whether a general language is regular, a further subtlety is that you have to be careful about what is the input to your algorithm. The input must be a finite string – otherwise, even just reading the input would be a non-terminating algorithm.  In the case of context-free languages, you could use a grammar as a finite representation of an infinite language.  For more general languages, you would need... well, something more general.  Ultimately, though, if you want to deal with all languages, you're doomed.  Over any finite alphabet, there are uncountably many languages but only countably many finite strings. That means you can't possibly describe all languages using finite strings.1 Therfore, trying to write an algorithm to determine whether arbitrary languages given as input are regular actually fails before it begins. It's not just that you can't write the algorithm: you can't even write the input!

Note that this doesn't mean that you, a human being, can't use Myhill–Nerode to determine whether languages are regular. It just means that you can't write down a set of precise instructions to tell me how to do that.  At some point, any such set of instructions would have to say something like, "And then play about with it to see what works," or "From there, you have to figure it out on your own."

In particular, this means that some languages must be undecidable, since there are more languages than there are algorithms.


Reducing Clique to Independent Set The Clique problem takes a graph $G = (V,E)$ and an integer $k$ and asks if $G$ contains a clique of size $k$. (A clique is a set of vertices such that every pair of vertices in the set is adjacent.) The Independent-Set problem takes a graph $G’ = (V’,E’)$ and an integer $k’$ and asks if $G’$ contains an independent set of size $k’$. (An independent set is a set of vertices such that no pair of vertices in the set is adjacent.)

Give a polynomial time algorithm that, given a graph $G$ and an integer $k$ produces a graph $G’$ and an integer $k’$ such that $G$ has a clique of size $k$ if and only if $G’$ has an independent set of size $k’$. Justify your answer.
Use 1. to prove that the Independent-Set problem is NP-Complete given that the Clique problem is NP-Complete.

The trick is to realize that if a graph has a clique of size $k$, the inverse graph has an independent set of size $k$. A clique of size $k$ means that $k$ nodes all have edges in between them. In the inverse graph these $k$ nodes are not (directly) connected and can be used to create an independent set of size $k$

Hence, the polynomial time algorithm you are looking for is merely the one that inverts the graph.

You will find a youtube explanation here.

I suspect that if you try to draw some very simple graphs with cliques and the inverses of said graphs you will realize why this is true.

As for (2), you need to show that an algorithm to the independent set problem can be used to solve the clique problem. Furthermore you need to show that using the solution to the independent set problem can be used to find the solution to the clique problem in polynomial time. This proves the following:

You can now reduce the clique problem to independent set. As all problems in NP can be reduced to the clique problem (the definition of clique being in NPC) all problems in NP can be reduced to independent set too and so it is in NPC. And since you reduced clique to independent set in polynomial time it cannot be harder than the clique problem either.

So (2) is equivalent to the following: If you were given a polynomial time algorithm for the independent set problem, how would you use it to find out whether a graph had a clique of size $k$?


How to judge the searching precision of Particle Swarm Optimization? As the title mentioned, how can I judge the searching precision of PSO? Is this depending on the velocity of the particles? I would like to give an example to clarify my question: For a 2-D searching, the precision of grid ergodic searching is the searching step. But what the precision should be using PSO searching. From the position update formula of PSO:

$x_i \leftarrow x_i+v_i$

So, we can assume the precision of PSO searching is the maximum of velocity of particles? Is this right?
Generally, we set the maximum of particle velocity is about 10% to 20% of the position scale. But with this setting, we can still obtain a good precision with PSO, which contradicts previous assumption. So the searching precision of PSO is? Or it can be expressed as a function of maximum velocity and other parameters?

It seems that PSO can realize arbitrary precision... Because if there are sufficient particle numbers and iteration times, the PSO can approach to the actual solution.

If by "precision" you mean the error in the result of PSO (i.e., the difference between the value that PSO outputs and the true global optimum), the error can be arbitrarily large.  PSO is a heuristic.  There are no guarantees that it finds the global optimum, or even that it gets close -- and there is no formula in terms of parameters (like velocity) for how large the error will be.  The error depends on the optimization problem you're solving and on the shape of the loss surface.


What is the practical purpose of an epsilon NFA? If for every $\epsilon$-NFA their exists an equivalent NFA what is the purpose of ever using an $\epsilon$-NFA? I am having trouble understanding what the practical purpose of using one would be.

Purely convenience.  It's like, in a programming language, why have for loops, if every for loop could alternatively be written as a while loop?  Convenience.  It's sometimes convenient to be able to use epsilon-transitions, when defining NFAs.  For instance, when converting a regexp to a NFA, the construction is arguably a bit simpler (easier to understand) if you allow yourself to use epsilon-transitions.


Reduction examples from the strongly NPC problem 3-PARTITION 3-PARTITION is strongly NP-complete, i.e. it remains NP-complete even if the input is given in unary.

I'm searching two or three examples of (possibly well-known) non-numeric problems that have been proved to be NP-complete using a reduction from 3-PARTITION (and the reduction obviously relies on the strongly np-completeness). I would like the references to the original papers.

Prof. Erik Demaine has contributed the wonderful (video) lecture of "Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall'14)". In particular, lectures 2 and 3 are devoted to the reductions (directly or indirectly) from $\textsf{3-Partition}$.

For example, Lecture 2 is concerned with several variants of Jigsaw puzzles. The results are collected in the paper "Jigsaw Puzzles, Edge Matching, and Polyomino
Packing: Connections and Complexity". Its abstract says

  We show that jigsaw puzzles, edge-matching puzzles, and polyomino packing puzzles
  are all NP-complete. Furthermore, we show direct equivalences between these three types of
  puzzles: any puzzle of one type can be converted into an equivalent puzzle of any other type.

Most probably you have known these results and this video lecture. However the wonderful lecture may be also useful for other people.


One way recurrence O(N)->O(1) Imagine we have a random number generator where g(n+1) = f(g(n)), where f is some function (e.g linear recurrence).
I'm trying to find a system where it's fast to find many steps in the future immediately, whereas it's hard or impossible to work out a previous state.
for example, if I know state = X at time t,  I would like to calculate state at t+n steps in the future, done in order O(1) rather than having to iterate n times.

I'm assuming state has an implicit modulo of around some power of 2 so it must be restrainted to a given number of bits at each time.

Does anyone know of a system that could provide this?
Many thanks.

There are two answers: one that solves your problem, and one that answers your question. I'll start with the first. One way to make sure that previous states cannot be backtracked from generated numbers is to mask the true state. Here's how it works. You take your $b$-bit number $x_t$ to be the true state at time $t$, but the number your RNG generates is $x_t \text{ mod } m$, where $m$ is much less than $2^b$. Then you can specify $g$ to be $x_{t+1} = a \cdot x_t \text{ mod } n$, with $a$ and $n$ large numbers that are relatively coprime.

This way, if you collect the numbers generated by this RNG, you need at least a couple of data points before you can make educated guesses about $x_t$, and even then it's not easy. The period of the RNG is $n$.

The answer to your question about whether there exist easy-to-compute functions that are hard to invert is an open question, known as the existence of one-way-functions. Existence is known to imply P $\not=$ NP, so it probably won't be resolved for some time. That's for functions that are easy to compute in one iteration; functions that allow an arbitrary amount of time steps to be computed is a question on a whole other level.

Of course, if you relax the question to mean a function whose inverse requires, say, $\Omega(b^2)$ time to invert, rather than superpolynomial time, there are options. For example, you could keep the function $x_{t+1}=a\cdot x_t \text{ mod }n$. To invert that function, you need to find the the multiplicative inverse of $a \text{ mod } n$. This takes $O(b^2)$ time. Then you will be able to compute $x_{t}$ given any $x_{t+1}$ in, again $O(b^2)$ time, as $x_t = x_{t+1} \cdot a^{-1} \text{ mod }n$.

This function is easy to compute for several steps, if you are willing to do some precomputation. Note that $x_{t+1} = a \cdot x_t$ and $x_{t+2} = a\cdot x_{t+1} = a^2 x_{t}$, so $x_{t+k} = a^{k} \cdot x_t$. Now you can precompute $a, a^2, \ldots, a^k$ up to some $k$, and from then on you will be able to compute $a_{t+j}, 1 \leq j \leq k$ efficiently.


How to do product construction with 2 DFA which has dead state I have been trying to do a product construction(intersection) with 2 DFA which has dead states, but I'm stuck at the transition table with a confusion that,what should I do with dead state. Should I also combine the dead state with other states?

The product construction works for any two DFAs. There is nothing special you need to do. The resulting automaton would have many dead states and so won't be minimal, but that doesn't affect its correctness.


What are some possible "functional" memory structures? With my thin knowledge on embedded systems, compilers, and computer architectures, I know that the basics of computer memory(physical) are sort of like an array, with addressing which work like pointers. I see that imperative programming(which eventually unwraps to assembly, or the Turing Machine) fits this architecture very well.

I am a bit interested to see if there is a counterpart of physical memory that might fit the functional programming style. By "fitting", I am making the assumption that all pure functional languages can unwrap to be immutable lambda expressions(via Lambda Calculus). Now, with the array-like memory structure, we have to allocate and gc objects under the scene in order to get lambdas to work(because lambda expressions do not address operations on memory directly). Just as a thought experiment, is it possible to have a device that fits the need of memory in lambda expressions, while not containing a garbage collector?

Yes, I know that some imperative programming languages do use garbage collectors. However, when boiled down to assembly, it doesn't. So I am more curious about the evaluation of "pure" lambda expressions.

Just as a note, the lambda expressions I talk about include the fixed point operator(i.e. recursion).

The topic is fairly broad.

Functional hardware has been explored in e.g. Lisp machines.

More on the theoretical side, you may want to read about the various abstract machines which have been proposed for running functional languages.
Some of them are the SECD machine, the CAM (categorical), the Krivine machine, the STG machine.

Perhaps a more radical approach can be learnt by looking at the various graph-reduction machines. A pioneering work by Lamping describes how lambda can be run faster by rewriting graphs (!), instead of expressions.
More recently, linear logic simplified the several rewriting rules.

Some of these approaches can give you some hint at how a custom functional hardware should be made to speed up execution.

For conventional hardware, the STG machine seems one of the most promising approaches.


Definition of a grammar I am learning about context free grammars and have been through few texts in a undetailed  manner  on these topic . I think I should know the exact , rigorous ,technical definition of what exactly a "grammar" means .

I could see that  ,in all of these lessons, a sequence of equations as follow :

 a = bc
 b = ed
 c = gh

I was tempted to conclude that "a grammar is a collection of symbols which are related by a set of equations which dictate rules for substitution of a symbol by a series of symbols "

Then I got to know that , not in all series of equations can we substitute one symbol by a series of another symbol .We can do it only in case of "context-free grammars " .
Then I went through one of the stackexchange post and through a brilliant answer got to know what context free exactly means .

So , I thought before I proceed ahead I better seek for the exact rigorous definition of a grammar .
What exactly is the mathematical/technical definition of a grammar ?

A grammar is a set of production rules for symbol sequences.

But you knew that already. If you edit the question to make it more specific, we can offer more specific answers.


Why did Apple include dedicated a neural network "processor" in standard consumer products? Not sure if this is the right place, but I guess it is better than Reddit and I couldn't find any discussion.
I was wondering why Apple include a neural network "processor" and can't help but feel that is a waste as a prospective ML Engineer, so it is very likely that I am missing / in ignorance of something so wanted to ask what it is.
Two reasons come to my mind:

Apple will allow a distributed cloud computing on its products (Feels expensive if that is the only reason.).

Improved security. All personal bio-data (fingertip, face, speech) will be stored locally, while processing will be done on wholly local or quasi-local with some calculation going to servers safely.

Does anyone have any idea?

Having a powerful machine learning chip in your device allows you to do things that you probably have not thought of. Things like improving the images that your camera is taking. Cutting out the background and replacing it with a boring beige background, very valuable if you are in a video conference and want to show your face to people but not your home.
Or a nice one: Most people in a video conference look at the screen, not at the camera, so when their image is transmitted, it seems that you can't look in the other persons eyes. Very nice if you have an ML chip how can change the image as if you were looking straight into the camera, without taxing your battery.
Something not done (yet) would be improving sound quality, for example removing background noise and filling in gaps when sound transmission fails, and totally cool would be removing people's accents, so that I can understand someone with a strong Scottish or Indian accent without problems.
You are about in the same situation as someone in the early 1980's asking what the advantages of a graphical user interface would be.


Regular Expression for {W | W contains an even number of As and an odd number of Bs, but doesn't contains AB} While studying Automata at my University, I faced the following problem from SIPSER, M textbook:

  Consider D = { w | w contains an even number of as and an odd number of bs and doesn't contains the chain ab}. Draw an DFA with 5 states that recognizes D and a Regular Expression that generated D.

I tried doing the following DFA:

With the Regular Expression b(bb)*(aa)*

And that seemed quite right for me, but for chains that goes like baab it should be refused, but it isn't.

I couldn't find a way to fix it without adding another state to the DFA.

How can it be done?

Here's one possible solution:

(In fact, the words $b,bb,ba,baa,bab$ show that at least five states are needed, so this is the unique minimal DFA.)


A doubt on best media for a time capsule So, I have some data to a time capsule project of mine. But the thing is, I need to know the best media on long-time scale to use as storage unity. The time range is 120 years. Now, I've been thinking about two medias: the average CD-ROM/DVD-ROM and a outdated Vinyl/LP. On the one hand the CD/DVD is a good one, due to its dimensions and information space, but the question remains about the difficulties to read a CD/DVD in 2141. A vinyl LP could be more simple.
So my question is: what is the best media for a time capsule?

This is an interesting question that has a multidisciplinary application. Not only does this apply to computer science, but given the nature of preservation of that data over time also applies to archival science!
While DVDs and CD-ROMs generally have a high information density, they were never designed with longevity in mind. The average life-expectancy for either of the two is about 100-200 years, according to Council on Library and Information Resources. [1]
This may sound like a long time, but your question regarding the ability to retrieve the information 120 years from now comes into play. A major factor in deciding if a media is archival or not is the ability for that information to be interpreted years later. Assuming there is still a method for retrieving data from CDs and DVDs 120 year from now depends on several factors:

How much information are you looking to store?
What are the storage conditions?
--You said "time capsule," but does this mean the capsule will be hermetically sealed? Will it be purged of all moisture, oxygen, and other environmental contaminants that are known to degrade material integrity over time? Will the environment be replaced with an inert gas like nitrogen to provide a stable environment?
What is the tolerance for data loss/corruption? Is this going to be something that needs to have archival quality, e.g. zero-tolerance for loss? CDs and DVDs can experience some loss given their storage and handling over time. [1]
You have already asked one of the most important questions regarding the ability to retrieve the information 120 years from now.

The last question is something that archivists have been asking for some time. In today's world where we are generating more data on a daily basis than we have since the beginning of time, we need to develop a solution that addresses the questions of how much information needs to be stored and for how long does it need to last?
A question still remains unanswered: does your time capsule have to have media that already exists, or is it a quandary into the realm of storage technologies that could be developed to store information for a long period of time?
If it has to be of media that already exists, there are a few options out there:

Microfilm: industry standard for data preservation. Film of particular types is guaranteed to last for ~500 years. [2] In the application of computer science, you could quite feasibly encode some arbitrary data in binary dots/dashes onto a piece of microfilm and interpret the data via computer. The advantage here is twofold: binary is a numbering system that isn't going anywhere and all you just need something to view the microfilm. Any intermediate technology can change between now and the next 120 years (think scanners, other ways of reading data into a computer), but all you need is a way to read visual data into a computer. This is unlike CDs or DVDs that can only be read by a very specific device.
You already mentioned one of them: an LP. Specifically an LP made from copper, aluminum and gold like the ones on Voyager I and II.
Least romantic? Straight up paper. As long as it is well-kept and information density is not a concern, acid-free paper will stick around for 120+ years (think The Declaration of Independence).

Things to stay away from:

SSDs or anything based on flash memory. These all need a minimum trickle charge of voltage to hold onto all of their data. Over time, the electrons leak from the storage cells and the data becomes corrupted. [3]

Some things have already been proposed for future storage:

Recording the information on a CD or DVD-like surface, or a small square, either of which would be made from glass. This would not involve the metallic substrate employed by laser-read media that is known to degrade over time. The method for recording the information would be etched in the media by laser in a similar bit pattern, while using etchings of varying depths could be used to increase the information density.
Using DNA to encode data. DNA is known to last for millennia as long as it is kept from UV light. It would also provide a method of storing information in base-4 -- given the fact that DNA uses the four base pairs G, C, T and A to store information -- versus base-2, which uses 0 and 1. This would effectively increase the information density in two domains: the space in which the data could be stored given the relatively small size of DNA and the numbering system used to store that data.


Proving NP-completeness of a graph coloring problem Given a graph $G=(V,E)$ and a set of colors $k<V$. Find a assignment of colors to vertices that minimizes the number of adjacent vertices in conflict. (Two adjacent vertices are in conflict if they have the same color.)

I want to prove the above problem is NP-complete. Call the above problem P1.

Answer: I am trying to reduce the k-coloring problem.

P2: Given a graph $G=(V,E)$ and set of colors $k<V$ is the graph k-colorable (zero conflicts)?

P2 is feasible iff P1 has optimal value is exactly $0$. Therefore if P1 is solved we know solution to P2.

Is this solution correct? Is it what is suggested by the first comment of user G.Bach in A variation of the graph coloring problem ?

First of all, you haven't formulated your problem as a decision problem (a problem that has a YES/NO answer). The decision problem corresponding to your optimization problem is: Given a graph $G$, an integer $k$ and another integer $\ell$, is there a $k$-coloring of $G$ with at most $\ell$ monochromatic edges?

In order to show NP-completeness of a problem $P$, you need to do two things:

Show that $P$ is in NP. This is usually easy. It just means that a putative solution can be verified.
Show that $P$ is NP-hard. In practice, this is (almost) always done by showing that some other NP-hard problem $Q$ is many-one reducible to $P$. This implies that $P$ itself is NP-hard.

A many-one reduction from $Q$ to $P$ is a function $f$, computable in polynomial time, which maps an instance $x$ of $Q$ to an instance $f(x)$ of $P$ such that $x \in Q$ iff $f(x) \in P$.

In your case, it is easy to see that your problem (let's call it MIN-MONOCHROMATIC) is in NP: the NP machine guesses a $k$-coloring of $G$, and verifies (in polynomial time) that there are at most $\ell$ monochromatic edges. In order to show that it is NP-hard, we come up with a many-one reduction $f$ from the NP-hard problem K-COLORING to MIN-MONOCHROMATIC. The reduction $f$ takes a graph $G$ and an integer $k$, forming an instance of K-COLORING, to the instance $(G,k,0)$ of MIN-MONOCHROMATIC (i.e., with $\ell=0$). The definition of coloring implies that $(G,K)$ is in K-COLORING iff $(G,k,0)$ is in MIN-MONOCHROMATIC. Also, clearly $f$ can be computed in polynomial time. So $f$ is a polytime many-one reduction from an NP-hard problem K-COLORING to MIN-MONOCHROMATIC, so we conclude that the latter is NP-hard. Since it is also in NP, it is NP-complete.

As you see, this is the same proof as yours, only with a lot of fluff. At this stage of your education, this fluff is important, since you need to makes sure that you understand the definitions not only intuitively but also formally (both are important). Once you're past this stage, all the details you really need are the ones explained in your current proof.


Deustch algorithm using one qubit Deutsch algorithm uses two qubits to determine the type of function. But what if we have only one qubit? How the algorithm would be implemented? And especially, how $U_f = |x\rangle |y \oplus f(x)\rangle$ would look like?

Unfortunately, as D.W. says, it's not possible to do Deutsch's Algorithm with only a single qubit.

The key is the line you quoted in your question: the quantum oracle for the function $f$ returns $\mid x\rangle \mid y \oplus f(x)\rangle$. This only works with two qubits.

Why can't we just make the oracle return $\mid f(x) \rangle$? Well, in quantum computing, all functions must be reversible (you can reconstruct the input from the output), and we have no guarantee that $f(x)$ is reversible. And if we force $f(x)$ to be reversible, then we know it's balanced, and the problem becomes trivial (return "balanced" every time).

The only way to make a reversible function out of a function that may not be reversible is to add "ancillary" or "garbage" qubits; this is how the Toffoli gate implements the non-reversible AND function. That's basically what the second qubit is doing here: without it, we can't even necessarily call the function.


Relation with the perfect partition problem and the single machine task schedule problem Perfect partition problem (PPP): given $x_1,...,x_n\in \mathbb{N}$ we want to know if there's a set $S\subset \{1,2,...,n\}$ such that $$\sum_{i\in S}x_i=\sum_{j\notin S}x_j.$$

Single machine task schedule problem (SMP): a machine can perform only one task $T_i$ with duration $d_i$ at a time and we want to know if all tasks can be done, given that $T_i$ can't start before the time $a_i$ or be finished after the time $b_i$ with $i\in \{1,2,3,...,n\}$.

I want to know how to reduce PPP to SMP.

EDIT: I tried modelling SMP using the constraints and the existence of a bijection $f:\{1,2,3,...,n\} \rightarrow \{1,2,3,...,n\}$ such that $$a_{f(i)}\leq \sum_{j=1}^i d_{f(j)}\leq b_{f(i)}$$ for all $i\in \{1,2,3,...,n\}$. And I tried to make $x_i=d_i$ and get the conditions of the SMP to make the sum be equal to que complementary $\left (\frac{\sum_{i=1}^{n} x_i}{2}\right)$ at some point, but I got stuck as I can't find how to relate $f$ to $S$ from the PPP, that's not really working.

Just let $d_i=x_i$, $a_1=\frac{\sum_{i=1}^n x_i}{2}-d_1$ and $b_1=\frac{\sum_{i=1}^n x_i}{2}$, and $a_i=0$ and $b_i=\sum_{i=1}x_i$ for other $i$'s. Then easy to see there is a solution for the original PPP instance iff there is a solution for this SMP instance.


What would be a natural generalization of a byte parity check? Suppose that we have a group of N bytes. One can add a very basic (and not particularly reliable) check of the consistency of this data by storing an additional (N+1)th byte containing exclusive XOR of all N original bytes. It will be enough to detect a single byte error during the transmission.

In the practical problem that I am trying to solve, if an error occurs during transmission, I actually will know when error occurred and which byte contains the error. Then knowledge of the (N+1)th byte is sufficient to recover the incorrect byte by simply XORing all correct bytes with the (N+1)th byte.

The errors that can occur in my application actually occur in bursts of 1 or several bytes, I will denote this number as M. There can be no more than a single burst per group of N bytes. In fact, when error occurs my transmission channel returns N-M bytes, along with the marker of the position where bytes were lost.

My question is: what would be (is there?) a natural way to generalize the simple (M=1) error correction scheme using a single XOR byte to the case where the error burst can contain up to M skipped bytes? Is it possible to do this specific kind of error correction using only M bytes?

For $i \in \{0,\ldots,M-1\}$, add a new byte which is the sum (or XOR) of every byte whose index equals $i$ mod $M$. For example, if $M=2$, one byte is the sum of all the bytes in the even positions, and the other one is the sum of all the bytes in the odd positions. Since bursts have length at most $M$, each of these checksums will only be missing a single byte.


Spanning trees on disconnected graphs Can anyone please help me out with my query: can disconnected graphs have minimum spanning trees?

A spanning tree, by definition, has the same vertices as the graph it spans. Since such a tree is an induced subgraph and, since trees are (by definition) connected, the graph itself must be connected.

Note this applies to any spanning tree, not just a minimal one (i.e., an MST).


find shortest paths from source to all vertices using Dijkstra’s Algorithm? For Dijkstra’s,i can find shortest paths from source to all vertices in the given graph but how can i calling the algorithm |V| times taking each vertex as a source and store all tables ???
For example :
What is the shortest path from 1 to 4? You need to print the value and the exact path vertices starting from 1 and ending at 4.

I am assuming here that you want to calculate the all-pairs shortest paths for a graph using Dijkstra's.

First, to find the shortest path between all pairs of vertices, you can create a $ |V|^2 $ matrix where row and column i and j corresponds to the shortest distance from vertex i to vertex j.

Second, to mark the all-path shortest paths' path, you simply set the parent property of each vertex j to the current vertex i you are visiting from every time you have to relax the edge going to j from i. Keeping one set of vertices and edge will be sufficient as an APSP will also produce a tree, similar to a SSSP tree.


Spanning Tree - Equivalent Properties I am working on the following problem:

Suppose that $T$ is a spanning tree of a graph $G$, with an edge cost function $c$.  Let $T$ have the cycle property if for any edge $e' \not \in T, c(e') \geq c(e)$ for all $e$ in the cycle generated by adding $e'$ to $T$.  Let  $T$ have the cut property if for any edge $e \in T$, $c(e) \leq c(e')$ for all $e'$ in the cut defined by $e$.
Show that the following three properties are equivalent

T has the cycle property,
T has the cut property, and
T is a minimum cost spanning tree.

I believe that to show that 3. implies 1., we suppose otherwise, and then show that this would give a cycle with an edge that can replace another edge in T and that is cheaper, whence we have a contradiction.  Similarly, I believe to show that 3. implies 2., we similarly suppose otherwise, and then show that this would give a cut with an edge that can replace another edge in T and that is cheaper, whence a contradiction.
However, I am not sure how to prove the other implications needed for this problem.  My feeling is to somehow use a similar argument to what I listed, but "in reverse".
Any help with this problem would be greatly appreciated.

Continuing where @ijkilchenko left off.

$2\to 3$: Let $T$ have the cut property and let $T'$ be any other spanning tree of $G$. For each $e\in T$, there is some edge $e'\in T'$ that crosses the cut defined by $e$. Define $f : E(T) \to E(T')$ by mapping each edge $e \in E(T)$ to the edge $e' \in E(T)'$ with smallest weight among those crossing the cut defined by $e$.  According to the cut property $w(e)\le w(f(e))$, so we get
$$ w(T) = \sum_{e \in T} w(e) \le \sum_{e\in T} w(f(e))\le \sum_{e'\in T'} w(e') = w(T')$$
where the third inequality comes from the fact that if $f$ is not injective, it only decreases weights.  Since $T'$ was arbitrary, we have shown that $w(T)$ is minimum among all spanning trees of $G$, and we are done.

$3\to 1$: If $T$ does not have the cycle property, the definition supplies us with an edge $e\in T$ and $e'\notin T$ such that $w(e') < w(e)$, so $T - e + e'$ is a tree with weight less than $T$. Therefore $T$ does not have minimum weight.


Why does n! have the least time? I was reading the book Introduction to Algorithms, Chapter 1. When I saw this diagram, I got confused because $\lg n$ has the largest value of time while $n!$ has the least value of time. And that doesn't make sense to me - perhaps I misunderstood this?

The numbers in the table are not times; they're the rough sizes of the input $n$, for which the algorithm would take the amount of time in the column labels to run.

i.e. you'd need to give an algorithm of logarithmic complexity input of size on the order of $2$ to the something enormous in order to get it to run for a century, but for an algorithm of complexity $O(n!)$ you only input of size ~10 to make it run for that long.

One of the main things to take away from this table is how the numbers grow as you go across some row, and compare this growth rate for different rows.

For example, for logarithmic complexity the size of the input grows exponentially with the increase in time, while for exponential and factorial complexities the input size grows sublinearly with the time increase (though this is a bit obscure just from the table because the time scale is not linear).


Determine number of blocks in a cache The question is: We need to design a cache with cache size of 128K bytes, block (line) size of 8 words, and word size of 4 bytes. Consider a computer with 64-bit physical address. The cache is addressed by physical address

I need clarification on this: if we have 128k bytes and each block equals 32 bytes (8*4), do we have: 1.($128$ x $2^{10}$)/$32$ or 2. $128k/32$. The problem is that the first gives 4096 blocks and the second gives 4000 blocks. Which is the correct one?

The common usage is for KB, MB, GB, TB, and so on to denote powers of 2 rather than powers of 10. There are ways to denote powers of 10, but they are infrequently used. See for example the Wikipedia page on kibibyte.


Store and sort a large number of 64-bit integers I have about $500000000$,  $64$-bit integers, so these numbers are very large.
I want to sort them as quickly as possible. I have couple of questions:

What data structure do you suggest for storing this data?
What algorithm do you suggest for sorting these numbers?

I'm concerned about speed.

You're not going to get much in the way of programming tips here, this is a site for computer science, not programming.

For the sorting algorithm, you probably want to use Radix Sort, which will run in time $O(k n)$, for you $k = 64$ and $n = 500 000 000$.

For the storing of these numbers, you might want to look into compressed data structures. However, these are necessarily going to bring some overhead. You're looking at approximately 4GB of memory, which is reasonable on many modern machines. As you will learn in computer science, there is often a tradeoff between time and space. Here, you must choose between a fast data structure and a space-efficient data structure.

EDIT: I change the time complexity to $O(kn)$, I'd mistyped and originally written $O(k\log n)$. Sadly, it's impossible to sort a list without actually looking at the entire contents of the list.


XOR operation to swap to value without additional variable I'm breaking my mind to find a good explanation to split two variables with the XOR operation.
The operation is the following:
x ^= y # =>                      (x ^ y, y)
y ^= x # => (x ^ y, y ^ x ^ y) = (x ^ y, x)
x ^= y # => (x ^ y ^ x, x)     = (y, x)

and my doubt is about the second line, in particular (x ^ y, y ^ x ^ y) = (x ^ y, x)  how I can have the result X from the operation y ^ x ^ y?
I know that y^y = 0, but in the previous case I can not say that y^x^y is equal to x.
What I'm losing here?
Source

First, xor is commutative and associative, therefore (a xor b) xor c = a xor (b xor c) = a xor (c xor b) = (a xor c) xor b, and in your case that means (x xor y) xor x = (x xor x) xor y = 0 xor y = y.
But this is just a rather pointless programming trick. It only works for integers, it can't be used for floating point numbers, strings, booleans, pointers etc., so it is pointless. It wouldn't pass any code review, so you can't ever use it in real life.


Advice for statistics/ML problem I've been studying a particular problem recently, and it seems like there might be techniques from statistics or ML that could be applied. Any advice or comments would be appreciated.

We're given some set of values sampled from a particular distribution. The values themselves are hidden to us, but their frequencies are known. We don't know the exact distribution the hidden values are drawn from, but using other information we've developed a model/approximation of it that probably has some errors, both in terms of missing elements and the frequency of a particular element. Our eventual goal is to map elements of our approximate distribution to their hidden counterparts in our target distribution.

For some small number of hidden values, we're also given the actual member of the distribution this value corresponds to. In a sense, a few of the hidden things are 'revealed' to us, but most of them remain hidden.

Is there any way for us to take the information we get from the revelation of the small number of values from our 'real' distribution and use it to refine our approximation of the entire target distribution, and not just the values that were revealed?

Obviously we know with certainty which elements of our approximate distribution correspond to the hidden values that were revealed, but can we use the fact that we also know 'how far off' our approximation was for those values to make our approximation more accurate for other values?

I would suggest using bipartite matching.  Have one vertex on the left side for each hidden value you observed.  Have one vertex on the right side for each value in your approximate distribution (your model for the underlying distribution).  Draw an edge between each pair of vertices $(u,v)$, with a weight based on how similar their counts (frequencies) are.  Look for a matching of maximal weight.

This will work if you have no other information about the hidden values, other than their frequencies.  If you also have some information about their order or other side information, I don't know how to use bipartite matching for that.


An algorithm to turn descending order into ascending order, but why correct? Why is this sort algorithm correct? Many thanks!

Task:

Suppose all elements in an array with length $n = 2^m$ are in descending order: $a_1 > a_2 > ... > a_n$, we need to turn them into ascending order.

Algorithm:

For each step from $1$ to $m$:

Swap each adjacent (odd index, even index) pair into ascending order, so that:
$a_1 \le a_2, a_3 \le a_4, ... , a_{n-1} \le a_n$
Move all elements with odd index to the front of those
with even index, so $a_1, a_2, a_3, a_4, ..., a_{n - 1}, a_n$ turns to : $a_1, a_3, ..., a_{n - 1}, a_2, a_4, ..., a_n$

Example:

Sort result after each step with $n = 8$:

[0] 8 7 6 5 4 3 2 1
[1] 7 5 3 1 8 6 4 2
[2] 5 1 6 2 7 3 8 4
[3] 1 2 3 4 5 6 7 8

Code:

#include <stdlib.h>

void swap(int *arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void magic_sort(int *arr, int *result, int n)
{
    int half = n >> 1;
    int i;

    /* Swap adjacent (odd index, even index) pair into ascending order */
    for (i = 1; i <= n; i += 2)
    {
        if (arr[i] > arr[i + 1])swap(arr, i, i + 1);
    }

    /* Move all elements with odd index to front half */
    for (i = 1; i <= n; i += 2)
    {
        result[(i + 1) / 2] = arr[i];
    }

    /* Move all elements with even index to tail half */
    for (i = 2; i <= n; i += 2)
    {
        result[half + i / 2] = arr[i];
    }

    for (i = 1; i <= n; i++)
    {
        arr[i] = result[i];
    }
}

int main()
{
    int m = 3;
    int n = 1 << m;
    int *arr = (int *)malloc(sizeof(*arr) * (n + 1));
    int *result = (int *)malloc(sizeof(*arr) * (n + 1));
    int step, i;

    printf("[%d] ", 0);

    for (i = 1; i <= n; i++)
    {
        arr[i] = n + 1 - i;

        printf("%d ", arr[i]);
    }

    printf("\n");

    for (step = 0; step < m; step++)
    {
        magic_sort(arr, result, n);

        printf("[%d] ", step + 1);

        for (i = 1; i <= n; i++)
        {
            printf("%d ", arr[i]);
        }

        printf("\n");
    }

    free(arr);
    free(result);

    return 0;
}

This is an interesting algorithm.

Conventions

Array indexes start with 0. Note this convention is different from the convention used in the question. This convention helps us see what is going on more easily.

All arrays have length $n=2^m$ for some positive integer $m$.

Given any array $b_0, b_1, b_2, b_3,\cdots, b_{n - 2}, b_{n-1}$, the magic shuffle $M$ maps it to the array $b_1, b_3, \cdots, b_{n-1}, b_0, b_2, \cdots, b_{n-2}.$ Please note that I avoid using the term "sort" since this algorithm is hardly about sorting.

Let $A_0$ be the array $a_0, a_1, \cdots, a_{n-1}$ (that is, $A_0[i]=a_i$). Define $A_k$ recursively by $A_{k+1}= M(A_k)$.

Claim: $A_m$ is the reverse of $A_0$, which is $a_{n-1}, a_{n-2}, \cdots, a_0$.

Proof of the claim. For an array $B$, we can check by the definition of the magic shuffle, $$M(B)[i] = \begin{cases} B[2i+1] & \text{ if }i\lt 2^{m-1},\\
B[2(i-2^{m-1})]&\text{ if } i\ge 2^{m-1}.\end{cases}$$

For an integer $i=i_{m-1}2^{m-1} + i_{m-2}2^{m-2} + \cdots + i_12 + i_0$, where $i_t\in\{0,1\}$, let $(i_{m-1}i_{m-2}\cdots i_1i_0)_2$ be its representation in base 2. We can easily check that

$$M(B)[(i_{m-1}i_{m-2}i_{m-3}\cdots i_1i_0)_2] = B[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2]$$
where $\overline{x}=1-x$ for $x=0,1$. So we have
$$A_1[i] = M(A_0)[i] = A_0[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2]$$
$$A_2[i] = M(A_1)[i] = A_1[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2] = A_0[(i_{m-3}\cdots i_1i_0\overline{i_{m-1}}\overline{i_{m-2}})_2]$$
$$\cdots$$
$$A_{m-1}[i] = M(A_{m-2})[i] = A_{m-2}[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2] = A_0[(i_0\overline{i_{m-1}}\overline{i_{m-2}}\cdots\overline{i_2}\overline{i_1})_2]$$
$$A_m[i] = M(A_{m-1})[i] = A_{m-1}[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2] = A_0[(\overline{i_{m-1}}\overline{i_{m-2}}\cdots\overline{i_2}\overline{i_1}\overline{i_0})_2]$$

Since $i + (\overline{i_{m-1}}\overline{i_{m-2}}\cdots\overline{i_1}\overline{i_0})_2 = (\overline1\overline1\cdots\overline1\overline1)_2 = n-1$, we have proved the claim.

An exercise

Let $a_0, a_1, \cdots, a_{n-1}$ be an array of length $n=2^m$ for some positive integer $m$. For each step from 1 to m, repeat the following shuffle. For each term in the front half of the array, insert right before it the $n/2$-th term after it. Here is the result array after each shuffle for $n=16$.

[0]  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
[1]  9  1 10  2 11  3 12  4 13  5 14  6 15  7 16  8
[2] 13  9  5  1 14 10  6  2 15 11  7  3 16 12  8  4
[3] 15 13 11  9  7  5  3  1 16 14 12 10  8  6  4  2
[4] 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1

Show that we will obtain the initial array reversed in the end of $m$ shuffles.

If you consider the array as a deck of cards, then this shuffle is the (perfect) in (riffle) shuffle. In particular, if you repeat 10 in shuffles on a deck of 32 cards, you will end up with the deck of cards in its original order.


Converting an infix expression to postfix So the question is to convert the following expression to postfix:

(a+b)^(p+q)^(r*s*t)

The answer I get when I calculate is: ab+pq+^rs*t*^

But the answer is given to be ab+pq+rs*t*^^

I assume that the step when you need to push second '^' into stack when there is already a '^' in the stack is where I went wrong (I pop out the '^' before pushing). Shouldn't we pop out the first '^' as they are of equal precedence ? Or is it an exception to '^' operator ?

There is a sort of an exception to '^', the exponentiation operator since it is right associative. That is, $a^{b^c}$ means $a^{\left({b^c}\right)}$ instead of $\left(a^b\right)^c$. That is, (a+b)^(p+q)^(r*s*t) means (a+b)^((p+q)^(r*s*t)) instead of ((a+b)^(p+q))^(r*s*t).

When you reach the first ^ while evaluating postfix expression ab+pq+rs*t*^^, you will pop out the result of rs*t* and the result of pq+. You get the expected exponentiation as expected.


Is there a O(log n) algorithm for matrix exponentiation? Is there an algorithm to raise a matrix to the $n$th power in $O(\log n)$ time?

I have been searching online, but have been unsuccessful thus far.

Here is the pseudocode for an $O(\lg n)$ matrix exponentiation algorithm. Note that the * operator denotes ordinary matrix multiplication.

MATHPOWER (M, n)
if n == 1
    then return M
else
    P = MATHPOWER (M, floor(n/2))
    if n mod 2 == 0
        then return P * P
    else
        return P * P * M


Understanding the "ordering of the four types of edges" in DFS The following is Exercise 22.3-6 from CLRS (Introduction to Algorithms, the 3rd edition; Page 611).

  Show that in an undirected graph, classifying an edge $(u,v)$ as a tree edge or a back edge according to whether $(u,v)$ or $(v,u)$ is encountered first during the depth-first search is equivalent to classifying it according to the ordering of the four types in the classification scheme.

Problem: What does it mean by "the ordering of the four types in the classification scheme"? In particular, what does the "ordering" refer to? What is supposed to prove?

The classification scheme is defined on page 609:

  We can define four edge types in terms of the depth-first forest $G_{\pi}$ produced by a depth-first search on $G$:

  Tree edges are edges in the depth-first forest $G_{\pi}$. Edge $(u,v)$ is a tree edge if $v$ was first discovered by exploring edge $(u,v)$.
  Back edges are those edges $(u,v)$ connecting a vertex $u$ to an ancestor $v$ in a depth-first tree.
  Forward edges are those nontree edges $(u,v)$ connecting a vertex $u$ to a descendant $v$ in a depth-first tree.
  Cross edges are all other edges. They can go between vertices in the same depth-first tree, as long as one vertex is not an ancestor of the other, or they can go between vertices in different depth-first trees.

Added Example:

Consider the figure below.

Suppose that a DFS starts from node $u$ and travels along $(u,x)$ first and then $(x,v)$. Both $(u,x)$ and $(x,v)$ are tree edges.

What about the edge $(v, u)$? It should be a back edge according to the classification scheme in the textbook.
How is $(v,u)$ classified as back edge according to the classification in the exercise?

Is $(v,u)$ a tree edge while $(u,v)$ a back edge according to the definition in the exercise? This is strange, because in an undirected graph, $(u,v)$ and $(v,u)$ refer to the same edge.

I have reviewed section 22.3, "Depth-first search" a couple of times.

"What does it mean by "the ordering of the four types in the classification scheme"? In particular, what does the "ordering" refer to?

While quoting the textbook, You have used 1, 2, 3 and 4 to label the four cases in the classification scheme. That is an ordering. All it means is that $1 \prec 2 \prec 3 \prec 4$. In other words, tree edges precede back edges, which precede forward edges, which precede cross edges.

What is supposed to prove?

Suppose we have done a depth-first search $S$ on an undirected graph $G$ that has produced the depth-first forest $G_\pi$ as describe in the textbook.
An edge $e=\{u,v\}=\{v,u\}$ can be represented by either the directed edge $(u,v)$ or the directed edge $(v,u)$. Note that $(u,v)\not=(v,u)$. Both $(u,v)$ and $(v,u)$ will be explored during $S$. There are two methods to classify $e$ with respect to $S$.

$e$ is classified as the earliest type of edge (according to that ordering) which either $(u,v)$ or $(v,u)$ can be classified as.
More specifically, if either $(u,v)$ or $(v,u)$ is classified as a tree edge, then $e$ is classified as a tree edge. Otherwise, $e$ is classified as a back edge. Note that at least one of $(u,v)$ and $(v,u)$ must be classified as either tree edge or back edge (theorem 22.10 of the book).

If $(u,v)$ is discovered earlier than $(v,u)$, then $e$ is the same type of edge as $(u,v)$. If $(v,u)$ is discovered earlier than $(u,v)$, then $e$ is the same type of edge as $(v,u)$.

That exercise asks readers to prove the above two classifying methods are equivalent. That is, $e$ is classified as type $X$ by the first method if and only if $e$ is classified as type $X$ by the second method, given any edge $e$ and any type $X$.
(Somewhat informally, an edge is a tree edge if it appears in the resulting tree; otherwise it is a back edge. This seems to be the simplest way to label edges in an undirected graph with respect to a DFS.)

Let us take a look at the example given in the question.
Here is the relevant part of running DFS-VISIT $(G,u)$.

$u.d = 1$
$x.\pi = u$
$x.d = 2$
$v.\pi = x $
$v.d = 3$
Now we discover edge $(v,u)$, which connects $v$ to $u$, which is an ancestor of $v$ since $v.\pi=x$ and $x.\pi = u$. That is, $(v,u)$ is a back edge. This is the first time edge $e$ is discovered. So $e$ is a back edge according to second classifying method.
$v.f = 4$
$x.f = 5$
Now we discover edge $(u,v)$, which connects $u$ to its descendant $v$. This edge $(u,v)$ is classified as a forward edge. Since $(v,u)$ is classified as a back edge, a type of edges that precedes a forward edge, $e$ is a back edge according to the first classifying method.
$u.f = 6$

We just saw that $e$ is classified as the same type of edge according to either classifying method. That exercise asks readers to prove that is not a coincidence.


Tokenizer and complex operators I'm trying to create simple tokenizer to transform following (only part shown) search expression to tokens

word1 near(1) word2

where word1, word2 are some words and near(1) is distance operator.
The question is how this expression should be tokenized.
I see two ways

1. <WORD, word1> <WORD, near> <LPAREN> <NUMBER,1> <RPAREN> <WORD, word2>.
2. <WORD, word1> <NEAROP, 1> <WORD, word2>

But should I really try to tokenize NEAR(\d+) during tokenization, or should I go first way and handle NEAR operator at parser level, during building parse tree?

Since you indicate that the parameter of the near operator can be an arbitrary expression, it should be handled at the parser rather than at the lexer. Otherwise how would you handle things like near(x+y)?


Does a polynomial solution to weakly-NP Complete problem mean P = NP? Suppose someone finds a polynomial solution to weakly-NP Complete problem does that mean P = NP.

All weakly NP-complete problems are NP-complete by definition,
so yes, a polynomial time algorithm would imply P = NP.


Cuckoo filters for non powers-of-2 The Cuckoo filters paper (https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf) claims a 95% load factor, however it seems to make an implicit assumption that the table size is a power of 2, and their implementation also enforces that (https://github.com/efficient/cuckoofilter/blob/master/src/cuckoofilter.h#L90). This means that the load factor can be as bad as ~50%, depending on the number of keys.

The reason seems to be intrinsic to the alternate index algorithm: it is
$$
h_2(x) = h_1(x) \oplus hash(signature)
$$
The XOR makes the algorithm an involution (so the same formula holds to find $h_1$ from $h_2$), but the result is smaller than the table size only if the size is a power of 2.

Is there an alternative formula that works with non-powers of two? Basically something that pseudo-randomly maps signatures to involutions of [0, n).

Yes, it is possible.  Use

$$h_2(x) = \text{hash}(\text{signature}) - h_1(x) \bmod n.$$

The theory behind this: if $c$ is a constant, the function

$$f(t) = c - t \bmod n$$

is an involution for any $c$ and any $n$, since

$$f(f(t) = c - (c-t) = t \pmod n.$$

Therefore, we can use the hash of the signature as the constant $c$.  This gives you a scheme that works for any $n$, without requiring that $n$ be a power of two.


Given a list of strings, find every pair $(x,y)$ where $x$ is a subsequence of $y$. Possible to do better than $O(n^2)$? Consider the following algorithmic problem: Given a list of strings $L = [s_1, s_2, \dots, s_n]$, we want to know  all pairs $(x,y)$ where $x$ is a subsequence of $y$. We can assume all strings are of length at maximum $m$, where $m << n$ and are all over a finite alphabet $\Sigma$ with $|\Sigma| << n$. We may also assume that the number of pairs $(x,y)$ where $x$ is a subsequence of $y$ is much smaller than $n$.

A trivial algorithm would be this:

1. foreach x in L:
2.   foreach y in L:
3.      if x is subsequence of y:
4.         OUTPUT x,y

However, this has complexity $O(n^2 \cdot m)$ - I am curious to know whether there is a faster algorithm (Faster given that the number of pairs $(x,y)$ is much smaller than $n$, so for example an algorithm with complexity depending on the number of output pairs).

Note that this question is a follow up to this question, which is about the same problem but for substrings (not subsequences). There, the Aho-Corasick algorithm solved my problem perfectly - is there maybe somethign like this but for subsequences?

No, it is not possible to do better unless the Strong Exponential Time Hypothesis (SETH) fails. If we could solve this problem substantially faster than $O(n^2)$ we would immediately obtain a much faster algorithm for solving the NP-complete problem Satisfiability. This is true even for $m$ slightly more than $\log(n)$ and the case in which we want to decide whether such a pair $(x,y)$ exists at all.

See, e.g., these lecture notes under section 3 "Tight Lower Bounds for Orthogonal Vectors". The proof is analogous to the proof of Theorem 2 in these lecture notes.

First, we consider the more general problem of given two sets of strings $X,Y$, finding whether some string in $X$ is a subsequence of a string in $Y$.

Given a SAT formula, we split its $n$ variables into two equal sets of $n/2$ variables. In $\Sigma$ we take a character corresponding to every clause. In $X$ we add a string for every possible assignment to the first half of the variables, with a character corresponding to every clause not satisfied by those variables. Meanwhile, in $Y$, we add a string for every assignment to the second half of the variables, with a character for every clause that is satisfied by those variables. Clearly, the formula is satisfiable if and only if some string in $X$ is a subsequence of some string in $Y$.

If this problem can be solved substantially faster than $O(n^2)$, then this gives a substantially faster algorithm for Satisfiability than $2^n$. Suppose the problem could be solved in $O(n^{1.99})$ time, then Satisfiability could be solved in $(2^{n/2})^{1.99}=O(2^{0.996n})$ which contradicts SETH.

In your problem, there is only a single set of strings, all of which may be a subsequence of each other. This is however not a problem, as we can simply modify the strings in our instance such that no string $Y$ is a subsequence of any other string (for instance by padding all strings in $Y$ to have the same length), and similarly padding every string in $X$ to the same length as other strings in $X$ (but substantially shorter than strings in $Y$).

This can probably also be done with a constant-size (likely even binary) alphabet but this requires more clever encoding.


Ordering the tasks to minimize penalties So I just started learning greedy algorithms and I have a problem that I want to solve. The statement is as follows:

In your calendar you have an $L$ list of all the tasks you need to complete today. For each task $i \in L$ the duration $d_i \in \mathbb{N}$ is specified which indicates the time required to complete it and a penalty factor $p_i \in \mathbb{Z^+}$ which aggravates the delay. You must determine in what order to perform all the tasks to get the result that accumulates less total penalty.
Note that:
• In an instant you can only perform one task,
• Once you start a task, you must continue it until it is completed, and
• All tasks must be completed.
The actual penalty associated with a task $i \in L$ is the completion time $t_i$ of its completion, multiplied by its penalty $p_i$.
The completion time $t_i$ corresponds to the time elapsed from the start of the working day (i.e. from time instant 0) to the time the task has been completed.
Provide an algorithm (as efficient as you can) to solve it.

I have figured out that the completion of a task $i ∈ L$ with completion time $t_i$ must
started at instant $t_i - d_i$.
I'm stuck with the optimization criteria. I tried sorting the tasks by $p_i$ decreasingly, or by $p_i * d_i$ increasingly and doing the tasks in such order, but it doesn't work. I can find a counter-example for both approaches. What would be a good optimization criteria for this problem?

Note the minimum penalty for a task is always $p_i d_i$.
If I choose at a point in time to do task $i$, then all other tasks $j$ will incur an extra penalty of $p_j d_i$.
Therefore, you need to do the most expensive task first (i.e., having the largest $p_i$). If there are multiple such tasks, then the one with the shortest $d_i$ needs to be performed first.


Does assembly language get translated to binary code? If so, is assembly language portable across machines? I've tried to find the answer through Google but I've come across conflicting uses of terminology, so I just wanted to be absolutely clear.

Here is my understanding: High level code written in a high level language (C I think is one of the lowest-level high level languages) gets translated to assembly code by that language's compiler.

That assembly code then gets translated to machine code (aka binary code aka hexadecimal code) by something (not sure what does this translation).

Does that mean that assembly code, but not machine code, is portable across computers? Or is assembly also not portable, and the only thing portable is code written in a high level language?

Assembler code describes instructions for one particular architecture. It is slightly helpful by allowing you to use human-readable names for instructions, names for memory addresses, doing some simple calculations etc. but it is totally useless to produce instructions for any other processor.

With heroic effort you could create a translator that produces code for a different architecture but nobody would thank you for it. The advantage of assembler code is that it lets you write code for things high level software isn’t designed for - like writing the code to boot a computer, handle interrupts, doing a process switch - and that kind of code is often very machine specific; it might not even be usable on a different computer with the same processor.

So yes, for any portability you need a high level language.


An example of a computable problem that is not in P I am trying to find a simple example of a problem that is computable but not in P, I know very well that it would be enough to get one in NEXTIME-complete however the problems that I find in this set are very artificial

As Yuval Filmus already mentioned in the comments, because of the time hierarchy theorem, we know $\mathsf{P} \neq \mathsf{EXP}$. Hence, any $\mathsf{EXP}$-complete problem is an example. These include, for instance, generalized chess and checkers.


Number of states in classical planning With reference to the Heuristics section of Classical planning in Artificial Intelligence: A Modern Approach by Russell and Norvig, there is a question: consider
an air cargo problem with 10 airports, 50 planes, and 200 pieces of cargo. Each plane can
be at one of 10 airports and each package can be either in one of the planes or unloaded at
one of the airports. So there are 5010 × 20050+10 ≈ 10155 states.

I think it should be 1050 + (50+10)200 (each of the 50 planes can be in any of 10 places; each of the 200 packages can be in any of the 50 planes or unloaded at any of the 10 airports).

What is the actual number of states?

You're both wrong.  It should be $10^{50} \times (10+50)^{200}$.  If you have $k$ objects, and there are $n$ possible places for each, there are $n^k$ possible combinations of ways for where to put each of them.

This probably doesn't really change the main point that I suspect the AI book was making: there are a lot of possible states, far too many to iterate over one by one.


Computing the intersection of two NPDA where it is possible Apropois to Raphael's suggestion on Intersection of two NPDAs:

Let $A_1$ and $A_2$ NPDA for context-free languages $L_1$ and $L_2$, respectively. Assuming that we know that $L = L_1 \cap L_2$ is context-free, can we (effectively) construct NPDA $A$ for $L$?

Any type of algorithm would be acceptable, but the more practical the better.

I think this is possible for the subclass of CFLs that are permutation-invariant with a binary alphabet.

These correspond to type $\langle 1,1\rangle$ quantifier languages comparing the cardinalities of two sets. [1] characterizes such languages accepted by DPDA by the equivalent semilinear sets, and states at the end that quantifier languages accepted by NPDA are finite boolean combinations of such languages accepted by DPDA.

A theorem of van Benthem ([2]) says that pushdown automata accept type $\langle 1,1\rangle$ quantifiers definable in Presburger arithmetic (i.e. defined by semilinear sets). So, if you get two languages that are non-deterministic CFLs (using the first paper to know you have such examples), their intersection should also be a CFL by this theorem.

The semilinear set which is their intersection might be a bit difficult to compute... but, if you have that, [3] (pgs.11-12) give an algorithm for creating an NPDA accepting the language based on the generators of the corresponding semilinear set.

[1] Makoto Kanazawa. Monadic quantiers recognized by deterministic push-
down automata. In Proceedings of the 19th Amsterdam Colloquium, pages
139-146, 2013.

[2] Johann van Benthem. Essays in Logical Semantics. Studies in Linguistics and Philosophy Volume 29, 1986, pp 151-176.

[3] Marcin Mostowski. Computational semantics for monadic quantiers. Journal of Applied Non-Classical Logics, 8(1-2):107-121, 1998.


Vertex Cover special cases This was from a test from my university:

Consider $T = t_1, t_2, \cdots, t_n$ a set of intervals of the form $(s, e)$, representing the start and end time, respectively. Now, select the minimum number of intervals such that their "union" intersects all other intervals. The question then asked for an optimal greedy algorithm.

From what I can see, this is a vertex cover problem (each interval is a vertex; draw an edge between each pair of intervals that intersect), which is NP-complete on general graphs.

Consider $W(i)$ the number of intervals intersecting $i$, and $M$ a set of intervals already covered. Here is my solution:

Order $T$ by $W$ and insert in $T_{ord}$;
If $T_{ord} = \emptyset$ terminate
Remove the first element $e$ from $T_{ord}$;
If $e \in M$ go to $2$;
Decrease $1$ for every element $e^{'}$that intersect $e$, and $M \cup\{e,e^{'}\}$;
Order $T_{ord}$ and go to $2$.

I managed come up with a greedy solution, but couldn't come up with a counterexample. Given that, I was thinking if this is a special case of the vertex cover problem. Is it?

This is dominating set, not vertex cover.

The graph has the set of intervals as vertices and two vertices are adjacent if the corresponding intervals overlap. Such a graph is known as an interval graph, which is a special case of intersection graphs (vertices are sets of some kind, and two vertices are adjacent if their sets intersect).

You're looking for a minimum-sized set $S$ of intervals such that every other interval intersects at least one interval in $S$. In the interval graph, this means that you're looking for a minimum-sized set $S$ of vertices such that every other vertex is adjacent to $S$: this is a dominating set.

The problems of omputing minimum vertex covers and minimum dominating sets are both NP-hard on general graphs. However, on interval graphs, both problems can be solved in polynomial time, by

M.V. Marathe, R. Ravi and C. Pandu Rangan, Generalized vertex covering in interval graphs.  Discrete Applied Mathematics, 39(1):87–93, 1992.
K.S. Booth and J.H. Johnson, Dominating sets in chordal graphs. SIAM Journal on Computing, 11(1), 191–199, 1982.

In the former case, a $2$-vertex cover is an ordinary vertex cover; in the latter, the algorithm actually works for all for all directed-path graphs, and every interval graph is a directed-path graph.


Analysis of straight insertion I'm currently reading through N. Wirths': Algorithms + Data Structures = Programs. I'm not sure, but I think there might be an error in the analysis of the provided straight insertion sort. Screenshot of the relevant paragraph is here: screenshot

Edit: sentinel item a[0] = x, the current item that I want to insert at the appropriate place.

Sorry, another screenshot of relevant paragraph is here: screenshot2

    type index = 0..n
    var a: array[0..n] of item

    procedure straightinsertion
        var i,j: index; x: item;
    begin
        for i := 2 to n do
        begin x := a[i]; a[0] := x; j := i-1;
            while x.key < a[j].key do
                begin a[j+1] := a[j]; j := j-1;
                end;
            a[j+1] := x
        end
    end

I think, that the analysis of the number of comparisons might be wrong. He claims, that the number C_i of key comparisons in the i-th sift is at most i-1. But shouldn't it be i? Because at the worst case, since we are using sentinel, we have to make an extra comparison with the sentinel too. I claim, that:

C_min = n-1
C_ave = 1/4 * (n^2 + 3n - 4)
C_max = 1/2 * (n^2 + n) -1

The number of moves M_i should then be (i-1)+2. M_min, M_ave, M_max are, I believe, correct in the text (screenshot).

Could you please confirm if I'm right or is there something I'm missing?Thank you all very much!

Edit: My apologies, misunderstood what you meant by sentinel earlier. It seems to me that you are correct, and this is indeed a typo. When you include comparison against the sentinel at $a[0]$, you perform $i - 1 + 1 = i$ comparisons on a worst case sift.


Can we approximate the number of possible witnesses for an NP language? Assuming $L \in NP$, meaning that L could be verified by some $V(x,y)$, such that there exists a polynomial $P(X)$ such that $|y| \leq P(|x|)$ for every $x \in L$.

I was wondering - can I assume something about the possible witness space?
My intuition says that this number is bounded by $O(2^{P(|X|)})$ (all possible subsets of a certain problem, all possible strings by the length at most $P(X)$ etc...)

Thanks

The class of counting problems associated to languages in NP is called #P. More formally, $f:\mathbb{N}\rightarrow\mathbb{N}$ is in $\#P$ if there exists a nondeterministic polynomial time Turing machine $M$ such that for all $x\in\Sigma^*$, $f(x)$ is the number of accepting paths of $M$ on input $x$. This is equivalent to requiring the existence of a deterministic verifier $M(x,y)$ such that $f_M(x)=\big|\big\{y: M(x,y) \text{ accepts}\big\}\big|$.

You ask, given a language in $NP$ with it's verifier $M(x,y)$, can we approximate $f_M$? If the witnesses are of length $p(|x|)$ then obviously $0\le f_M(x)\le 2^{p(|x|)}$, but without knowing more about $M$ then we can't really say anything else about $f_M$. Note that computing $f_M$ is harder than asking whether a witness exists (obviously if you could count then you could determine existence). In fact, counting is considered much harder, as demonstrated by Toda's theorem (given an oracle for counting, one could decide the entire polynomial hierarchy in polynomial time).

So how hard is approximating such functions, or (allow me to focus on a specific $\#P$ complete language) how hard is it to approximate $\#SAT(\varphi)$, the number of satisfying assignments of a given CNF. In these lecture notes by Jonathan Katz, a constant factor approximation is considered, i.e. an algorithm producing a number inside the range $\left[2^{-k}\#SAT(\varphi),2^k\#SAT(\varphi)\right]$ for some fixed $k\in\mathbb{N}$. They show that with high probability, given an oracle for regular SAT, one can produce such an approximation in polynomial time (the algorithm can also be strengthen to yield an $1\pm p^{-1}(|\varphi|)$ approximation). So while exact counting is considered much harder than $NP$, an $NP$ oracle is enough to approximate $\#SAT$ with high probability.


What is the big O for $n^{\log n} + n!$? By intuition $n^{\log n}$ should be as the same as $n!$. By Stirling's approximation, $n!=n^ne^{-n}\sqrt{2\pi n}$, which makes me think both are also the same. So, is this $O(n!)$ or $O(n^{\log n})$?

Look at this
$$(\frac{n}{e})^{\log{n}} = \frac{n^{\log{n}}}{n} = n^{{\log{n}}-1}$$
And compare it with $(\frac{n}{e})^n$ (as $e^{\log{n}} = n$, because of $\log$ function property). By multiplying $n$ to the above eqautation you will get $n^{\log{n}}$. Hence, just we need to compare $n$ and $(\frac{n}{e})^{n-\log{n}}$. So, definitely, we will find that the growth of $n!$ is much higher than $n^{\log{n}}$.


Show that every grammar for an inherently ambiguous CFL has infinitely many ambiguities Prove that if a CFL $L$ is inherently ambiguous, then for any grammar $G$ with $L(G) = L$, there are infinitely many strings in $L$ that have (at least) 2 different derivations in $G$.

Here's a sketch of a proof I have in mind:

  Suppose $G = (V, \Sigma, P, S)$ is a grammar satisfying $L(G) = L$.  Then, since $L$ is inherently ambiguous, it must be that $G$ is ambiguous.  Hence, there exists a string, call it $z$, with two different derivations in $G$.  Now, if the right-hand side of every production in G is of length $\leq d$, and if $|z| \geq d^{|V| + 1}$, then by Ogden's Lemma, if
  $d^{|V| + 1}$ or more symbols of $z$ are marked arbitrarily, there exists a decomposition $z = uvwxy$ such that there exists a variable $A$ in G such that

  $S \Longrightarrow^* uAy $

  $ A \Longrightarrow^* vAx$

  $A \Longrightarrow^* w$

  Hence, every derivation of $z$ must at least contain the sentential forms $S \Longrightarrow^* uAy \Longrightarrow^* uvAxy \Longrightarrow^* uvwxy = z$

  In particular, we may indefinitely "pump" the sentential form $uvAxy$ in both derivations via repeated application of $ A \Longrightarrow^* vAx$.  Hence, the resulting two derivations must at least contain the sentential forms

  $S \Longrightarrow^* uAy \Longrightarrow^* uvAxy \Longrightarrow^* uv^iAx^iy \Longrightarrow^* uv^iwx^iy \in L$

  Both derivations; however, are still different, and thus we have that strings of the form $uv^iwx^iy \in L$, with $i \geq 2$ have 2 distinct derivations.  Hence, there are infinitely many strings in $L$ with 2 different derivations.

Now, I do see some problems with this sketch.  For one, we cannot guarantee that $|z| \geq d^{|V| + 1}$.  Second, even if $|z| \geq d^{|V| + 1}$, I'm not sure that we can guarantee that both derivations of z must contain the sentential forms $S \Longrightarrow^* uAy \Longrightarrow^* uvAxy \Longrightarrow^* uvwxy = z$.

  Given $k = |V|$, suppose that every string of length $\geq d^{k+1}$ is unambiguous in G.  Let $z$ be an arbitrary string in $L$, with $|z| \geq d^{k+1}$.  Then by Ogden's lemma, there exists a decomposition $z = uvwxy$ and a derivation of $uv^2wx^2y$, namely:

  $S \Longrightarrow^* uAy \Longrightarrow^* uvAxy \Longrightarrow^* uv^2Ax^2y \Longrightarrow^* uv^2wx^2y$.  Clearly, $|uv^2wx^2y| \geq d^{|V| + 1}$, and thus the provided derivation for the string is unique.  But now, mark only the characters in $uv^2wx^2y$ which appear in $u, w, \text{ or } y$. The resulting derivation for $uv^2wx^2y$, obtained using Ogden's Lemma, must differ from the previous derivation for $uv^2wx^2y$, contradiction.  Hence, there exists an ambiguous string of length $\geq d^{|V| + 1}$, and we may apply the argument above.

Intuitively, the reason the claim is true is that if a grammar $G$ had only finitely many ambiguous strings, then you could somehow resolve the ambiguity and come up with an equivalent unambiguous grammar $G'$, thus contradicting the inherent ambiguity. The way you would resolve the ambiguity is something like this: you would generate all small strings (say at most $\ell$, the length of the maximal ambiguous word in $G$) explicitly (and unambiguously), and modify the grammar so that all other strings that it generates are longer; for example, you could have a different subgrammar for every prefix of length $\ell+1$ which simulates $G$.

Of course, this is only one argument, there might be completely different ones.


Time complexity of recurrence function with if statement Given the following code.

public static int fc(int n, int p) {
    if (p == 0) {
        return 1;
    } if (p % 2 == 0) {
        int a = fc(n, p / 2);
        return a * a;
    } return n * fc(n, p - 1);
}

How to calculate the time complexity of this code in big-$\mathcal{O}$ notation? I already define the recurrence function, which is

\begin{equation}
T(p) =
\begin{cases}
  1, & \text{if}\ p=0 \\
  T(p/2) + 1, & \text{if } p \text{ is even} \\
  T(p-1) + 1, & \text{if } p \text{ is odd}
\end{cases}
\end{equation}

Assuming that $p = 2^k$, then $T(p) = T(2^k) = T(2^{k-1}) + 1$. By backwards substitution, the equation become $T(2^k) = T(2^{k-n}) + n$. When $k = n$, $T(2^k) = T(1) + k = 1 + \log p$. Thus, $T(p) = \mathcal{O}(\log p)$.

However, I think that it only holds for the best case. I want to know about the other cases as well. How do I prove the average and worst case for this code?

Let us prove by induction the following formula:

  $T(n)$ is the number of 0s in the binary representation of $n$, plus twice the number of 1s.

This certainly holds for $n = 0$. If $n$ is even, then $T(n) = T(n/2) + 1$, and indeed the binary representation of $n/2$ differs from that of $n$ by having one less 0. If $n$ is odd, then $T(n) = T(n-1) + 1$, and indeed the binary representation of $n-1$ differs from that of $n$ by having one 1 replaced by 0.

This shows that $T(n) = O(\log n)$. It is not clear what you mean by average case, but the formula above should let you work that out. For example, let us consider the $2^{m-1}$ numbers of length exactly $m$. Each of them has a leading 1, and the other $n-1$ bits are half 0, half 1 (considering all numbers in the range). Hence the average value of $T$ for $2^{m-1} \leq n < 2^m$ is $m + 1 + \frac{m-1}{2} = \frac{3m+1}{2}$. Using this, we can compute the average value of $T$ for $0 \leq n < 2^m$ to be
$$
\frac{T(0)}{2^m} + \sum_{\ell=1}^m 2^{\ell-1-m}\frac{T(2^{\ell-1}) + \cdots + T(2^\ell-1)}{2^{\ell-1}} =
\frac{1}{2^m} + \sum_{\ell=1}^m 2^{\ell-1-m} \frac{3\ell+1}{2} = \frac{3}{2}m - 1 + \frac{1}{2^{m-1}}.
$$


Without using pumping lemma, can we determine if $A =\{ww \mid w \in \{0,1\}^* \}$ is non regular? Without using pumping lemma, can we prove $A =\{ww \mid w \in \{0,1\}^* \}$ is non regular?

Is $L= \{w \mid w \in \{0,1\}^* \}$ non regular? I'm thinking of using concatenation to prove the former isn't regular. If L is non regular then so is LL

Your idea (while interesting) is unlikely to work for two reasons:

How would you express $A$ as a concatenation of a language with itself?
If $L$ is non-regular, it may still be the case that $LL$ is regular. See this post:
Is $A$ regular if $A^{2}$ is regular?

You could prove it using the Myhill-Nerode theorem - show that there are infinitely many equivalence classes. Or you could simply use a pumping argument without the lemma. That is, follow the proof of the lemma for this particular language.


Binary counter amortized analysis This is a question I have stumbled upon in my textbook, and didn't really know how to approach:

Given a $k$-bit binary counter.
We have an operation Increment, which adds 1 to the counter.
We add a new operation Decrement, which subtracts 1 from the counter.
Prove that the cost for executing $n$ operations is $\Theta(nk)$.

Hint: Think of a value $n$ such that the transition from $n$ to $n+1$ and back is very costly.


Given a function and its complexity, what is the complexity of its circuit? For example,
given an element-wise function $f$, with input $x\in\{0,1\}^{p\times n}$, the complexity $T(f(x))=O(n)$, and that all numbers are represented using $p$ binary digits. Suppose that we also know the complexity of each individual operations inside $f$. For example, multiplication takes $O(m^{1.585})$ using Karatsuba algorithm, here $m$ is the number of digits of the product. Similarly, suppose that we know all the complexity of arithmetic operations like addition, subtraction, division, square root etc. In addition, suppose that we also know the complexity of all the basic boolean cells, e.g. Full Adder, Subtractor, Multiplier etc.

What is the complexity, in terms of number of boolean gates, of its equivalent boolean circuit? Can we derive a formula containing $n,p,m$?

If so, what is the complexity of a boolean circuits of a Cholesky decomposition, with input $X\in\{0,1\}^{p\times n\times n}$?

There is no mapping from algorithmic complexity to circuit size. A counterexample: consider the language of strings of all ones, $1^n$, for only those $n$ such that the $n$-th Turing Machine rejects the string $1^n$ within $2^{2^n}$ time. Then this function requires $\Omega\left(2^{2^n}\right)$ time to compute on any machine, but the circuit for it only has size $O(n)$, because you can "hard-wire" the answer into the circuit, which then only checks that all the inputs are $1$.

D.W. provides a construction from an algorithm to a circuit. However, note that this gives only an upper bound, which is not necessarily tight. In particular, no function requires circuits of size larger than $O\left(\frac{2^n}{n}\right)$, because that is the size of a circuit which simply enumerates that function's truth table for inputs of size $n$.

Consequently, if an algorithm takes $O(2^{2^n})$ time, then you can use D.W.'s construction for a circuit of size $O(2^{2^n}\log(n)^2)$, but it is immediate that this bound is not tight; there is also a circuit of size $O(\frac{2^n}{n})$, and there may be a much smaller circuit for it, as in the example above. What we really want to know when we ask what is the size of this function's circuit is a lower bound: a minimum size for any circuit.

Circuit size lower bounds is a particularly enigmatic part of computational complexity about which very little is known. For example, we do not know whether or not SAT can be solved with $O(n)$-size circuits, and we have not ruled out that each problem in NEXP can be solved with polynomial-size circuits.


Is OS mode required for accessing general purpose registers In which of the following cases a process executing in user model is required to enter into the OS mode?

(a) Decreasing the value of unsigned integer value in a register to less than 0

(b) Accessing general purpose register

(c) Executing printf()

(d) Adding values in two registers using ADD

In my opinion, both (c) and (b) should use OS mode. But my solution manual says only (c) uses OS mode.

I believe that (b) requires the use of OS mode as well, because the processor may have more than one process executing at the same time. As both of them have access to the general purpose register, it is quite possible that one process may overwrite the contents of another process if switching takes place.

The only way it can be avoided is setting up of a semaphore. At the end of the day, it boils down to a critical section problem. So, for accessing and setting up a semaphore, OS mode is required.

So, in my opinion, (b) should be true as well.

Am I correct or where is my reasoning wrong regarding the problem?

Thank you!

Computations on general-purpose registers ((a), (b), (d)) doesn't require any privileges.

Input/output requires privileges, to access a peripheral or to communicate with the part of the system that manages files. So (c) does generally require going to kernel mode. It's possible for some printf calls to remain entirely within the calling process, for example if output is buffered and the output of this call is going entirely inside the buffer. But in general a printf call does need to do actual I/O and thus does need a transition to kernel mode.

A processor does not really “have more than one process executing at the same time”. The processor alternates between executing different processes, but at a given point in time, it's only executing one process (or it's in kernel mode). On a multiprocessor machine, each processor¹ executes one process at a given time, but the different processors can be executing different processes. While a process is executing, it can access the general-purpose registers directly. It doesn't need the kernel for that. (And how would it ask the kernel, anyway? A process communicates with the kernel by placing the parameters of a system call in general-purpose registers and then invoking the system call instruction.)

Processes execute code as if the other processes didn't exist. When the kernel decides to switch to another process, it suspends the running process and unsuspends the process that it wants to run next. Part of this suspension mechanism is to save the values of the general-purpose registers into a dedicated memory area that belongs to the process that is being suspended. There is one such register store for each process². Part of the unsuspension mechanism is to restore the registers of the process that is being unsuspended. When a process is unsuspended, it keeps running where it left off, with the same values in registers as when it was suspended. This suspension/unsuspension mechanism is called a context switch.

A process never overwrites the registers used by another process because only the currently running process's register values are in the processor registers. The other processes' register values are in their register store. There has to be a context switch to change which process's register values are in the processor registers.

Switching between processes does not involve semaphores. It's the other way round: in order to use semaphores to synchronize between different processes, the processes need to call the kernel.

¹  Each core, each thread — whatever you call the single-threaded processing unit.
²  More generally, for each kernel thread.


Why is the k-bounded spanning tree problem NP-complete? The $k$-bounded spanning tree problem is where you have an undirected graph $G(V,E)$ and you have to decide whether or not it has a spanning tree such that each vertex has a degree of at most $k$.

I realize that for the case $k=2$, this is the Hamiltonian path problem. However I'm having trouble with cases where $k>2$. I tried thinking about it in the sense that you can add more nodes onto an existing spanning tree where $k=2$ and maybe since the base is NP complete, adding things on will make it NP-complete as well, but that doesn't seem right. I'm self-studying CS and am having trouble with theory, so any help will be appreciated!

The question has been asked before on stackoverflow, where it has also been answered. The idea is to connect each vertex to $k-2$ new vertices. The new graph has a $k$-bounded spanning tree iff the original graph has a hamiltonian path.

Mohit Singh and Lap Chi Lau gave a polytime algorithm which find a $(k+1)$-bounded spanning tree if a $k$-bounded spanning tree exists. So we can determine the minimum degree of a spanning tree up to an uncertainty of $1$.


Packing chocolate boxes I've been trying to solve an interesting problem created by one of my friends. The following is the problem statement:

There are $n$ types of chocolates. $\langle a_1,a_2,a_3....a_n \rangle$ are positive integers which represent the number of chocolates of each type. These chocolates must be packed into boxes of capacity $k$ i.e. each box can contain at most $k$ chocolates. Also no box can contain two chocolates of the same type i.e. the chocolates in every box must be of distinct types. What is the minimum number of boxes needed to pack all the chocolates?

A greedy approach would be to iteratively fill boxes by picking chocolates from the top $k$ types (in terms of number of remaining chocolates). However this is not of polynomial time complexity.

I also tried to solve the decision version of the problem. (can the chocolates be packed using $m$ boxes ?). I was able to model it as a max flow problem but the number of vertices was not polynomial in the input size.

Is this problem NP-Complete? If not what would be a good polynomial time algorithm to solve it?

The greedy algorithm will find an optimal solution: As long as there are more than k different chocolates, fill a box with one each of the k chocolates where the most pieces are left. Then as long as there are any chocolates left, fill a box with one of each of the chocolates. That solution is linear in the number of chocolate pieces but unfortunately not linear in the problem size. So instead of doing the greedy algorithm, we simulate how it would run and calculate how many boxes would be filled, in polynomial time.

Let $x_i$ be the number of pieces of type $a_i$. Sort in descending order, then remove the chocolates where $x_i$ = 0. If n ≤ k you need $x_1$ boxes.

As long as $x_k$ > $x_{k+1}$ you would put chocolates $a_1$ to $a_k$ into a box. This fills $x_k - x_{k+1}$ boxes, and you decrease $x_1$ to $x_k$ by $x_k - x_{k+1}$. You simulate this in constant time.

After that you have $x_1$ to $x_j$ greater than $x_k$, and $x_{j+1}$ to $x_m$ equal to $x_k$, for some j < k and m > k. So you have a larger number of j chocolates, and an equal number of m-j chocolates, m > k. You would fill m-j boxes by putting m-j of the chocolates $a_1$ to $a_j$ into each box, and filling with k-j of the chocolates $a_{j+1}$ to $a_m$.

You would do that t times. t is limited: With each round of m-j boxes, the number of the top j chocolates is reduced by m-j, the next chocolates are reduced by k-j. The difference is reduced by t (m-k), so t ≤ $(x_j - x_{j+1}) / (m-k)$. The next chocolates are reduced by t (k-j), so t ≤ $(x_m - x_{m+1}) / (k-j)$, letting $x_{m+1} = 0$ if m = n. You take the largest possible t and simulate t (m-j) steps in constant time.

When this is done (and t may be 0) we remove all chocolates with a zero count, and we may be done. If not, then we do one simulation step which will change the situation, and start all over.

That's the idea. You can probably clean this up a bit.