Reduction from P to NP Conceptually, I know that reducing a problem $Y$ that's NP-complete to a problem $X$ implies that $X$ is at least as hard as $Y$, implying $X$ is also NP-complete. So if any NPC problem, say $Z$, can be solved in polynomial time, then that implies $P = NP$, since any other NP-complete problem can be reduced to $Z$ in polynomial time, and then solved in polynomial time. But what does it mean to reduce a problem in $P$ to a problem in $NP$? I feel like this is self-evident (problems in P are no harder than problems in $NP$), but is there any example that can make this clearer?

Note: this answer assumes that we are considering polynomial-time reductions (and not e.g. log-space ones).

If $A$ belongs to $P$, then we can reduce $A$ to any nontrivial language, i.e. any $B\neq \emptyset,\Sigma^*$.

Reducing $A$ to $B$ can be done as follows. Fix $b_1\in B, b_0 \in \overline B$ arbitrarily. The reduction algorithm then takes an input $x$ and tests whether $x\in A$: if that holds, return $b_1$, otherwise return $b_0$.

Note that all of this can be run in polynomial time since $A$ belongs to $P$. This allows to solve the $A$ instance in the reduction algorithm itself, trivializing the reduction.

This proves that problems in $P$ are indeed the easiest possible ones, according to the "polynomial-time reduction" preorder.


What can distributed computing do besides parallel computing? I have some experiences of working on clusters and grids for parallel computing. But I wonder what distributed computing can do besides parallel computing?
If I understand correctly, parallel computing is to solve a common task by multiple processors (computers).

Are the Internet and a intranet considered distributed systems? They don't necessarily involve parallel computing, or solving a common task by multiple computers.

Distributed computing can be seen as a special case of parallel computing with some additional features and restrictions, some of which I'll outline here.

Multiply IO throughput

In some settings, e.g. databases, IO is the main limiting factor of performance, e.g. hard drive accesses. By serving requests on many machines, you can parallelise hard drive accesses (not possible in typical many-core machines).
Avoid slow IO

Real machines have technical limits regarding quick memory. These limits change constantly, but at any given point in time every machine can only hold so much data in RAM. A distributed system can be scaled so that all data resides in RAM, thus eliminating the need to resort to slower mediums.
Focus on throughput over response time

When faced with many small requests already dominated by, say, IO, you can not speed up individual requests anymore. Having multiple nodes serve requests can increase throughput.
Redundancy

Many nodes should be able to serve any given request so you can perform load balancing.
Consistency

When a requests not only retrieves but also changes data, many nodes may need to be informed of these changes. This is probably the factor with the most impact on performance.
Failure tolerance

The system as a whole should be robust against failure of individual nodes, i.e. continue to work (if with reduced throughput). This is not trivial since you can typically not hold all data on all nodes.
Communication cost

In a distributed system, nodes typically communicate over some kind of network. Delays in the order of milliseconds (typical response times in Ethernet) are prohibitive for systems/algorithms that require frequent communication. In specialised network implementations, wire length actually becomes a significant factor in delay times even inside a single server farm.
Security

If you don't control all aspects of the network connecting your nodes, the inner workings of your system are open to outside attack.

Note that all of these are interconnected.


Memory cells (addresses) read into a cache How does one determine what memory cells (addresses) are being read into a cache?

For example if we read at adress "C000EAFCH", which memory cells will be read into the cache if the cache is 64 byte and each cacheline is 8 byte?

If we use direct mapping, would one say that there are the 4 previous bytes and the 4 next bytes from the address that are being read?

In that case I would say that addresses C00EAF8H to C00EAFFH are being read. That would mean 4 bytes before the address, then the byte on the address and 3 more addresses are read.

However the one who asked this question wrote that the correct answer is C00EAF8 to C00EAFFH. I don't know why the 'H' disappeared in C00EAF8 but maybe it's a typo. To be honest I don't even know what the 'H' stands for, as it is not a hexadecimal character. Maybe someone can clarify this?

I also wonder, why doesn't one read the byte on the address, and then the next 7 bytes? Does this reading 4 bytes before and 3 bytes after have to do with direct mapping?

Cache lines are aligned.  That means that the bottom-most bits of the start address of the cache line are always 0s.

If you have 8-byte cache lines they will always be read in address ranges $[8i, 8(i+1) - 1]$.  For example, if you read address 117 (decimal) = 1110101 (binary) then the 8 byte cache block that gets read in is the set of bytes in the range 112 (decimal) = 1110000 (binary) through 119 (decimal) = 1110111 (binary).


How often is Prolog/ASP used in non-research areas? I've just recently found out about KRR (Knowledge representation and Reasoning) and ASP, not hearing a thing about them before (except a bit about prolog). I've read a bit about them and one of their primary usage seems to be AIs.

My question would be how widely used ASP or other declarative languages are, is there some frequently used program using them (like search engines?) or is it mostly for research purposes? What may be the reason they are not so well known? Is it because AI-development belongs to a more "advanced level" of programming?

how widely used ASP or other declarative languages are

You can see the activity of Prolog which I think is the most common ASP programming language:

SWI-Prolog Package Downloads: 483 downloads (not sure the interval), 239 packages.
Compare to Node.js Package Downloads underscore.js has 139,326 weekly downloads. Over 350k packages.

Just based on that, Prolog's top package is (483 / 139,326) x 100 = 0.35% as popular as one of Node.js's large packages. Or 0.07% as many packages.

  is it mostly for research purposes

IMO yes, it is mostly for research purposes. But it is similar to Ocaml, which from my experience was mostly for research purposes until corporate users like Facebook published Flow (typed JavaScript programming), and others published Coq (automated theorem proving), which helped bring Ocaml to the mainstream.

  What may be the reason they are not so well known?

IMO Prolog is not used because it is (a) a different paradigm, (b) the package manager isn't up to par (this is a big deal these days), and (c) there is no evangelized web framework. If there was a good package manager like NPM for Node.js, and there was a web framework that was marketed, as well as a small group of evangelists, that would help bring it to the mainstream. Ruby had 37signals and Rails, Python had Google, etc.

  Is it because AI-development belongs to a more "advanced level" of programming?

No not really. Some AI research uses prolog for modeling stuff, but it is not a requirement for AI. AI could be divided into two parts: (1) Machine learning / probabilistic-based models where the relations are learned and not well-defined, and then (2) manually defined models. Most AI is a mixture of both, but the manually defined models are valuable and kept private for the most part. The manually defined models could be defined using Prolog, and there are a few papers out there for doing that, but it is not necessary. To summarize, all AI work can be done in regular programming languages, just that Prolog might make it slightly more compact to write in some cases.


Is a circle inside a polygon? How do I test if a circle (x,y,radius) is inside a polygon ([x,y],[x,y],[x,y],[x,y]...) without touching the edges?

Update
I decided to do a point in polygon followed by a circle line collision on each edge, this let me know first if the circle was within the polygon and then told me if it was colliding with any of the edges.

Call the center point $(c_x, c_y)$. The function $d(p_x,p_y) = \sqrt{(p_x-c_x)^2+(p_y-c_y)^2}$ computes the distance from the point $(p_x,p_y)$ to the center of the circle.

For each edge of the polygon create its line equation from its two endpoints. If the two endpoints are $(a,b)$ and $(c,d)$ then this line is $y = (\frac{d-b}{c-a})\cdot(x-a) + b$. Solve for, $x$ and $y$ and plug this into the distance equation above, $d(x,y)$. Find the critical points by setting the partial derivatives equal to zero. Check that the critical points are further than the radius of the circle from the center of the circle.

If all critical points for all edges are more than the radius away from the center then the circle fits.


$UP=BPP$ implies $UP=RP$? https://cseweb.ucsd.edu/~mihir/cse200/ss6.pdf shows $NP$ in $BPP$ implies $NP$ in $RP$ by showing $SAT$ is in $RP$ if $NP$ is in $BPP$ and since $SAT$ is $NP$ complete we have $NP$ is in $RP$.

However since $UP$ does not have a complete problem and so can we still show $UP$ in $BPP$ implies $UP$ is in $RP$?

Suppose $L\in \mathsf{UP}$, and let $M(x,y)$ be a polynomial deterministic Turing machine such that:

$x\in L \Rightarrow \exists !y : M(x,y)$
$x\notin L\Rightarrow \forall y : \neg M(x,y)$

Consider the language $L'$ consisting of words in $L$ along with a prefix of a witness:

$L'=\left\{(x,w)\big|\exists w' : M(x,ww')\right\}$

Clearly $L'\in\mathsf{UP}$. Given an oracle for $L'$, one can find the witness for words in $L$ in polynomial time. If $\mathsf{UP\subseteq BPP}$, then $L'\in\mathsf{BPP}$, so you don't actually have an oracle for $L'$, but you have an oracle which is right with high probability.

Now, given $x$, execute the machine for finding a witness for $x$ with an $L'$ oracle, only that now you replace oracle calls with executions of the $\mathsf{BPP}$ machine (after some amplification, I leave the details for you). If the execution resulted in a valid witness $w$ for $x$, i.e. $M(x,w)$ outputs $1$, then output "yes", otherwise output "no". Clearly this solution can only be wrong for positive instances, which makes it a good candidate for an RP machine for $L$. I leave it to you to choose the right success probability to make everything work.

Essentially, the above solution uses the property of self reducibility, and in that sense the same proof as that for $SAT$, or any other self reducible problem in $\mathsf{NP}$.


Multiple Knapsack using Dynamic Programming Def MKP (Multiple Knapsack Problem): Given a set of n items and a set of m bags (m <= n), with

pj: profit of item j
wj: weight of item j
ci: capacity of bag i

select m disjoint subsets of items so that the total profit of the selected items is a maximum, and each subset can be assigned to a different bag whose capacity is no less than the total weight of items in the subset.

I'm wondering if there is a reasonable way of solving MKP using DP. I get the point in 0-1 Knapsack Problem. The recurrence is quite straightforward, add item/ not add item.

dp[item][capacity] = max{
     value[item] + dp[item - 1][capacity - weight[item]],
     dp[item - 1][capacity]}

However, I cannot see how to get an recurrence equation for the MKP. Should I extend the recurrence equation to "add item bag 1/ not add item bag 1/ add item bag 2/ not add item bag 2" and so on and so forth? It does not seem a good approach as the number of bags becomes larger and larger.

When all values are 1 and all capacities the same, this is the bin-packing problem, which is Strongly NP-Complete. Therefore, a sensible DP solution is probably not possible unless P=NP.

For very small m, say m=3, you can do:

dp[item][capacity1][capacity2][capacity3] = max{
     value[item] + dp[item - 1][capacity1 - weight[item]][capacity2][capacity3],
     value[item] + dp[item - 1][capacity1][capacity2 - weight[item]][capacity3],
     value[item] + dp[item - 1][capacity1][capacity2][capacity3 - weight[item]],
     dp[item - 1][capacity1][capacity2][capacity3]}


Find a continuous path filling whole 3xN grid going through certain points in given order I've got a grid consisting of squares that is 3 squares high and N squares long.
Some of the squares are filled with numbers that are not greater than 3*N. You can move only to squares that are below, above, on right, or left from you. When you move on a square, you fill that square with a number of the amount of moves you have already taken + 1. If square is already filled with a number, you can move onto it, only if the sum steps you've have taken + 1 is equal to the number on the square.

I need to find a continous path that leads through all the squares of the grid only once and output the same grid filled with numbers corresponding to the steps of your path. In other words, a path was previously laid out on the grid and then some numbers have been erased from squares. Now I have to retrace that path.

I should be done in O(N^2), but I will be thankful for any solutions.

Hint: if this is a homework problem that comes up in a chapter on graphs, you might want to consider forming a graph.

A common pattern in applications of graphs is to let each node in the graph represent the "state" of the world at some point in time, and then use that graph somehow.

Suppose you're following some continuous path through this grid, and at some point in time in the middle of your traversal, I yell "freeze!", temporarily pause time, and look at the state of the world at that point in time (ignoring past or future).  What information do I need to record, to fully describe the state of the world (where you are) at that point in time?  How many different possible states are there?  Now create a graph where ..., and.....  (you fill in the rest)


What happens to a file after too many copy-pasting? Let's say we're talking about a 1 GB video file. It's copy-pasted from hard disk D1 to the hard disk D2, then from D2 to D3, and so on, all using Windows. If we continue this process for like 1 million times, what would the resultant file look like? Do error bits accumulate and finally corrupt the file?

Once a single-bit error is introduced into a file, the file is corrupt.  File systems, disk drivers, and hardware on the disk itself have checksums, error correction codes, and facilities to detect bad sectors to limit the probability of write (or read) errors, but it's not 100% (but it better be close to 100%, otherwise my disk isn't reliable).

In general, the way to compute the probability of corruption:

Let's say the probability of a single bit error occurring during a file copy is P. (P should be really, really low, otherwise, the disk or media wouldn't be reliable).

And let's assume that a file has a size N measured in bits (e.g. a 1 GB file would be 8 billion bits or so).

So the probability of the first bit in the file not getting corrupted is: (1-P).  And so it follows that the probability of all bits not getting corrupted during a transfer is (1-P)N

Now let's say you copy the file X times.  Therefore the probability of the file not getting corrupted after X transfers is (1-P)NX.  Or rather, the probability of corruption after X transfers is 1 - (1-P)NX


Seating arrangement problem $n$ professors go to a conference and have to sit together at a table. See illustration below for $n=8$

Each professor has people they like to sit next to and people they do not want to sit next to. Given a $n\times n$ (non-symmetrical) matrix $M$ where $M_{ij}$ gives the score assigned by professor $i$ if s/he is made to sit next to professor $j$ and $M_{ii}=0$, the goal is to output a symmetrical indicator matrix $I$ where $I_{ij} = 1$ if professor $i$ is sitting next to professor $j$ such that $\sum M.*I$ is maximized (I used Matlab notation here to denote elementwise multiplication of two matrices). How can we find this optimal arrangement? Lets assume we are dealing with even $n$.

From my side I spent some time calculating the total # of possible arrangements for given $n$ and arrived at this formula:
$\frac{C^n_{n/2}}{2}(\frac{(n/2)!}{k})^2$
where $k = 1$ if $n = 2$ and $k = 2$ otherwise.

I wrote the following program to calculate the # of different arrangements for given value of $n$ (assume even $n$) according to above formula.

public static void main(String[] args) {
        for(int i = 2; i <= 10; i += 2)
        {
            System.out.printf("%d\t%s\n", i, foo(i).toString());
        }
    }

    static BigInteger foo(int n)
    {
        BigInteger t1 = binomial(n, n/2).divide(BigInteger.valueOf(2));
        BigInteger t2 = factorial(n / 2);
        BigInteger t3 = n >= 4 ? BigInteger.valueOf(4) : BigInteger.ONE;
        return t1.multiply(t2).multiply(t2).divide(t3);
    }

    // http://stackoverflow.com/a/2929897/147530
    static BigInteger binomial(final int N, final int K) {
        BigInteger ret = BigInteger.ONE;
        for (int k = 0; k < K; k++) {
            ret = ret.multiply(BigInteger.valueOf(N-k))
                    .divide(BigInteger.valueOf(k + 1));
        }
        return ret;
    }

    static BigInteger factorial(int n) {
        BigInteger ret = BigInteger.ONE;
        for (int k = 2; k <= n; k++) {
            ret = ret.multiply(BigInteger.valueOf(k));
        }
        return ret;
    }

Output:

2   1
4   3
6   90
8   5040
10  453600

Assuming that you are trying to maximize the seating preferences, this problem is NP-Hard =(.

NP-Hardness

Specifically, consider the decision version of this problem: Given a matrix of preferences, is there some way to assign people to seats such that the total score (sum of resulting preferences of professors to their nearby neighbors) obtained is at or above some $k$?

This problem is NP-Complete.

First, clearly this decision problem is in NP, as if one can provide you with such an assignment then you can compute the total score and verify that their solution works.

Next, note that this problem is essentially equivalent to finding two distinct highest-cost paths that go through the same amount of nodes, and together go through every node. Using this idea, we will solve the hamiltonian path problem.

Given two hamiltonian path instances $G_1=(V_1, E_1)$ $G_2=(V_2, E_2)$ of the same size $n$, consider the combined graph $G=(V_1\cup V_2, E_1 \cup E_2)$, and then create an instance of our seating arrangement problem where every edge is a $1$ if it occurs in our combined graph, and a $0$ otherwise. Because these graphs are undirected, the preferences will be the same in both directions.

The question "is there some way to assign seating positions to professors such that the total score obtained is greater than or equal to $\vert V_1 \vert + \vert V_2 \vert$" is NP-Complete, as it is only possible to do this if a hamiltonian path exists in both graphs.

Approximation algorithm ideas

NP-Hardness just guarantees that a problem can't always be solved exactly unless $P=NP$, however, it doesn't tell us anything about how difficult it is to approximate. Here is one idea I had, it's incomplete, but is at least something to get you started.

For simplicity, I will now consider the problem where there is a single circle of chairs, and we are trying to place professors in the same way you require. We will also restrict all preferences to be greater than or equal to 0. This can most likely be extended to your problem but I haven't got around to that yet, so I will update this problem once that is accomplished, or you can do this yourself.

With this "roundtable" problem, it turns out there is an algorithm I found that is guaranteed to find a solution that is no less than 8 times the optimal solution.

This algorithm does the following:

Place each person randomly around the table.
Consider a pair of people (any will do), and see if swapping them will increase the total score. If so, swap them.
Repeat until no swap will increase your total score.

This is guaranteed to halt in polynomial time because each swap strictly increases the total score (I think? Still a little fuzzy about this part but I'm fairly sure that is true and will formalize it in a bit).

How good does this algorithm do? Well, call $Opt$ the optimal ordering of professors, and $Val$ the ordering of professors that this algorithm gives when it is done.

Now, consider any set of edges $(a, x)$, $(x, b)$, $(c, y)$, $(y, d)$ in your graph, where $a, x, b, c, y, d$ are professors. We will denote these edges $(a,x,b)$ and $(c, y, d)$ since by definition given any arrangement of professors they are next to each other.

We know that, if $y$ and $x$ could be swapped our algorithm would have done so. Call $\mid (a, x, b)\mid$ the score of edge $(a, x)$ plus the score of edge $(x, b)$. Then, if $(a, y, b)$ and $(c, x, d)$ are in val, we know

$$|(a, y, b)| + |(c, x, d)| \geq |(a, x, b)| + |(c, y, d)|$$

Because either our algorithm swapped $x$ with $y$, or there was equal score regardless of the swap, in which case we have

$$|(a, y, b)| + |(c, x, d)| = |(a, x, b)| + |(c, y, d)|$$

Note that we technically also know

$$|(a, y, b)| + |(c, x, d)| \geq |(a, x, b)| + |(c, y, d)| \geq |(c, y)|$$

Which is true because $|(a, x, b)| + |(c, y, d)|$ contains $|(c, y)|$ in it. Now we can look at the terms on both ends, and this gives us

$$|(a, y, b)| + |(c, x, d)| \geq |(c, y)|$$

Which holds for all edges $(c, y)$. Note that given any $(c, y)$, there is only one such pair of $(a, y, b)$ and $(c, x, d)$, because the positions $c$ and $y$ are fixed.

We know that the value of $Opt$ is equal to the sum of all it's edges $(v_1, v_2)$, $(v_2, v_3)$, ..., $(v_{n-1}, v_n)$, $v_n, v_1)$ (where $v_i$ is some professor), so for each of these, we get a single inequality. Consider the edge $(a, y)$. $|(a, y)|$ will only appear in an inequality if $a$, $y$, or the professor before $a$ is contained in the edge in Opt. Thus, worst case $(a, y)$ is counted 8 times, because each variable can be in at most two edges, by definition.

If we sum all of the edges on both sides, we get

$$8*Val\geq Opt$$

Thus

$$(8 \geq \frac{Opt}{Val})$$

which is a factor 8 approximation, as desired.


How does $\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$ imply these two inclusions? In the proof of Theorem 1 in this paper by Chen, McKay, Murray, and Williams the authors assume $\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$ and (in different parts of the proof) state this implies the following two inclusions:

$\Sigma_3 \mathsf{TIME}(n^c) \subset \mathsf{SIZE}(n^{O(c)})$ for every $c$
$\mathsf{ZPP}^\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$

They also cite this enhancement of the Karp-Lipton theorem, in which the collapse of $\mathsf{PH}$ is to $\mathsf{ZPP}^\mathsf{NP}$.
I suspect the theorem is behind the inclusions in some way, but I just can't make the connection.

What am I missing?

If $\mathsf{NP} \subseteq \mathsf{P}/\mathsf{poly}$, then $\mathsf{SAT} \in \mathsf{SIZE}[O(n^k)]$ for some fixed constant $k$. The claimed results should follow by using this circuit to replace the $\mathsf{NP}$ oracle(s) involved in the relevant classes. For example, (2) follows by noting that $\mathsf{ZPP}^{\mathsf{NP}} = \mathsf{ZPP}^{\mathsf{SAT}}$ and then replacing every call to the $\mathsf{SAT}$ oracle with the assumed small circuit for $\mathsf{SAT}$.


Role of weak entities in avoiding inconsistencies My material on database claims that:

  Weak entities help to avoid data duplication and inconsistencies arising due to duplicating the key of the strong entity.

My question is how can a strong entity key even be duplicated? This would make the key lose its uniqueness property.

Can anyone please help? How is the statement provided in the material justified?

Thanks in advance!

Definition and example of weak entity

The diagram shows a strong entity (Order, key Order number) linked to multiple weak entities (Order Line, key Order number+Order linenumnber). There's a foreign key from the weak entity to the strong (Order number).

So the Order number is duplicated in the sense a given Order number appears in many entities: one strong (Order number is the whole key); many weak (Order number is part of the key).


Finding paths with smallest maximum edge weight I need to find the easiest cost path between two vertices of a graph. Easiest here means the path with the smallest maximum-weigth edge.

In the above graph, the easiest path from 1 to 2 is:

1 > 3 > 4 > 2

Because the maximum edge weight is only 2. On the other hand, the shortest path 1 -> 2 has maximum weight 4.

So it's an MST problem. I am thinking I will use Kruskal's algorithm to build the tree, but I'm not sure how exactly. I will know the edges but how do I "reconstruct" the path? For example, given vertices 3 and 2, how do I know to go left (top) of right in the tree? Or do I try both ways?

You're right; it's essentially a MST problem. First build the minimum spanning tree, then use breadth-first or depth-first search to find the unique path in the tree between the two vertices.


Integer solution that approximates a desired stock split I am building software for an investment manager. The investment manager invests money on behalf of his clients.

The investment manager has a model portfolio, of say 20 stocks, each with certain weightage.

Eg: His model portfolio can look like this:

{GOOG: .03, AAPL: 0.4, MSFT: 0.25, TESLA: 0.5, IBM: 0.1, .....}
Now lets say the investment manager has one client, who holds all of the stocks, the total of which is worth, say USD50,000, but with slightly different weightage:

{GOOG: .0295, AAPL: 0.415, MSFT: 0.232, TESLA: 0.1, IBM: 0.2, .....}
Now the client wants to invest a lumpsum, lets say USD10,000.

Now, the investment manager wants to split this USD10,000 across 20 stocks, so that he gets closest to the model portfolio. i.e. I want the resultant USD60,000 to be split in a way that is closest to the ratios maintained in the model portfolio.

A limitation here is that, I can buy or sell a minimum of 1 stock; I cannot deal in fractions of stocks.

Is there a name for this kind of problem? I am pretty sure this has been solved by someone, so do not want to reinvent the wheel.

I do not know what I should google for, or where to start from.

I want the chosen allocation to have the least deviation from the model portfolio, measured by $L_2$ distance (sum of squared differences). Also, the investor keeps investing periodically, so there is a chance his portfolio might deviate further and further, so the idea is to keep these "tracking errors" to a minimum, so that it the investor's portfolio is as close to the model portfolio as possible.

Let $d_i$ be the desired dollar amount that you'd ideally like to have invested in the $i$th stock (i.e., $d_1,\dots,d_n$ represent the ideal/model portfolio, without taking the requirement to avoid fractional shares).  Let $p_i$ denote the price of a single share of the $i$th stock.

Then you want to find a solution to the following optimization problem

$$\begin{align*}
\text{minimize } &(p_1 x_1 - d_1)^2 + \dots + (p_{20} x_{20} - d_{20})^2\\
\text{subject to } &p_1 x_1 + \dots + p_{20} x_{20} = 10,000\\
                   &x_1 \ge 0, \dots, x_{20} \ge 0
\end{align*}$$

where you require that the variables $x_1,\dots,x_{20}$ be integers.  Here the $p_i$'s and $d_i$'s are given (they are known constants), and you've solving for the $x_i$'s.

This is an instance of quadratic integer programming: i.e., integer programming with linear constraints and a quadratic objective function.  That in turn is a special case of mixed-integer quadratic programming (MIQP).  In general MIQP allows the problem to contain some integer variables and some continuous variables; your particular instance has only integer variables, so it's a special case of MIQP.  You can find off-the-shelf MIQP solvers out there.  I would recommend that you try applying one to your problem.  Given the problem size you describe, I would expect them to be effective and efficient at your problem.

If you wanted to measure the deviation from the ideal model by the $L_1$ distance (sum of absolute values of differences) instead of the $L_2$ distance (sum of squared differences), that could be expressed as an instance of integer linear programming (ILP), for which solvers are even more effective.


Minimizing catastrophic risk in Gale-Shapley matching In the hospital-resident assignment problem we have to match a large set of med students with a small set of hospitals. Hospitals may accept multiple students, but the number of students is much larger than the total number of residency slots available - several students are left unmatched.

If a particular student's primary concern is simply matching somewhere,  is there any strategy they can adopt that outperforms ranking hospitals according to their true preference?

(In theory) No, no other strategy will help. In the student-proposing version of the deferred acceptance algorithm, it is a theorem[0] that each student's optimal action is to report her true preference order. It's a dominant strategy, meaning this is optimal regardless of what others submit. This implies that if the student is unmatched when submitting her true preferences, then there is no other submission she could make that would have gotten her matched[1].

Note deferred acceptance still works for weak preference orderings (see [0]), so e.g. here the student is indifferent between all hospitals and prefers them all to being unmatched. The dominant-strategy guarantee of deferred acceptance still holds.

(In practice) In practice, students don't interview or rank all possible hospitals. So a student could likely improve her chances by trying to interview and rank mostly lower-prestige programs where the competition is lower.

[0] e.g. Theorem 8 of the survey by Al Roth, Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions. https://web.stanford.edu/~alroth/papers/GaleandShapley.revised.IJGT.pdf

[1] I am assuming she prefers any match to being unmatched.


Is There Any Shortest Path Algorithm That Finds The Shortest Path Between Only Two Nodes The Dikstra shortest path algorithm on a weighted graph, directional or bidirectional, pretty quick. There is also the Bellman Ford algorithm. However, these two find the shortest path between one source to all vertices. However, if I only want to know the path between two vertices, is there a faster algorithm that only finds the distance between two nodes?

Nope.  The best you can do is to use Dijkstra's or Bellman-Ford.  With Dijkstra's algorithm, you can stop the iteration as soon as you reach the target node, but this doesn't improve the worst-case asymptotic running time.


Context-free grammar for $\{ a^n b^m a^{n+m} \}$ I've got a problem with this task. I should declare a context-free grammar for this language:

$\qquad \displaystyle L := \{\, a^nb^ma^{n+m} : n,m \in \mathbb{N}\,\}$

My idea is: We need a start symbol, for example $S$. I know that I can generate the first $a$ and the last $a$ by $S \to a a$. I don't know what is the next idea to solve this task.

First, rewrite $a^nb^ma^{n+m}$ as $a^nb^ma^ma^n$. Now, from the outside in, you need rules to (1) add an $a$ to the front and back of your strings, and (2) to add $b$ to the front and $a$ to the back. It's also helpful to imagine building strings from the inside out... you can either add a $b$ to the front and an $a$ to the back, or an $a$ to both ends.

The first, working from the outside, rule is straightforward:

S := aSa

Notice that once you start adding $b$, you cannot go back to adding only $a$... so we need a new nonterminal:

S := B
B := bBa

Since the empty string is in your language, add another production to allow $B$ to generate the empty string. So we get:

S := aSa | B
B := bBa | -


Show that the collection of Turing-recognizable languages is closed under homomorphism I have seen this question here,
Closure of Turing-recognizable languages under homomorphism
But actually this question answers the question of "What is the relation between homomorphism and concatenation?", so I still have a problem of how to show that the collection of Turing-recognizable languages is closed under homomorphism. Could anyone help me in doing so please?

In my opinion closure under homomorphism is very similar to closure under Kleene Star, but I am convinced that I have to put marks on any number of tape cells because my language $f(L)$ may contain many strings, am I right?

Many thanks!

The proof is posted by Anwar Saiah on this post. I quote it here (with its formatting improved).

Given a language $L$ that is Turing recognizable and a TM $M$ that recognizes it and a homomorphism $f$, we build a NTM $M'$ that recognizes $f(L)$.
$M'$ looks like this:
On input $w$ :

Non-deterministicly feed words from $\Sigma^∗$ to $f$ until you obtain $w$.

Run $M$ on $f^{−1}(w)$, if $M$ accepts accept, otherwise reject.

This works because $M'$ is a non-deterministic Turing machine.  A NTM accepts $w$ if there is at least one branch accepting $w$, so if there is any word $x$ such that $f(x)=w$ and $M(x)$ accepts, this will find it and accept.


How to extend Bellman-Ford to solve the $k$ shortest path routing? Browsing the wikipedia I got to this page where it is said:

  Finding k shortest paths is possible by extending Dijkstra algorithm or Bellman-Ford algorithm and extend them to find more than one path.

The same statement is somewhat repeated in the hall of fame of algorithms:

  To find the shortest path one can use shortest path algorithms such as Dijkstra’s algorithm or Bellman Ford algorithm and extend them to find more than one path

Then, the Wikipedia (i.e., the first link, not the second) goes into proving how it is possible to extend Dijkstra's algorithm to solve the loopy variant (i.e., where non-simple paths are allowed). The extension is absolutely simple as it simply consists of allowing each node to be expanded up to $k$ times, with $k$ the number of paths to find to the goal state. This idea, indeed, was generalized by Rina Dechter to consider heuristics as well:

Rina Decther, Natalia Flerova and Radu Marinescu. Search algorithms for $m$ best solutions for Graphical Models. AAAI 20, pp. 1895--1901
Natalia Flerova, Radu Marinescu and Rina Dechter. Search algorithms for the $m$ best solutions in Graphical Models. Journal of Artificial Intelligence Research (55) 2016, pp. 889--952.

However, I never heard of any extension of Bellman-Ford for solving neither the loopy nor the loopless variants of the $k$ shortest path routing problem. Moreover, I'm not aware of any algorithm that can solve this problem in the presence of negative edge costs.

The only variant I can think of for extending Bellman-Ford is observing that upon termination the cost of the optimal path of one designated vertex to all the other vertices $v\in V$, $d_v$, is known so that one could run sort of a Recursive Best-First Search to enumerate all paths. Maybe is this what the authors of those pages mean?

Thus, my questions are:

What is the way to extend Bellman-Ford to solve the $k$ shortest path routing problem?
Are there any algorithms out there for solving the $k$ shortest path routing problem with negative edge costs (provided there are no negative cycles)? Note that neither Eppstein's nor Yen's algorithm can deal with negative edge costs.

This is all I know about the subject and please note that my questions are a result of my ignorance so that I would be very grateful if any answer is provided or any link I could follow.

Cheers,

It seems that we can use the following generalization of Bellman-Ford. Let's store a set $Pt_{v}$ of $k$ numbers for each vertex $v$ of graph $G$ which initially are all equal to $+\infty$. The only exception is a vertex $s$ (the vertex from which all paths are calculated). Its set $Pt_{s}$ should be initialized to a single value of $0$ and $k-1$ values of $+\infty$.

Now let's run $k \cdot |V|$ iterations of relaxations (instead of $|V| - 1$ iterations like in usual Bellman-Ford) and try to maintain the following invariant. After $i$-s iteration for each vertex $v$ the $j$-s least number from $Pt_{v}$ should be not greater than the length of the $j$-s shortest path from $s$ to $v$ containing not more than $i$ edges. This invariant will be maintained by means of proper edge relaxations. For each $(u, v)$ edge relaxation we should assign $Pt_{v}$ to a set of $k$ least numbers from a set $Pt_{v} \cup \{x + weight(u, v)|x\in Pt_{u}\}$.

So after all $|V|-1$ iterations each set $Pt_{v}$ will contain $k$ shortest paths from $s$ to $v$. The proof of correctness for this algorithm should be literally the same as for usual Bellman-Ford.

This is a loopy algorithm. Its time complexity is $O(|V|\cdot|E|\cdot k^2)$ (because single edge relaxation can be done in $O(k)$ time using a selection algorithm).


Matrix Sum, factorial(K) times Given an N x M matrix. The task is to repeat the following steps K! times.

Add all the elements of the matrix and get a matrix sum (S) % mod 10^9 + 7
Add S to all the elements. % mod 10^9 + 7
Repeat.

What I can think of regarding the complexity it will O(K! x N x M).

But K ranges from 1 to 10^5 and this is a huge number of iterations for a computer to process.

Is there a way to optimize these operations so that these can be performed using less computational resources.

Thank You.

Suppose that the original elements are $a_{ij}^{(1)}$. Their sum is $S^{(1)} = \sum_{ij} a_{ij}^{(1)}$, and the new elements are $a_{ij}^{(2)} = a_{ij}^{(1)} + S^{(1)}$. The new sum is $S^{(2)} = \sum_{ij} a_{ij}^{(1)} + nmS^{(1)} = (1+nm)S^{(1)}$, and the new elements are $a_{ij}^{(3)} = a_{ij}^{(1)} + (2+nm)S^{(1)}$. The new sum is $S^{(3)} = S^{(1)} + nm(2+nm)S^{(1)} = (1+nm)^2S^{(1)}$, and so on.

More generally, you can prove by induction that $S^{(t)} = (1+nm)^{t-1} S^{(1)}$ and $a_{ij}^{(t)} = a_{ij}^{(1)} + \frac{(1+nm)^{t-1}-1}{nm} S^{(1)}$. It remains to find a fast way to calculate expressions such as $S^{(k!)} = (1+nm)^{k!-1} S^{(1)}$ modulo the given prime $p = 10^9 + 7$. You do the rest.


Mutex implementation on top of a minimalistic preemptive scheduler In this question, I'm implementing some synchronization primitives in the standard library of an operating system. Specifically, I want to implement mutexes and condition variables. This is on top of a microkernel with a preemptive scheduler (a thread has no way to prevent the scheduler from preempting it). I'm exploring how minimalistic the system can get while remaining powerful and efficient enough for my needs.

From the hardware, I get a basic atomic primitive such as compare-and-swap or load-link/store-conditional. You can assume that the word size for these instructions is large enough to store a pointer or a thread identifier. Furthermore all threads see the same memory.

From the kernel, I get three primitives:

sleep(): suspend the current thread until a thread has called wake(t) where t is the current thread. If the current thread's wake-up flag is already set then sleep() returns immediately. Returning from sleep clears the wake-up flag.
wake(t): wake thread t if it's asleep. If t isn't asleep then its wake-up flag is set and t's next call to sleep will return immediately. Note that non-participating threads may call wake — as far as the locking mechanism is concerned, it's thus possible for a thread's wake flag to become set non-deterministically.
yield(): give all other threads that are not asleep a chance to run.

How can I implement a mutex and condition variable API on top of these primitives?

lock(m): if m is taken, sleep until it is free. Mark m as taken.
unlock(m): mark m as free. If some other thread is waiting for it to become free, that thread is woken up.
wait(c, m): wait for the event c to happen. If c has already happened, don't block. When wait returns, it atomically locks the mutex m. When a thread notices c, the event is cleared.
signal(c): signal an event on the condition c. This wakes up one thread that's waiting on c.

A good solution must avoid starvation: if a thread tries to lock a mutex, it must eventually get it provided that every thread that acquires it releases it eventually. Preferably, threads should obtain the lock on a first-come, first-served basis. (To give a counter-example, a last-come, first-served system would be bad because one thread could hog the mutex if it keeps acquiring it immediately after releasing it.)

A solution is better if it avoids scheduling a thread that ends up doing no useful work. For example, systematically waking up all threads when something happens is not good enough.

What is an efficient algorithm for implementing mutexes and synchronization variables? (Note that I am not asking how to implement a spinlock! A spinlock is probably involved, but I expect answers to this question to explain how to set up wait queues and not just handwave that part.) Efficiency may vary based on the amount of contention; the kind of systems I work on tend to have low contention in practice (but must not overly drain the battery when there is contention).

(I expect answers to explain the algorithm in sufficient detail that a programmer could understand it, but a reference would be appreciated as well.)

Mutex

For the mutex I'm going to propose a modification of the MCS spinlock that uses your sleep/wake primitives to block instead of spin while waiting to acquire the mutex.  The MCS lock was introduced in

  Mellor-Crummey, John M; Scott, Michael L: Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors, ACM Trans. on Comp. Sys. (TOCS), 9(1):21-65, 1991.

The MCS lock was specifically designed to eliminate the undesirable coherence traffic associated with spin locks in large-scale cache-coherent shared memory multiprocessors (which is not your concern) but I'm suggesting it because of the analogy between inter-processor coherence messaging in multiprocessors and your sleep and wake primitives.

Essentially we are keeping a linked-list of waiters for the lock.  The lock itself is a pointer to the tail of the list.  The head of the list is the thread that currently has the lock.  The tricky part is that there are two pointers to the tail so you need to be careful about the lack of atomicity when adding or removing the tail node.

I'm going to use the same pseudo-code notation used in the paper, which is Pascal-based (it was 1991, give them a break), so the pointer notation may be unfamiliar to many readers.  I: ^qnode means, "the variable I has the type 'pointer to qnode'," and I^ means, "that which I points to."

compare_and_swap(addr, old, new) is defined as (atomically) if addr^ != old return false; addr^ := new; return true.  atomic_swap(addr, new) is defined as (atomically) old := addr^; addr^ := new; return old.

type QNode = record
  owner    : Boolean
  threadId : ThreadIdentifier
  next     : ^QNode

type lock = ^QNode    // locks start initialized to "nil" (the null pointer)

// The qnode I needs to be allocated in an outer scope

procedure acquire_lock (L : ^lock, I : ^qnode)
  I->threadId := myThreadId
  I->next     := nil
  predecessor : ^qnode := atomic_swap(L, I)
  if predecessor != nil                    // queue was non-empty
     I->owner := false
     predecessor->next := I                // put myself on the tail
     repeat sleep() while not I->owner

procedure release_lock (L : ^lock, I : ^qnode)
  if I->next == nil                        // no known successor
     if compare_and_swap(L, I, nil) return true  // L agrees that there's no successor
     else repeat (spin) while I->next == nil     // else spin wait for race to clear itself
  I->next->owner := true                   // there is a successor, wake it
  wake(I->next->threadId)

The only spinning is (1) in the (hopefully extremely rare) condition that the queue is empty except for the lock holder, and the lock holder tries to release at exactly the same time some other thread is trying to add itself to the queue or (2) when a thread waiting to acquire the lock receives a spurious wake up.

Condition Variable

Given a working mutex implementation with lock(m) and unlock(m), it is possible to do a relatively naïve but working implementation of a condition variable.  This design is based on

  Birrell, Andrew D; Impliementing Condition Variables with Semaphores, in Computer Systems, Theory, Technology, and Applications, Andrew Herbert and Karen Spärck Jones, editors, pp. 29-37, Springer Monographs in Computer Science, 2004.

and in particular, Birrell's advice that the condition variable should do the queueing itself, rather than relying on some other primitive.  Birrell's version additionally makes use of the observation that each thread can be waiting for at most one condition variable, so each qnode can be allocated as part of the thread control block when the thread is created.  (Which seems a bad idea to me, because then you have a dangling pointer when a thread gets killed while waiting for a condition variable.)

Start with a non-atomic queue of integers data type with push_tail(q, t) and pop_head(q)  and is_empty(q).

type CVar = record
  q : Queue
  qm : Mutex   // private mutex to protect the queue

// precondition: caller holds mutex m
procedure wait(cv : ^CVar, m : ^Mutex)
  lock(cv->qm)
  push_tail(cv->q, myThreadId)   // atomically add caller to the queue
  unlock(cv->qm)
  unlock(m)
  sleep()
  lock(m)

procedure signal(cv : ^CVar)
  lock(cv->qm)
  if not is_empty(cv->q)
    wake(pop_head(cv->q))
  unlock(cv->qm)

This implementation does suffer from spurious wakeups, but that's standard for condition variable implementations.  It is assumed that you are using condition variables to wait for some precondition (described by predicate P()) to become true and that you are thus using the condition variable like this:

m  : Mutex
cv : CVar

lock(m)
while not P()
  wait(cv, m)
// at this point P() is true and m is acquired


When was the terminology *tracing collector* introduced to denote both mark-and-sweep and copy collectors Automatic storage reclamation, aka garbage collection, comes in two
main families, sometimes cooperating: the reference count collectors
and the tracing collectors. I may develop specifics of each family if
there is demand for it but my question is about tracing collectors.

Tracing collectors, in their simpler form can be divided into
mark-and-sweep (possibly with compaction) and copy collectors (that
compact naturally). Historically, they seem to have been
considered distinct families in the first 10 or 20 years of the
development of garbage collection technology.

I am wondering when they started to become known as tracing collectors
forming a single family. When was the expression tracing collectors
first used to denote both mark-and-sweep and copy collection, and
possibly collectors mixing both technologies (as is often the case with
generational collectors).

Ideally, a reference to a paper introducing the terminology would be
the best form for an answer. Reference to a book is good too, if you can give the printing where it first appears, as books often evolve with successive printings. Specifying the page or giving a quote would be nice too.

Added after accepting the answer.

I am accepting the answer given by Pseudonym, as it is a very clear
answer, that seems to be as good as it will ever get (but who
knows?). What I mean is that it seems unlikely that an earlier date
will be found, sinve the Paul Wilson's 1992 survey is pretty
thorough. As I recall, the previous survey by Cohen in 1981 does not
allude to tracing or unification of copy and mark-and-sweep.

An interesting trivia is that the introduction of this concept is
exactly half-way between the first garbage collection paper in 1960 (as
far as I know) and now (early 2015), which give a kind of time measure
of conceptual evolution.

This first GC papers, to my knowledge, used reference counting and
were published in 1960. According to wikipedia, which cites  Jones,
Richard; Lins, Rafael (1996), Garbage collection: algorithms for
automatic dynamic memory management, Wiley, p. 40, ISBN
9780471941484:

  The first, though cumbersome and error-prone, reference counting technique was described by J. Gelertner, J.R. Hansen, and C.L. Gerberich [Gelernter et al, 1960] but the standard reference counting algorithm is due to George Collins [Collins, 1960].

To my knowledge, the first tracing GC is a mark-and-sweep
implementation for LISP published in 1964 in, Notes on implementing
LISP for the M-460 Computer, Timothy P. Hart and Thomas G. Evans,
pp. 191-203 in The Programming Language LISP, its Operation and
Applications, March 1964, published by Information International, and
reprinted by MIT press (though they seemed to have lost all memory of
it when I asked, a long time ago). It does use the name "garbage collector", but I do not
know whether that is the first occurrence in the computer literature.

The terminology was introduced in Lang and Dupont, Incremental Incrementally Compacting Garbage Collection, SIGPLAN 87. This is the paper which consolidated several lines of enquiry into one common language.

The way I found this out was by consulting Paul Wilson's 1992 survey, Uniprocessor Garbage Collection Techniques, which is required reading if you need to know stuff like this.


how does a harddisk work? block / sector Can someone explain me the way harddisks work? :/
The size of a block is specified in the filesystem, am I right? As you can see in the picture from wikipedia, the disk is divided into circle sectors. But the blocks on the outer tracks are obviously larger (physically)...

So the "bit-density" on the outer blocks is way smaller than on the blocks near the middle of the disk? I think that I am missing something.... Maybe someone can help me out with another picture / sketch.
Thanks a lot and sorry for the "nooby" question :)

This is something that has changed over the decades.

In the past, the blocks were laid out exactly as you see in the picture.  The bit density of the outer blocks was less than those of the inner blocks.  This made the hardware easy to build at the expense of being less efficient.

In modern times, we no longer need to make the hardware easy.  We're interested in maximum efficiency of the harddrive.  Modern harddrives do not have nice easy angular wedges like the old ones do. They, instead, try to keep the bit density as even as possible (maximized at all places).


Could I simulate the implementation of memory components I am currently reading the IEEE paper A Memory-Efficient Parallel String Matching
Architecture for High-Speed Intrusion Detection by Kai Zheng,  Bin Liu,  Xin Zhang, and  Yunhao Liu.

In the paper they propose a model for
 a memory-efficient multiple-character-approaching architecture
consisting of multiple parallel DFAs.

I have read the paper and I have understood to an extent.

But when I think of implementation, could I simulate the SRAM, LE,BCAM etc.. as in the case of a network simulator (NS-2,OPNET,OMNET).

You can simulate the architecture using a hardware-description language.

Try VHDL (http://esd.cs.ucr.edu/labs/tutorial/) or Verilog ( http://www.asic-world.com/verilog/veritut.html) two of the most popular hardware description languages.


Sorted-greedy for Load Balancing Problem In load balancing problem we have $m$ machines and $n$ jobs, each taking processing time $t_j$. Total processing time on the machine $i$ is $T_i =\sum_{j\in A(i)}{t_j}$, where $A(i)$ is the set of jobs assigned to machine $i$. Goal is to provide an assignment of jobs, such that $\max T_i$ is minimized.

It is known that sorted greedy algorithm is only approximation solution for load balancing problem. But I can't find an instance of problem, when it actually doesn't find an optimum solution. Can someone provide an example when this algorithm gives a wrong answer?

Take for instance $m=2$ machines and $n=5$ jobs with processing times $4,3,3,2,2$.

The optimal schedule puts $4+3$ on one machine and $3+2+2$ on the orther machine.
Sorted-greedy assigns $4$ to the first machine, $3$ to the second machine, $3$ to the second machine, $2$ to the first machine, $2$ to the first machine. Hence the loads are $4+2+2$ and $3+3$.


Quality LISP/Scheme compilers to compete with C/C++ Theoretically speaking, is it possible to have a Lisp/Scheme compiler that can produce code that can compete with compiled C, let's say within 15-25% margin?

In my testing, I've found that the current crop of compilers (Bigloo, SBCL, Gambit, Chicken, etc) are 20-50 times slower than equivalent C code.

The only outlier is the Stalin compiler. For simple programs, it produces binaries that are equivalent to C. However, what I find suspicious is that none of the other projects (Bigloo, Chicken, Clozure, etc) have attempted to implement whatever tricks Stalin uses ("whole program optimization", etc).

I'm a huge fan of LISP since the mid 90s and would love to bring it on board so my team can crank out projects in half the time in normally takes using C/C++/.NET/etc, but...the performance issues are a huge roadblock.

I wonder if the lack of quality LISP compilers are due to the fact that no serious time and money has been invested into the subject OR if this simply isn't a feasible task given the current state of compiler technology??

As noted in the comments, it isn't very exact to state "the current crop of compilers (Bigloo, SBCL, Gambit, Chicken, etc) are 20-50 times slower than equivalent C code", without qualifying how you tested and what you tested.

For my use, I find that for many things Gambit and Chicken Scheme are quite close to the equivalent 'C' code in speed, with the current version of Gambit (4.7.3) generally faster than Chicken (4.9.0.1) but over pre-optimizing the output 'C' code (making assumptions about the number of available registers - assumes x686 - and forcing the use of stack memory for any extra memory requirements, which decisions should be left to the 'C' compiler as Chicken does, which often eliminates the requirement for extra registers and combines processing steps) so as to prevent the 'C' compiler from doing its own optimizations resulting in very tight small loops being up to about twice as slow as those same tight small loops in 'C' (or Chicken); Chicken just defines as many variables local to a given function as it sees fit (mostly used immutably) and then depends on the compiler to optimize most of those away.  Chicken doesn't seem to optimize Continuation Passing Style (CPS) algorithms with multiple forked levels of continuations as well as Gambit and can be up to about eight times slower than Gambit for these, but then one thinks that CPS isn't really formalized for 'C' code at all so...

EDIT_ADD:  I have done some more research into the Chicken and Gambit-C Scheme versions and have found the following:

Chicken is faster than Gambit for small tight loops for the above reason (depends more on the 'C' compiler for optimizations without doing as much itself and thus takes better advantage of x86-64 extra registers), but also because it doesn't include a "POLL" stack maintenance check inside the loops, whereas Gambit includes the "POLL" check inside the loop.  Even when this isn't triggered (the usual case), it will take several CPU clock cycles to determine that nothing is required (about 6 cycles).  A future smarter compiler might see that there is no need to do a stack check when inside a tight loop and not doing stack-building operations, doing it just before or after the loop and save this time.
Gambit's 'C' macro's do too much work, as said, in precisely defining how the operations should be carried out, especially including fixed stack size operations, and these are likely harder for the 'C' compiler to optimize; using registers more effectively could reduce tight loop time by perhaps 4 cycles, which in combination with the above would put it into the Chicken ballpark.
Neither output "read/modify/write" optimizations for say vector operations that are modify in place and don't output code so that the compiler does it.  A smarter backend such as LLVM when used with Haskell does this kind of thing.  This would reduce register use by one and execution time in using only a single instruction rather than a separate read, computation of the modification, and a write to the same location; this would become just a calculation of the modification (say a bit or), and then a read modify (|=) write single instruction.  This might make the speed faster by a cycle or so
Both are dynamically typed and process data "tag" bits as part of their data.  Neither are smart enough for tight loops to reduce the tags, perform the loop "tag-less", then add the tags back for any results from the loop, nor do they produce code where the 'C' compiler can see to do this although it does combine these operations for some cases.  Optimization here could reduce loop times by a couple of CPU cycles or so, depending on the loop.
Very tight 'C' loops can take about 3.5 CPU clock cycles per loop on a fast CPU that isn't memory cache access speed throttled (such as AMD Bulldozer, which is about twice as slow); the same loop in Chicken currently takes about 6 cycles and Gambit takes about 16.9 cycles.  With all of the optimizations as per the above, there is no reason that these implementations of Scheme couldn't do that, however some work is required:
In the case of Gambit, the harder work might be improving the flow analysis to recognize when no "POLL" tests need to be inserted (ie. could this be interrupt driven, although the compiler does allow interrupts to be turned off for some uses?); the easier improvement would be to just implement better register usage (ie. recognize x86-64 registers better rather than the default x686 architecture).  For both, better flow analysis to recognize that they can "untag" the data, especially "fixnum", "flonum", and vector, data so these operations aren't necessary inside tight loops and combining read/modify/write instructions. Both of these ends could be accomplished by using a better backend such as LLVM (not a trivial amount of work, but both are already partly there).

Conclusion: Chicken is currently about 50% slower than 'C' on the fastest CPU's (not my Bulldozer, where it is about the same speed due to cache throttling of the 'C' code) and Gambit is about 400% slower (only about 125% slower on my slow Bulldozer).  However, future improvements to the compilers could reduce this so that either code is no slower than 'C' or within the margin that the OP specifies.

A more complex language such as Haskell, when using the LLVM backend, paying careful attention to strictness use (not a problem with scheme which is always eager by default), and using appropriate data structures (ST unboxed arrays rather than lists for tight loops; somewhat applicable to Scheme using vectors), runs at about the same speed as 'C' if the LLVM backend is used with full optimizations.  If it can do this, so can Scheme with the above compiler improvements.

AGAIN, there is no way that either of these is 20 to 50 times as slow when used with proper optimization flags.  END_EDIT_ADD

Of course, all benchmarks are invalidated if one does not use the appropriate optimization settings for each as one would in a production environment...

I would think that the commercial Chez Scheme compiler would be in the ballpark as to producing high performance output as do Gambit and Chicken, as being commercial it surely has some "serious time and money invested into it".

The only way I can get Gambit or Chicken to run as slow as "20 to 50 times slower than 'C'" is to not use any optimization settings, in which case they often don't run much faster than as interpreted in their REPL's - 10's of times slower than as properly using those settings.

Is it possible that the OP hasn't tested using these settings properly?

If the OP cares to clarify his testing procedures, I will gladly edit this answer to show that at least Gambit and Chicken don't have to be that slow.


Greedy algorithm correctness proof for "Elegant Permuted Sum" (UVa 11158) Given a sequence of $2 \leq n \leq 50$ numbers $s = (s_1,s_2,...,s_n)$, find a permutation $a = (a_1,a_2,...,a_n)$ of $s$ such that $$\sum_{i=1}^{n-1} |a_i - a_{i+1}|$$ is maximized.

I found many codes that get "Accepted" in the online judge with the following greedy algorithm.

  If $n = 2$, then $a = s$. Stop the algorithm.

  Let $s' = (s'_1,s'_2,...,s'_n)$ be $s$ in the non decreasing order.
  Start the optimal sequence with $a = (s'_1,s'_n)$ and remove these two
  elements from $s'$.

  $\text{loop}$: Let $s' = (s'_1,s'_2,...,s'_k)$ be the remaining sorted
  sequence. If $k = 0$, stop the algorithm. If $k > 0$, from the
  following choices, choose the one that yields the greatest absolute
  difference.

  Remove $s'_1$ from $s'$ and push it to the front of $a$.
  Remove $s'_1$ from $s'$ and push it to the back of $a$.
  Remove $s'_k$ from $s'$ and push it to the front of $a$.
  Remove $s'_k$ from $s'$ and push it to the back of $a$.

  Go to $\text{loop}$.

I'm having trouble to formally prove the correctness of this algorithm.

For example, to prove the optimal substructure property. Let $b = (b_1,b_2,...,b_n)$ be an optimal solution. How can I argue that $(b_1,b_2,...,b_{n-1})$ is also optimal? What if it's not???

And for proving the greedy-choice property. Let $a = (a_1,a_2,...,a_m)$ be a partial, yet still optimal, solution. The algorithm relies on the fact that only adding $s'_1$ or $s'_k$ to $a$ can yield another optimal solution. Why is this true? And more, why we don't need to test inner positions for inserting the new element, but only the ends?

Any help with these proofs? Or, perhaps, this algorithm is not correct? But I can't find a counterexample...

This algorithm appears and is analyzed in Curtis, Darts and hoopla board design. Curtis actually considers two problems:

Dartboard design: Given a sequence of numbers, find a circular arrangement $a_1,\ldots,a_n$ maximizing $\sum_{i=1}^n |a_i-a_{i+1}|^q$ for some $q \geq 1$ (where $a_{n+1} = a_1$).
Hoopla board design: Given a sequence of numbers, find a permutation $a_1,\ldots,a_n$ maximizing $\sum_{i=1}^{n-1} |a_i-a_{i+1}|^q$ for some $q \geq 1$.

Your problem is the hoopla board design with $q = 1$. You can find a complete proof of the greedy algorithm in Curtis' paper. It's not trivial, though also not too complicated.


Find Divisible Sum Pairs in an array in O(n) time You are given an array of n integers a0, a1, .. an and a positive integer k. Find and print the number of pairs (i,j) where i<j and i+j is evenly divisible by k (Which is i+j % k == 0). This problem has been taken from Hackerrank.

We need a solution in O(n) time.

An explanation is that we can do this by separating elements into buckets depending on their mod k. For example, you have the elements: 1 3 2 6 4 5 9 and k = 3

mod 3 == 0 : 3 6 9
mod 3 == 1 : 1 4
mod 3 == 2 : 2 5

Now, you can make pairs like so:

  Elements with mod 3 == 0 will match with elements with (3 - 0) mod k =
  0, so other elements in the mod 3 == 0 list, like so: (3, 6) (3, 9)
  (6, 9)

Further:

  There will be n * (n - 1) / 2 such pairs, where n is length of the
  list, because the list is the same and i != j. Elements with mod 3 ==
  1 will match with elements with (3 - 1) mod k = 2, so elements in the
  mod 3 == 2 list, like so: (1, 2) (1, 5) (4, 2) (4, 5)

It makes sense that (3, 6) (3, 9) (6, 9) ( all items in the 0th bucket be paired) since (a + b)% k = 0 = a % k + b % k.

What isnt clear is how the other pairs (1, 2) (1, 5) (4, 2) (4, 5) were generated by combination of elements in the 1st (mod 3 == 1) and the 2nd (mod 3 == 2) bucket and why would there be n * (n - 1) / 2 pairs.

Consider in your example the set $S_1=\{1, 4\}$ and the set $S_2=\{2,5\}$. Let $n_1 = 2$ and $n_2=2$, the sizes of sets $S_1$ and $S_2$. All of the elements $x\in S_1$ satisfy $x\equiv 1\pmod 3$ and so are of the form $x=3s+1$ for some $s$. Similarly all $y\in S_2$ are of the form $y=3t+2$ so $x+y=3s+1+3t+2=3(s+t+1)$, which is divisible by 3. The number of such pairs is $n_1\cdot n_2$: pick one element, $x$, from $S_1$ and one element, $y$, from $S_2$ to form the pair $(x, y)$, rearranging, if necessary so that the first element is less than the second. In sum, there will be $n_1\cdot n_2=2\cdot 2$ pairs: $(1, 2), (1, 5), (4, 2), (4, 5)$, which, after arranging the pairs in component orders, gives $(1, 2), (1, 5), (2, 4), (2, 5)$ (your highlighted quote didn't do that).

For a general $k$, then, you'll have sets $S_i$, for $i=1, \cdots k-1$ (ignoring $S_0$ for the moment), so if $n_i$ represents the size of $S_i$, you'll have pairs $(x,y)$ where $x\in S_i$ and $y\in S_{k-i}$. The number of such pairs is $n_1\cdot n_{k-1}+n_2\cdot n_{k-2}+\dotsc$.

[You have to be a bit careful, since, first, the sum only should include those products $n_i\cdot n_{k-i}$ for which $i<k-i$, and second, you'll have to account for the cases where $i$ and $k-i$ are equal. You'll also have to deal with the pairs you get from $S_0$, which have to be counted differently.]

I'd suggest ignoring the sentence where $n(n-1)/2$ appears: it's true but irrelevant.


Turing machine to compute $⌈\log_2n⌉$ with 1 tape and unary input/output I'm trying to figure out how to make the action table for a Turing Machine computing $⌈\log_{2}(n)⌉$. The input and output shall be unary (meaning $3$ should represent $111$). I can only deal with 1 tape.
Also, I would prefer having 7 transition states, 1 final state, 24 actions and 5 symbols, but any other numbers are fine too. At the end of the computation, the TM head should be at the 1st $1$ from the left, of the output.
For $⌈\log_{2}(0)⌉$, I would like to have the symbol $N$ on the tape.
I would also like an easy-to-understand explanation, if possible.

One simple approach is repeated halving.
Remove a single 1 from the input (if you fail, output N).
Then go over the tape in passes. Each pass deletes every other 1 encountered (starting with the first). The number of passes required to delete all 1s is $\lceil \log_2 n \rceil$. You can count the number of passes as you go.
For example, suppose that $n=6$:
111111       Delete the first 1
b11111       Delete every other 1
2b1b1b       Delete every other 1
22bb1b       Delete every other 1
222bbb       Convert back to 1
111bbb       Done

The number of passes is $3 = \lceil \log_2 n \rceil$.


What learning algorithm is appropriate for predicting one time-series from another? I have eye-tracking data on two subjects -- a teacher, and a student. It's in the form (x, y, time), so there is a series of these for each subject. What the teacher looks at influences what the student looks at. What method would I use to predict what the student is looking at, using only teacher data? Lets say I can train some learning algorithm using a gold standard set of student and teacher data.

I was thinking hidden markov model would be appropriate, given the definition in Wikipedia, but I am not sure how to put this into practice over my dataset.

More detail: I have data about how a teacher and student each look at a map and some readings. I have 40 of these datasets, which look like [(366,234,0), (386,234,5), ...] which means the teacher looked at point (366,234) at time 0 and then 5 seconds later moved up to look at coordinate (386, 234). I can to learn a model to understand the relationship between how a teacher looks at content, to predict how a student will look at the same content. So maybe the student looks at the content in the same order as the teacher but slower. Or perhaps the student doesn't look around as much but the teacher scans more of the content. I have both sets of data and want to see how accurate of a model I can get -- would I be able to predict the student's looking behavior within 50px of the teacher's looking behavior?

If I understand your question right, you want to model two stochastic processes, where the 'student' process is driven by the 'teacher' process.

A hidden Markov model can represent such a relationship, but is restricted to a discrete state space. This means that you can only model a finite set of points on your map rather than continuous (x/y) coordinates. A Linear Dynamical System might suit better to your problem.

You could also use recurrent neural networks to model your system.


Confusion about "false sharing" This is a homework problem that I have

In a multicore system, you are running the code on the right on each core, and it suffers from false sharing. You can assume t_id is set to a unique thread identifier (e.g. 0-15). How could you change the code to reduce false sharing?

for (int i=0; i<N; i++)
    totals[t_id] += a[i];

What I'm having trouble with is seeing where the false sharing is occurring. It says state t_id is set to a unique thread identifier, so doesn't that mean there's only 1 thread that's accessing the data here?

We only briefly went over false sharing, but from what I've learned false sharing occurs when a cache miss occurs because the data was invalidated previously due to an "irrelevant" data being written/read from a different cache. But if the thread is the same, then doesn't that mean it's the same cache being used to write/read? How would false sharing occur here?

The false sharing is happening in the totals memory block.

The smallest unit of cache is a cache line. On standard x86 and ARM systems, a cache line is 64 bytes. On some PowerPC archs, the cache line is 128 or even 256 bytes. Reading from main memory into the cache is done one cache line at a time, and cache invalidation is done one cache line at a time.

Imagine each element of totals is a uint8. 64 elements of totals fit in one cache line. Every time += is called, the 64 byte cache line containing totals[tid] is read from and written to. That means every core is constantly invalidating that cache line, and the ensuing coordination, “false sharing”, is costly and unnecessary.

You could fix this while maintaining similar code structure by

Padding each element of totals so that it takes up a whole cache line
If totals has enough elements, offsetting your access so that multiple threads tend not to manipulate the same cache line. Ex: index by (tid * 64) % n_elements


Is there a more efficient stability index algorithm? I have this assignment for a class and we're beginning to learn time complexity. I have to find create a Java program that finds the stability indices of an array. Stability index being defined as a[0] + a[1] + ... a[i-1] = a[i+1] + a[i+2]+ ... a[n-1]. Essentially if you sum every element left of the index and every element right of the index(excluding the element at the index itself) and the two sums are equal, it is a stability index.

I believe its complexity is O(n^2) since I have nested loops both with worst case size of n. I'm having difficulty understanding how to make this more efficient. I thought perhaps there would be a way to calculate two different arrays of sequential sums. One would be increasing from index 0 and the other decreasing from the last index. Then compare the two values, but I'm not sure how to do this without nested loops.

Not looking for answers, just a push in the right direction.

EDIT: I made an improvement to O(N)

Assume you have the sum $a[1] ... a[i - 1]$ and $a[i+1] ... a[n - 1]$. You can directly check the "stability" for index $i$. Think of how much additional computation you need to calculate the "stability" for index i + 1. In an $O(N^2)$ solution you would need $O(N)$ additional work by just recomputing the sum again. Is there something better you can do to reduce this to $O(1)$ so that the overall runtime reduces to $O(N)$.

Basically can you reuse some information that you already calculated before?


Proof the number of expected node in a binary using mathematical induction The following algorithm constructs a binary tree.

MakeArray(array[x:y]) (
 if(x==y):
  the root is x
 else:
  pick a number r as root
  MakeArray(array[x:r-1])
  MakeArray(array[r+1:y])
)

Let $a_n$ be the expected number of nodes which have two children in the tree with $n$ nodes generated.
Prove $a_n = \frac{n-2}{n}+\frac{1}{n}\sum_{i=0}^{n-1}(a_{i}+a_{n-i-1})$ using mathematical induction.

I have no idea where to start as I don't even know how to construct a proper equation to carry on the proof. Any help is appreciated.

If the array has length $n = 1$ then the constructed tree consists just of a root. Therefore $a_1 = 0$. Similarly, $a_0 = 0$ (this is a corner case).
Now suppose that $n \geq 2$. Without loss of generality, assume that $x = 1$, and so $y = n$. The array splits into two halves: $1,\ldots,r-1$ and $r+1,\ldots,n$. The first has length $r-1$, and the second has length $n-r$. If $r = 1$ or $r = n$, the one of these halves is empty; this happens with probability $\frac{2}{n}$. So with probability $\frac{n-2}{n}$, the root has two children. Defining $i = r-1$, we see that $i$ is chosen uniformly among the $n$ options $0,\ldots,n-1$, and the two subarrays have lengths $i,n-1-i$. From here it is straightforward to deduce your formula, using linearity of expectation.
Your formula simplifies to
$$
a_n = \frac{n-2}{n} + \frac{2}{n} \sum_{i=0}^{n-1} a_i.
$$
This implies that
$$
(n+1)a_{n+1} - na_n = n-1 + 2 \sum_{i=0}^n a_i - (n-2) - 2 \sum_{i=0}^{n-1} a_i = 1 + 2a_n,
$$
and so
$$
a_{n+1} = \frac{n+2}{n+1} a_n + \frac{1}{n+1} \Longrightarrow a_{n+1} - a_n = \frac{a_n}{n+1} + \frac{1}{n+1}.
$$
Now
\begin{multline}
a_{n+2} - a_{n+1} = \frac{a_{n+1}}{n+2} + \frac{1}{n+2} = \frac{a_n}{n+1} + \frac{1}{(n+1)(n+2)} + \frac{1}{n+2} =\\ \frac{a_n}{n+1} + \frac{1}{n+1} = a_{n+1} - a_n.
\end{multline}
In other words, $a_n$ is an arithmetic progression. You can check that $a_n = \frac{n-2}{3}$ for $n \geq 2$.


Convex Hull in no particular order The proof for the $\Omega(n\log n)$ lower bound for calculating the convex hull by using order-type predicates that I have come across uses the fact that if there was possible to calculate the convex hull in time better than this, then we could do sorting using the same technique, but as it is known that sorting has an lower bound of $\Omega(n \log n)$, hence the lower bound for calculating the convex hull is also the same.

My question is, what if we don't want the convex hull in a cyclic order (clockwise or anticlockwise)? What if we just want the points lying on the convex hull. Surely, in such a case, we can't reduce sorting to this problem and hence the logic for lower bound does not hold. Do there exist any such algorithms? Or some alternative proof that still makes the previous lower bound hold true for this problem?

The generalization of comparison sorting you're looking for is algebraic decision trees.  In this model, element distinctness is the standard problem with an $\Omega(n\log n)$ lower bound.  The reduction to convex hull is straightforward: $n$ input numbers $x_1,\ldots, x_n$ are distinct if and only if the convex hull of $(x_1,x^2_1), \ldots, (x_n,x^2_n)$.

These lower bounds depend crucially on the decision tree model.  For the word RAM, it is a famous result of Chan and Pătraşcu that $o(n\log n)$ is possible.


Counting specific subgraphs For a given undirected graph G, I want to count all the subgraphs H that satisfies the following conditions:

H.V = G.V (The subgraph will containt all the original graph nodes)
H is connected

(Note: I don't care if two subgraphs are isomorphic)

The graphs which I will be working with will have |G.V| <= 15

Your problem is known as counting the number of connected spanning subgraphs, and is pretty hard even for restricted classes of graphs. See this question on cstheory.

The number of connected spanning subgraphs of a graph $G$ equals $T_G(1,2)$, where $T_G$ is the Tutte polynomial of $G$ (this is mentioned in one of the answers to the linked question). Hence this paper of Björklund et al., which shows how to compute said polynomial in vertex-exponential time (i.e., $\exp O(n)$), gives us hope, since in your case $n$ is pretty small ($n \leq 15$).


Running time analysis of a linear algorithm seems to me quadratic I have been analyzing an algorithm for several hours in order to find out why it is expressed as $O(n)$ (I saw this solution in a PowerPoint presentation which refers to it as a linear algorithm). I see a while  loop inside a for loop.

The for loop executes $n$ times.

The while loop executes "at most" $n$ times $(0, 1, 2, ..., n - 1)$ which can be represented as $n*(n+1)/2$

So, the running time formula can be $(n)*[n*(n+1)/2]$ which yields to a quadratic expression. (I have not taken into account individual statements inside the loops for simplicity).

What is wrong with my reasoning?

Algorithm spans2(X, n)
    S = new array of n integers
    A = new empty stack
    for i = 0 to n - 1 do
        while (!A.isEmpty() && X[A.top()] <= X[i] ) do
            A.pop()
        if A.isEmpty() then
            S[i] = i + 1
        else
            S[i] = i - A.top()
        A.push(i)
    return S

Inner while loop will be executed at most $L$ times, where $L$ is number of integers that will be added to stack $A$, and it will be at most $N$ pushes to stack, because A.push(i) is called in outer for loop, so body of inner while loop (A.pop()) will be executed at most $N$ times.


sum of squared distances from mean equals all-pairs sum of square distances? In this variance based k-clustering paper they claim that for a cluster with S points:

$$|S|\sum_{i \in S}{\|x_i-\bar{x}\|^2} = \sum_{a,b \in S,\ a<b}{\|x_a-x_b\|^2}\,.$$

Why is that? can you please show me the derivation?

This can be easily seen by a change of coordinates that makes the average $\bar{x} = 0$. This can be done by translating the whole plane, preserving all distances. Since the equation depends only on distances, its validity does not change.

Let us denote $|S|$ by $n$. The left hand side becomes $n \sum_{i \in S} ||x_i||^2$. The right hand side can be simplified as follows:

$$
\sum_{a < b} ||x_a - x_b||^2 = \frac{1}{2} \sum_{a, b} ||x_a - x_b||^2
= \frac{1}{2} \sum_{a, b} ||x_a||^2 + ||x_b||^2 - 2 x_a \cdot x_b
$$

The first equality follows from the fact that $||x_a - x_b||^2 = ||x_b - x_a||^2$. The second is simple expansion of quadratic expression of vectors.

If you split the sum and notice that the first two terms are equal to $n \sum_{i} ||x_i||^2$. You get that $\sum_{a, b} x_a \cdot x_b = 0$. This is easy to see since:

$$
\sum_{a, b} x_a \cdot x_b = \sum_{a} x_a \cdot \sum_b{} x_b = (\sum_{i} x_i)^2 = (n \bar{x})^2
$$

which is zero since the mean vector is zero.

Of course this calculation is all well known as an identity on variance. If you have a random variable $x$ such that $Pr[x = x_i] = 1/n$. Then, your left hand side is $n^2 Var(x)$ and the right hand side is the right hand side of the last equation stated here.


The Algorithm Design Manual - Working with the Big Oh I'm reading The Algorithm Design Manuel and one part is kind of confusing to me
The part that's confusing to me is how in the "Proving the Theta" section he proves that selection sort is Ω(n^2).
I mean, I understand that for some (c) c.n^2 can be a lower bound for selection sort, however I don't understand how he proves this in that section.
I would really appreciate it if you could help me understand that part.
Thanks.
.

It is difficult to avoid what is repeating what is in the text, but you have exactly:
$T(n) = (n-1)+(n-2)+\ldots+1+0 =n\tfrac{n-1}{2} = \tfrac12n^2 -\tfrac12n$
and as an upper bound taking each value up to $n-1$:
$T(n) \le (n-1)+(n-1)+\ldots+(n-1)+(n-1) =n(n-1) = n^2-n$
and as an lower bound taking values of at least $\tfrac n2$ down to $\tfrac n2$ and other down to $0$ $($assuming $n$ is even; the odd case gives $\tfrac14n^2+\tfrac14 n)$:
$T(n) \ge \tfrac n2 +\ldots +\tfrac n2 +0+\ldots +0 = \tfrac n2 \times \tfrac n2 +\tfrac n2 \times 0 = \tfrac14n^2$
Since all three are essentially of the order of $n^2$ up to a constant, you can conclude $T(n)$ is $O(n^2)$ and $\Omega(n^2)$ and so $\Theta(n^2)$


Find a path that contains specific nodes without back and forward edges I have a directed graph and and a set of nodes(set = [1,2,5,9,24...]). I want to find a path that contains all the set of nodes and this path dont contain back edges(cycles) and forward edges. For example for set = [1,3,4] the following path is acceptable:

but for the same set of nodes the following paths are not acceptable:

and

First of all i thought that it would be a good step to write bfs code for finding the nodes that i can visit from a specific starting node. Here is my code:

def bfs(G, s):
    q = queue.Queue()
    visited = []
    #Put s onto a FIFO queue
    q.put(s)
    #mark s as visited
    visited.append(s)
    #Repeat until the queue is empty
    while not q.empty():
        #remove the least recently added vertex v
        v = q.get()
        #for each unmarked vertex pointing from v:
        #add to queue and mark as visited
        for node in G.neighbors(v):
            if node not in visited:
                q.put(node)
                visited.append(node)
    print(visited)

Does anyone have any idea about how to modify bfs algorithm for finding the path containing specific nodes without back and forward edges? Can you write a pseudocode example?

This is the Hamiltonian path problem.  No efficient algorithm is known, and it is widely suspected that no efficient algorithm exists.  You can read the linked article for references that suggest a variety of algorithms for this problem.


Is the universe problem for one-counter automata with restricted alphabet size undecidable? Consider the following universe problem.

  The universe problem. Given a finite set $\Sigma$ for a class of languages, and an automaton accepting the language $L$, decide if $L=\Sigma^*$.

In [1], it is stated and proved that the universe problem is undecidable for a particular class of one-counter automata. This result then follows for the class of all non-deterministic one-counter automata. I'm wondering if it is known whether this problem is still undecidable when we restrict the size of the input alphabet of the automaton.

I think that with alphabet size 1 the problem becomes decidable, but what about size 2? And if that turns out to be decidable what is the smallest value of $n \in \mathbb{N}$ such that the problem is undecidable.

I think it's probable that the answer to this question is known but I'm having trouble finding an answer. If it is already known then I would appreciate a reference.

[1] Ibarra, O. H. (1979). Restricted one-counter machines with undecidable universe problems. Mathematical systems theory, 13(1), 181-186

It must be undecidable for an alphabet with two symbols. It is possible to code any alphabet into two letters, e.g., map 16 symbols to the length 4 binary strings $aaaa, aaab, \dots, bbbb$. Then equality to $\Sigma^*$ is equivalent to equality to all possible codes for strings. In the 16 letter example this means equality to all strings of a multiple of four letters. Clearly that is not universality. That is obtained by adding those binary strings that are not coding. That is a regular set and can be generated by a one counter automaton.

The same explanation, with $\LaTeX$ for those who appreciate it.
Assume universality is undecidable for $\Sigma$. Let $h: \Sigma^* \to \{0,1\}^*$ be an injective morphism. Now $L = \Sigma^*$ iff $h(L) = h(\Sigma^*)$. This in turn is equivalent to $h(L) \cup R = \{0,1\}^*$ where $R$ is the (fixed) regular language $\{0,1\}^* - h(\Sigma^*)$. Hence we cannot decide whether the binary one counter language  $h(L) \cup R$ is universal. Note that language is one counter as the family is closed under morphisms and union (with regular languages).

As you state "I think that" I can also confirm the question is decidable for a one letter alphabet. It is decidable for push-down automata (hence context-free languages) as one letter CFL are (effectively) equivalent to regular languages.


What is the closed-form expression for $T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1$ where $T_1 = 1 ?$ Problem:

  Find the closed-form expression for$$
T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1
\tag{1}
$$where $T_1 = 1 .$

Calculating this sum I came up with the following result:
$$
T_n = 8^{\left(n-1\right)}
\tag{2}
\,,$$
but is this result correct?

I know the sequence is:$$
\begin{align}
 T_1 & =  1 \\
 T_2 & =  8 \\
 T_3 & = 64 \\
     & ~~\vdots
\end{align}
$$

Questions:

What would be the closed-form of $T_n ?$
What would be the best way to find it?

After calculating a few values, you can guess the solution and then easily prove it by induction. Another way to find it is to use "creative cancellation":
$$1 + 7 (T_1 + \cdots + T_{n-1}) = T_n = (T_n + \cdots + T_1) - (T_{n-1} + \cdots + T_1).$$
Hence if you put $S_n = T_1 + \cdots + T_{n-1}$, you deduce
$$
S_n = 8S_{n-1} + 1.
$$
In order to make this homogeneous, take $R_n = S_n + c$:
$$
R_n = S_n + c = 8S_{n-1} + 1 + c = 8(R_{n-1} - c) + 1 + c = 8R_{n-1} + 1 - 7c.
$$
Choosing $c = 1/7$, this gives $R_n = 8R_{n-1}$, and so $R_n = 8^{n-1} R_1$. Now $R_1 = S_1 + 1/7 = T_1 + 1/7 = 8/7$, and so $R_n = 8^n/7$.

It follows that $S_n = (8^n-1)/7$ and $T_n = S_n - S_{n-1} = (8^n - 8^{n-1})/7 = 8^{n-1}$.

Let me conclude by giving a combinatorial interpretation for the recurrence. I will show that $T_n$ is the number of base-8 numbers of length $n-1$. Indeed, any such number is either 0, or starts with a non-zero digit followed by a number $i < n-1$ digits long.


What are the practical uses of ontologies? I have read many papers and books about ontologies and I am trying to figure out that how they are used in a real project?

For example how the ontology for a soccer player robot can be defined and used with a cognitive architecture in order to make it intelligent?

Are ontologies relations between terms in that domain of knowledge ( for example relation between the ball and foot word and physical rules definition and their relation with the foot and ball movement , ...) or relations between tactics , strategies and different mixtures of tactics ?

Are there any clear examples of ontology usage in real projects and their combining usage with the cognitive architectures like ACT-R for augmenting the cognitive architecture?

I don't know about robotics, but ontologies are part of the standard toolkit for modern expert systems, especially those with a natural language processing component.

For example, consider the process of performing literature searches for systematic reviews in medicine. Of the millions of medical studies out there, reviewers need to find the 20 or so high-quality randomised control trial studies which are relevant to the clinical question that they want to answer. This is a classic needle-in-a-haystack problem, and computer scientists would like to build tools to aid the search.

Medical ontologies such as MeSH, ICD, and GALEN play a role in this, because they represent an "answer" to the question of what a given medical study is "about".


finding maximum virtual and physical memory If the following is given:

CPU uses a four-level hierarchical page table, each level can contain 512 entries
the page size is 4KB.
virtual address is 48 bits

How do i get the size of the virtual memory (in terms of pages or bytes). Do i just use the number of page table entries 29*4+12 ?

And can i get the size of the physical memory given this information ?

No, you can't get size of physical memory with the provided information.

Explanation:

Virtual memory that you mentioned is correct. But you can calculate
it just by seeing the number of bits virtual address has (What you
did is correct though).
To calculate the physical memory, we need to know that Physical memory is a collection of frames, which has same size as pages. Since
Page size is already given (4KB), next we need to know how many
frames does main memory(physical) has. For this we need to know the
size of page table entry, which contains frame address. If we know frame
address length, then we can calculate the total number of frames by
calculating  2^(length of frame address).
Then you can multiply the frame size (4KB) with the above value to get the size of Physical memory.


What is a Meta algorithm? I am currently reading a survey paper on the multiplicative weight update meta-algorithm. I am not quite sure what they mean by "meta-algorithm". Is it simply a general algorithm that can be used for different purposes?

I couldn't find any exact definition for this term, though I have found examples of meta-algorithms such as Boosting in machine learning.

I interpret it as meaning "algorithmic technique".  It's a general framework that can be used to solve a number of problems.

Don't worry too much about the meaning of that phrase.  It's not something with an accepted definition, and you don't need to understand it to gain the value from that survey paper; it's just a passing phrase.  Instead, focus on understanding the ideas and technical results in the survey paper.


Correcting two-bit error using a CRC What algorithm can be used to correct a two-bit error in a message protected by a 32-bit CRC, assuming the CRC polynomial allows that? I'm seeking something for 480-bit payload, able to detect uncorrectable errors, fast in the worst case, and compact.

Because I have hardware support for that, I'm most interested in the CRC-32 IEEE 802.3 primitive polynomial (allowing two-bit error correction for payloads up to 2974 bits),
$$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^2+x+1$$
but the question is of theoretical interest for others, such as the CRC-32K polynomial proposed by Koopman (allowing two-bit error correction for payloads up to 16360 bits)
$$(x+1)(x^3+x^2+1)(x^{28}+x^{22}+x^{20}+x^{19}+x^{16}+x^{14}+x^{12}+x^9+x^8+x^6+1)$$

Assume payload data of $b$ bits (assimilated to the coefficients of a binary polynomial $B(x)$ of degree less than $b$), to which is appended a CRC computed with binary polynomial $P(x)$ of degree $c=32$, as $C(x)=(B(x)\;x^c)\bmod P(x)$. It is then stored in memory $b+c$ bits of $B(x)\;x^c+C(x)$. On reading is it computed the syndrome $S(x)=(B'(x)\;x^c+C'(x))\bmod P(x)$. Assuming there has been at most two bits in error, and $b$ is small enough:

If $S(x)=0$, then there has been no error.
Otherwise, if there exists $i$ with $0\le i<b+c$ such that $S(x)=x^i\bmod P(x)$, then there has been a single error, and $i$ tells where, allowing correction.
Otherwise, there has been two errors and there exists $i$ and $j$ with $0\le i<j<b+c$ such that $S(x)=(x^j+x^i)\bmod P(x)$; again finding $(i,j)$ allows correction.

The case of a single bit in error is relatively easy; that's a discrete logarithm problem, with an easy size versus speed compromise: we can have a precomputed table allowing solving in a single lookup for $i$ multiple of $k$, and use that $k$ times. But I'm stuck with the case of two bits where I have nothing much better than trying all $j$ and doing as for a single bit in error.

One approach: Use a meet-in-the-middle algorithm.  Build a precomputed table that stores $T_i = x^i \bmod P(x)$ for all $i$ up to the maximum message length.  Now, given $S$, you are looking for $i,j$ such that $S = T_i + T_j$.  This can be found by enumerating all $i$, and for each $i$, computing $S-T_i$ and checking whether it is present in the precomputed table.

The running time is proportional to the maximum length of the message.  I'd imagine that in a real deployment, two-bit errors will be rare enough that this running time is affordable.  (If two-bit errors are common, then three-bit errors will have non-negligible probability, which is a problem of its own.)

If you want to reduce space complexity, instead of storing the entire precomputed table and looking up $S-T_i$ in the table, compute the discrete log of $S-T_i$ for each $i$ using whatever method you prefer (such as the one you listed in your question).

I don't know if there are smarter methods that exploit the structure of $\mathbb{F}_2^{32}$ in a more intelligent manner.


Why is determining the size of a maximum independent set or a clique in P? I read that determining the size of the maximum independent set (and also a clique of maximum size) is in P. The versions that find the actual solution are known to be NP-hard.

With respect to finding clique size, you can sort the node degrees, decrement $i$ from $|V|$ to $0$, and each time check if you have $i$ elements of node degree $i$, pick the power set of those $\geq i$ elements and verify the clique. However, picking the power set is exponential, and this algorithm would give you the solution itself. I have a hard time figuring out how you can construct an algorithm that decides the presence of a clique (or independent set) of a certain size in polytime, but doesn't give you the solution.

I would be interested to see what you read, but determining the size of the maximum independent set is $NP$-hard (of course clique is equivalent, so I'll just talk about independent set). Recall that the decision problem "Does the graph $G$ contain an indepedent set of size at least $k$?" is $NP$-complete. If we could determine the size of the maximum independent set ($\alpha(G)$) in polynomial time, we could answer this decision problem in polynomial time by taking $G$, getting $\alpha(G)$ from our polynomial time algorithm, then if $k \leq \alpha(G)$, we say $Yes$, if $k > \alpha(G)$ we say no. Hence a polynomial time algorithm for determining the maximum would immediately give us $P=NP$.

Perhaps you read that determining the size of a maximal independent set is poynomial time solvable. A maximal set is just one that cannot be made larger, so we can (typically, and certainly for independent sets) compute these greedily.


Complexity of a decision problem: system of linear equations over finite field with restricted solutions I have a system of linear equations over a finite field $\mathbb F_p \cong \mathbb Z_p$, and I'm interested in the decision problem of whether there exists a solution where all of the variables $x_i$ are in the set $\{0, 1\} \subset \mathbb F$. In particular, I'm trying to determine whether this problem is $\mathcal{NP}$-hard.
Example
One system of equations over $\mathbb F_3$ is:
$$
  \begin{alignat*}{2}
  &x_1\begin{bmatrix}1 \\ 1 \\ 0\end{bmatrix} +
  x_2\begin{bmatrix}0 \\ 0 \\ 0\end{bmatrix} +
  x_3\begin{bmatrix}0 \\ 2 \\ 0\end{bmatrix} +
  x_4\begin{bmatrix}1 \\ 0 \\ 1\end{bmatrix} \\ + \,
  &x_5\begin{bmatrix}2 \\ 1 \\ 0\end{bmatrix} +
  x_6\begin{bmatrix}0 \\ 1 \\ 1\end{bmatrix} +
  x_7\begin{bmatrix}1 \\ 0 \\ 0\end{bmatrix} +
  x_8\begin{bmatrix}1 \\ 2 \\ 0\end{bmatrix} =
     \begin{bmatrix}0 \\ 0 \\ 2\end{bmatrix}.
  \end{alignat*}
$$
This system of equations is satisfiable with entries in $\{0,1\}^8 \subset \mathbb F^8$, namely $$
  \begin{align*}
  (x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8) &= (0,0,0,1,0,1,1,1) \hspace{1em}\text{or}\\
  (x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8) &= (0,1,0,1,0,1,1,1).
  \end{align*}
$$
An unhelpful (?) reduction
One suggestion that was given to me was turning this into a system of quadratic equations in the following way: define auxiliary functions coordinatewise $$
\begin{align*}
  w_1 &= x_1 + x_4  + 2x_5 + x_7 + x_8 \\
  w_2 &= x_1 + 2x_3 +  x_5 + x_6 + 2x_8 \\
  w_3 &= x_4 + x_6 - 2,
\end{align*}
$$ and use these to solve the system of quadratic and linear equations $$
  w_1 = w_2 = w_3 = x_1^2 - x_1 = \cdots = x_8^2 - x_8 = 0.
$$
However, the MQ-problem (Multivariate Quadratic equations over a finite field) is $\mathcal{NP}$-hard, so this reduction doesn't help. However, this set-up is a quite special case, so I'm holding out some hope that the original problem might still be in $\mathcal{P}$.

Is there a polynomial-time algorithm for determining the existence of a solution of linear equations over a finite field with restricted variables? Or is it known if this problem is $\mathcal{NP}$-hard like the MQ-problem?

You can reduce 1-IN-3 SAT to your problem (an instance is a 3CNF, and we want to find a satisfying assignment having exactly one satisfied literal per clause), assuming $p \geq 3$.
A clause $x \lor y \lor z$ is encoded as the constraint $x+y+z=1$.
A clause $\bar x \lor y \lor z$ is encoded as the constraint $1-x+y+z = 1$; and so on.
When $p = 2$, your problem becomes easy.