At what point do electrical signals become actually logic and programmable language? I get that one transistor can store a value of 1 or 0. That's not the problem. What I don't get is how the fact that a transistor represents a 0 can translate into logic? How do these transistors turn each other one or of? Is there a uniform pattern to the circuit? how do these electrical signals magically transform into mathematical equations? Is there a specific set of transistors that deal with addition? Another set for subtraction? How does the kernel transform this into programmable language? How the hell do these transistors know which pixels to colour and what to colour them with? WHAT VOODOO MAGIC IS THIS? I am pretty curious as to how this magical transformation happens, but I'm also pretty stupid, so please dumb it down a lot...

Most your questions are covered by the field of "Switching Circuits" (and more generally, "Circuits and Logic Design", which are both part of computer engineering.

Try to find a textbook on switching circuits: it will explain how to take transistors and create AND / OR / NOT gates out of them.
Then find a book on logic design: it will explain how to use AND/OR/NOT gates to build more sophisticated logic primitives such as flip-flops and latches (as well as adders, subtractors, or even a CPU)

Then you will (hopefully) have more insight regarding how the low-level works to realize the high-level ideas.


Intersection of O(n) expanding circles with line from the origin I am interested resolving a programming challenge problem, but I'm struggling obtaining an efficient solution.

  Consider yourself as a point located on the origin $(0,0)$ of an infinite
  two-dimensional flat world. There are $n$ sea waves surrounding you,
  each one modeled as a circle with center $(x_i, y_i)$, initial radius $r_i$,
  and propagation speed $s_i$, so that the radius of wave $i$ as a function
  of the time $t ≥ 0$ is $r_i + s_i \cdot t$. You choose any fixed
  direction and run “forever” at speed $p$. Will you be able to scape?

Some helpful restrictions given as assumptions are provided:

  $1 ≤ p ≤ 1000$
  $3 ≤ n ≤ 10^4$ [the number of circles $c_i$]
  $−1000 ≤ x_i,\;y_i ≤ 1000$
  $1 ≤ r_i ≤ 1000$
  $0 ≤ s_i < p$
  Except for $n$, all numbers are real, with at most three digits after the decimal point.
  Initially, you are strictly outside all the waves.
  There are not precision errors.

My solution so far is quite simple (I have programmed it in C++):

Each "fixed direction" to run forever is solely determined by the angle of that line with the X axis, namely $0 \leq \theta < 2 \pi$.
For each $\theta \in [0, 0.001, 0.002, \dots, 2\pi)$:

Recall that the map is within the square $[-1000, -1000]$ to $[1000, 1000]$, and the furthest distance between $(0,0)$ and any point in the map has distance $1000\sqrt{2}$. We advance at $p$ speed, so at most we will compute $1000\sqrt{2}/p \approx 1414/p$ iterations.
For each $t \in [0, 0.001, 0.002, \dots, 1414/p]$:

My position at time $t$ in line $\theta$ is $pos_t = (\cos \theta \cdot t \cdot p, \sin \theta \cdot t \cdot p)$.
Check whether $pos_t$ is inside any sea wave at moment $t$. Basically, check if the distance between $pos_t$ and the center of each circle is less than that circle's radius at moment $t$, namely $r_i + s_i \cdot t$. If so, bad luck; we're done with this $\theta$ and we continue the search.
If not, try with next $t$.

If no intersection is found after iterating all $t$s, then you will be able to scape (through line with angle $\theta$).

If all $\theta$s got some intersections, then we are not able to scape.

This solution has cost $\Theta(6000 \times 1400 \times n)$, which is impractical for $n \leq 10^4$. Informally, and without being precise, the multiplicative term may be $O(n^3)$ if $n \leq 10^4$ is considered.  Plus, it may not be correct, as I am assuming that $\Delta t = 0.001$ is fine; same for the angle.

I have thought about another idea, which is reducing systematically $\theta$. For instance, let's imagine that we've got a circle at $C = (5, 5)$ (in the line of $\theta = \pi/2$) with some small radius. From the beginning, we know that angles $\theta = \pi/2 \pm \alpha$ will never be an option, being $\alpha$ determined by tangent lines from $(0, 0)$ to $C$ and $t$; the more time passes, the higher $\alpha$ will be and thus the wider will be this range of restricted angles.

So, at moment $t$ we have a set of ranges of possible $\theta$s, and that range is reduced as long as $t$ increases (unless all waves have speed 0, for sure).

But how to continue from there? I see the same problems as with my implementation: determining $\Delta t$ and $\Delta \theta$.

I ask for your help to find a better algorithm. I suspect that there may be an algorithm that is just $O(k n)$ or $O(k \cdot n \log n)$ with $k$ being reasonably small.

The solution outline:

Step 1. Verify, that all the initial (at the moment $t=0$) wave circles don't contain your starting point $(0,0)$. If yes, then continue - otherwise exit, no escape.

Step 2. For each wave circle $W_i$ you need to find an escape sector - the range of directions, where the escape is guaranteed.

Imagine a circle of your possible positions at moment $t$ with center in $(0,0)$ and radius $pt$ - we'll call it the circle $C$. Let's consider what will happen with circles $C$ and $W_i$ with time. Originally (when $t=0$) the circle $C$ is just a point at $(0,0)$. Then, with time increasing, the expanding circle $C$ will at first touch the expanding circle $W_i$ at a single point, then intersect it at two points. Moving further, at some point of time the expanding circle $C$ will touch the circle $W_i$ again at a single point, then it will contain the circle $W_i$ completely (because $p \gt s_i$).

Two intersection points between circles $C$ and $W_i$ define a no-escape sector. This sector angle $\alpha$ grows from zero to some maximal value and then decreases to zero again. Cosine of this half-angle at the moment of time $t$ can be found from the triangle with all known sides:

$$\cos(\frac {\alpha} {2}) = \frac {(pt)^2+d_i^2-(r_i+s_it)^2} {2d_ipt}$$

where $d_i = \sqrt{x_i^2+y_i^2}$.

You need to find positions of intersection points, which will give you this maximal angle value. In order to do that you can take first derivative of the non-escape sector half-angle by time and set it to zero - that will give you the moment of time when the non-escape sector is maximally wide. This moment of time $T_i$ will be:

$$T_i = \sqrt{\frac{d_i^2-r_i^2}{p^2-s_i^2}}$$

Knowing the non-escape sector you'll easily find the escape sector.

Step 3. If intersection of all the escape sectors is non-empty, then the escape is possible.

The algorithm time is obviously $O(n)$.


Bubble in a pipeline When NOPs are introduced in the pipeline by the control unit, how does they really cause the pipeline to stall? I mean, at every clock cycle, the pipeline register will eventually forward its contents to the very next stage, so how does NOPs prevent that from happening?

Also when NOPs are introduced the PC doesn't increment and no fetch occurs? How does that happen?

Inserting NOPs is the stall. It delays execution until the result is ready.

A simple pipelined CPU will have a instruction decoder that controls the entire CPU at a low level setting control lines to each functional unit to control how it behaves. Including whether to pull in a new instruction.

The decoder checks dependencies between instructions and when it sees it needs to delay it will stop pulling in new instructions until it can start the new one.

More advanced CPUs with out-of-order execution (every non-mobile/non-embedded CPU nowadays) will pull in a few more instructions and only start those that don't need to wait on data. The details of out of order execution is too complex to fully explore in this answer.


Databases and B-Trees: What are Keys and how are they related I confused about the description & definition of "key" occuring as terminology for databases and b-trees.
In first case dealing with theory of databases a key is defined as a choice for a in certain sense minimal (see below) subset $K \subset A := \{A_1,A_2,...,A_n\}$ of a fixed set of attributes $A_i$ parametrizing a data table (consisting of relations; a single relation is abstraction of a row in the table), where each attribute is literally a column specifying a property of objects = relations.
A key is characterized by property that there exist no two different relations (a relation is a row) which have exactly the same values for all attributes which belong to the key. And a key is a minimal subset with this property, ie there not exist a proper smaller subset of attributes contained in the key and having the property described in last sentence. Clearly keys are not unique. So the set of a keys is certain subset of the power set $\Omega(A)$ of the set attributes $A_i$. See also here: https://en.wikipedia.org/wiki/Unique_key
On the other hand the key concept occures as well for b-trees: https://en.wikipedia.org/wiki/B-tree#Definition
Here keys are a priori numbers or integers and different knots of b-tree contain different totally ordered subsets of keys where the total order on the space of keys is inherited from the order "$\ge$" for integers $\mathbb{Z}$. Especially the set of keys is a totally ordered subset of integers.
Question: How are the two concept of 'key' related to each other? My first idea was that if we consider in light of for definition (as elements of power set of attributes), we can simply randomly enumerate all the keys (that is associate to each key an number; formally speaking to specify an injection $f:\mathcal{K} \to \mathbb{Z}, K \mapsto f(K)$ where $\mathcal{K} \subset \Omega(A)$)
and then treat them as numbers when working with b-trees. Is this exactly the correct connection or is there another deeper one and my approach is wrong?

There's an indeed a relation that maps the database keys to the B-trees keys $K_d \mapsto K_b, K_b \in \mathbb{Z}$
The B-Tree keys are not random though, they represent the physical location of data stored for that key.   At the leaf level there are multiple ( up to the order of the tree) database $K_d$s associated with a single $K_b$ key. The relation is thus not an injective function.


What is the impact of synchronisation overhead on parallel speedup? When implementing a parallel version of an algorithm, what is the impact of synchronization delays on speedup efficiency? Does this depend on the platform used?

Is coarse-grained parallelism better than fine-grained parallelism in certain situations?

For current multicore CPUs with support for SMT (Simultaneous Multi Threading), coarse-grained parallelism is strictly required, independently of the parallel technology used (pthreads, OpenMP, MPI). You need to feed each thread or process with enough work, otherwise the cost of thread creation/management and synchronization (for Pthreads and OpenMP) or the cost of communication and synchronization (for MPI processes) will be much higher than the work done per thread/process.

For GPUs, since these are actually SIMD units, i.e., data parallel machines, you need to feed them with data according to a fine-grained data decomposition (again, this is independent from the actual technology used, such as CUDA or OpenCL). In this case, thread management is lower (because it is done in hardware, not in software), but in general synchronization must be avoided, as much as possible. If you can not restructure your code so as to avoid synchronization you are going to experience bad performances on GPUS. Both NVIDIA and AMD recommend to avoid synchronization and to use GPUs for very simple data parallel tasks.
Moreover, you need to copy the data to be processed from the host to the GPU and back once results are computed, and this will also incur a performance penalty, depending on the size of your data processed by the GPU device.


What is the overhead of Virtual Memory? What is the price paid for the vast virtual address space provided to
programmers for their applications? Or in other words, what is the overhead due to virtual memory?

Is there any other overhead from implementing virtual memory, beyond memory consumed by the kernel?

One major overhead of virtual memory is that virtual pages that are being used in the current computation have to
be loaded in physical memory, which usually means also transferring
out another page back on disk. Since this is costly, you want to avoid
doing it too often. Hence an important concept is the locality of
programs: though a program may have to use considereable space, you
try to organize the program so that only a much smaller part of memory
is used at any time, a smaller part that evolves only slowly.

THis concerns the code being executed, but also the data used. And
data is often orders of magnitude larger than the code. So, a program
handling large amounts of data will often be organized so as to
improve the locality of the data organisation in memory (but this depends also on what the code does with the data). As a
consequence, too naive a use of classical textbook algorithms may result in
very slow programs, because of too many page faults.

I guess there are tools to analyze the locality of programs, or to
optimize them to improve it. A specific example is the design of
garbage collectors, which have developed various techniques to improve
data locality by reorganizing the information, and which are of course
design to explore the memory in a very local way, for example by
looking in priority at pages the main program has already loaded in
physical memory.

Programs with bad locality spend too much time loading pages compared
to actual computing time. This is called thrashing.


Why more and more handcraft lex do not use regular expression any more? Recently I read the source code of Clang, and found that it just do the lex thing  by reading characters one by one and manually do the matching. But both my teacher when I'm in college and the book "Compilers Principles, Techniques, and Tools" take lots time to illustrate how to build a regular expression state machine, and I remember the tool Flex also build a state machine (correct me if I'm wrong). I think it's easy to lost in the manually matching code and if there's something changed in a language, it is a little difficult to update the matching code.

So why nowadays people prefer to manually do the matching rather than use regular expression? Is this because the table generated by the regex tool too big if the token table is complicated? Or is this an efficiency trade-off?

p.s. Evidence for "more and more":

Clang
Gcc (as long as they abandoned flex/bison)
OpenJDK
Python
Protobuf

What interesting is, the author of protobuf wants to use regular expression, but give up due to open source project get better keep independent, I think this counts a reason.

While I cannot give you a definitive answer, but I think there are a couple of reasons for handcrafting lexers and parsers:

Good error reporting and recovery: most of tools such as Lex that provide a declarative way of defining regular expressions are hard to customize for error reporting or recovery. When you hand-craft your lexer or parser, you have more control when you encounter an error.
Performance: while Lex is using Finite State Automata in their lexers, and they are efficient (assuming the automata can be loaded in memory) it may pay off to handcraft your lexer to have a tight control on both runtime and memory usage. Most regular expression engines in programming languages use backtracking and may have exponential worst case runtime.
Infrequent changes: the token definitions (and even syntax) of programming languages doesn't change that often. So I think in the prototyping phase it makes sense to use a tool to automate the process, but when the syntax became stable, it will pay off to handcraft the lexer and parser, both in terms of error reporting and performance.


BIT: range updates, point queries; true meaning of tree[x] for the past few days I've been studying Binary Indexed Tree (aka. Fenwick tree) data structure.

I understand the basic form of BIT (point update, range query), and I see the intuition behind it, but when it comes to range update - point query BIT I don't see the intuition behind it.

Let me be more specific:

let tree be an array where we represent our BIT
let A be an ordinary array where our array values are stored. both tree and A are initially zero

For the point update - range query, we know that tree[x], where x is some index, stores cumulative frequency for elements(values) [x - 2^r + 1, ... , x], where r is position of the last non-zero bit (looking from left to right in binary notation of number x)

Example:

array A: 1 3 6 7 5 5 2
x: ------  1 2 3 4 5 6 7 8
tree(x): 1 2 1 3 2 3 1 7
tree(6) = 3 (6 in binary is 110, r=1, 6 - 2^1 + 1 = 5; so tree(6)   stores frequencies for 5 and 6; in our example, number 5 appears 2 times and number 6 appears only once)

But, for the range update - point query i don't know the following:

a) what tree[x] represents. What is the true meaning for the value that is stored in tree[x] (for range update - point query).

b) To update range, say from a to b with value v, we will do the following operations:

update(a, v)
update(b + 1, -v)
and then query(x) returns value of A[x]

Why does the query(x) returns value of A[x], what is the proof(please give some example or resource with example) for that.

In quest for the answer i found the following resources but none of them helped for the questions above:

1: https://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree

2:
http://apps.topcoder.com/forums/;jsessionid=1749A5CAC2EA52B51F5509E8355A2CD3?module=Thread&threadID=715842&start=0&mc=8#1407869

For BIT and its variants, I recommend this article: http://coutcode.com/blog/binaryindexedtree/

The core of BIT is point update - range query, ie. for array $A[1 \dotsc n]$, BIT supports following operations:

$A[k] \leftarrow A[k] + d$ (Point update(k,d))
query partial sum $S[k] = A[1] + A[2] + \dotsb + A[k]$ (Range query(k))

Other variants are just converting to 1 or more of this case.

For range update - point query, it requires support following operations for array $A[1 \dotsc n]$:

$A[i] \leftarrow A[i] + d$ for all $a\le i < b$. (Range update(a,b,d))
query value of $A[k]$. (Point query(k))

First, noting that after range update $A_1[i] \leftarrow A[i] + d, (a \le i \le b)$, we have $$\begin{align}A_1[a]-A_1[a-1]=&A[a]-A[a-1]+d\\A_1[b+1]-A_1[b]=&A[b+1]-A[b]-d\\A_1[i]-A_1[i-1]=&A[i]-A[i-1]\ (i\notin\{a,b+1\})\end{align}$$
Taking $$D[i] = \begin{cases}A[i],&i=1\\A[i]-A[i-1],&1<i\le n\end{cases}$$ then there are only 2 updates $$D[a]\leftarrow D[a]+d\\D[b+1]\leftarrow D[b+1]-d$$ and $$\begin{align}A[k]=&A[1]+(A[2]-A[1])+\dotsb+(A[k]-A[k-1])\\=&D[1]+D[2]+\dotsb+D[k]\end{align}$$

Thus building BIT on $D[1\dotsc n]$, we convert the range update$(a,b,d)$ on $A$ to 2 point updates $(a,d)$ and $(b+1,-d)$ on $D$, and the point query $(k)$ on $A$ is just the range query $(k)$ on $D$.


How to derive the size of $k = \log n$ base from $\frac{1}{2^k} = O(\frac{1}{n})$? "We need $k$ to be large enough so that $(\frac{1}{2})^k = O(\frac{1}{n})$, and to do this we can choose $k = \log_2 n$. Thus, when $k = \log_2 n$, the size of the active region has been reduced to a constant, at which point the recursion bottoms out and we can search the remainder of the array directly in constant time."

Im not certain on how they determine that $k$ needs to be $\log_2 n$ from $(\frac{1}{2})^k = O(\frac{1}{n})$. Can someone please clarify the logic for this please?

Think about it if we remove the fraction. We need a $k$ large enough so that $2^k = O(n)$. We could do this simply by solving for $k$ in the expression $2^k = n$. Which is simply $k = \log_2 n$. This is because $2^{\log_2 n} = n$.

Now apply the same logic to your expression, with $k = \log_2 n$ we see that: $$\frac{1}{2^{\log_2 n}} = \frac{1}{n} = O\left(\frac{1}{n}\right)$$


How to efficiently create balanced KD-Trees from a static set of points From Wikipedia, KD-Trees:

  Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction and hence eliminate the costly step of finding the median at each level of subdivision. [..] This algorithm presorts n points in each of k dimensions

I fail to understand how that is actually done. Consider this example:

Lets say I have 5 points in an array.

0 = (4, 7)
1 = (2, 9)
2 = (5, 4)
3 = (3, 6)
4 = (2, 1)

I suppose we now want to create 2 sorted arrays, one by X and one by Y ?

Sort them by X     Sort them by Y
1 = (2, 9)         4 = (2, 1)
4 = (2, 1)         2 = (5, 4)
3 = (3, 6)         3 = (3, 6)
0 = (4, 7)         0 = (4, 7)
2 = (5, 4)         1 = (2, 9)

We start creating the KD-Tree. Lets split by X axis, at the first step. We select the median of the points, 3 = (3, 6), so the Left and right trees will like this:

Left  (first half)
1 = (2, 9)
4 = (2, 1)

Right  (second half)
0 = (4, 7)
2 = (5, 4)

Now we want to sort the Left and the Right trees by Y axis. How are we supposed to make use of the points that we sorted previously by Y axis ?

The only solution in my eyes is to re-sort the Left and Right trees respectively, by Y axis. What is Wikipedia talking about ?

At depth = 1, with your pre-sorted Y list, you'll still need to perform a comparison to the parent node (and compare by X value).

This ensures that items on the left branch will have X value less than parent node, and items on right branch will have X value greater than parent node.

Since at depth = 1, your list is already pre-sorted by Y value, you save time from sorting at each level.

In the case that your item is the same as the parent node, you don't insert, because that node is already the parent.


Difference between Data point, attribute, feature? Can anyone tell me the difference between the following in data mining? I am taking a class this semester and the professor is using the terms so frequently, I don't know what these mean anymore.

Data point
attribute
feature

An attribute is usually synonymous with feature, both of which refer to a single dimension. A data point probably refers to a complete record. That is, a data point is a collection of features.

For example, imagine we have a bunch of data on people and we want to classify each one as being male or female. Specifically, for each person (record), we have the following attributes (features): height, weight, and eye color. A data point would be one person's 3-dimensional record (e.g. [74in, 200lbs, brown] or [61, 125, blue]).


Difference between cross edges and forward edges in a DFT In a depth first tree, there are the edges define the tree (i.e the edges that were used in the traversal).

There are some leftover edges connecting some of the other nodes. What is the difference between a cross edge and a forward edge?

From wikipedia:

  Based on this spanning tree, the edges of the original graph can be divided into three classes: forward edges, which point from a node of the tree to one of its descendants, back edges, which point from a node to one of its ancestors, and cross edges, which do neither. Sometimes tree edges, edges which belong to the spanning tree itself, are classified separately from forward edges. If the original graph is undirected then all of its edges are tree edges or back edges.

Doesn't an edge that is not used in the traversal that points from one node to another establish a parent-child relationship?

Wikipedia has the answer:

All types of edges appear in this picture. Trace out DFS on this graph (the nodes are explored in numerical order), and see where your intuition fails.

This will explain the diagram:-

Forward edge: (u, v), where v is a descendant of u, but
not a tree edge.It is a non-tree edge that connects a vertex to a descendent in a DFS-tree.

Cross edge: any other edge. Can go between vertices in
same depth-first tree or in different depth-first trees. (layman) It is any other edge in graph G. It connects vertices in two different DFS-tree or two vertices in the same DFS-tree neither of which is the ancestor of the other.(formal)


Subtracting lower-order term to prove subtitution method works Substation method fails to prove that $T(n)=\Theta(n^2) $ for the recursion $T(n)=4T(n/2) + n^2$, since you end up with $T(n) < cn^2 \leq cn^2 + n^2$.

I don't understand how to subtract off lower-order term to prove that substitution works.

Came up with: $T(n) \leq cn^2 - bn^2$

Assume it holds for $T(n/2) \leq c(n/2)^2 - b(n/2)^2$

$T(n) \leq 4(c(n/2)^2 - b(n/2)^2) + n^2 = cn^2- bn^2 + n^2 $

However, there is no way to solve $cn^2- bn^2 + n^2 \leq cn^2 - bn^2 $ for $b$

If you're using the same book I have (Introduction to Algorithms 3rd edition), then you mis-wrote the question. The relation in question should be: $T(n)=4T(n/2) + n.$

That said, substitution here won't work, as you know.  Assuming $T(n) \le cn^2,$
you get:

$T(n)\le4T(n/2) + n$

$T(n)\le4(c\frac{n^2}{4}) + n$

$T(n)\le cn^2 + n$

Which doesn't imply  $T(n) < cn^2.$ Instead, you can make the assumption: $T(n) \le cn^2 - bn.$

$T(n)\le4T(n/2) + n$

$T(n)\le4(c\frac{n^2}{4}-b\frac{n}{2}) + n$

$T(n)\le cn^2 + n(-2b + 1)$

Letting $b=1,$ you get an equation consistent with the initial asumption. Namely:

$T(n)\le cn^2 - n$

As a side note, the relation you initially wrote, $T(n)=4T(n/2) + n^2,$ can be solved using case 2 of Master's Theorem, and has an answer of $\Theta(n^2lg(n))$


Using Context free language to simulate regular expression in finite automata Is there a minimum number of non terminal we need to use in order to simulate a finite automata with n states? When we try to convert a language accepted by NFA to context free language, do we need n number of non-terminal to store n states in the NFA?

No such non-trivial bound can be obtained. Consider the language $L_n = \{ 0^{kn} : k \in \mathbb{N}\}$. Any NFA for $L_n$ needs at least $n$ states, but it can be generated by a context-free grammar with only one non-terminal: $S\to 0^nS|\epsilon$.


Using Funk SVD with SGD? I work on a recommender system framework which is implemented with a variant on Funk SVD (See his explanation of his algorithm here).

However the framework that we are trying to integrate doesn't support Funk SVD, only SGD (Stochastic Gradient Descent).

Since shouldn't these be compatible? In other words, I should be able to create the U and V matrices with SGD and then treat them like they were made via the Funk SVD process?

Are there any disadvantages of using this versus the algorithm detailed by Funk?

simon funk is the apparent inventor of a simple & ingenious SVD (singular value decomposition) algorithm during the netflix contest although the algorithm may have predated his discovery (would like to know a ref if anyone knows). SGD = stochastic gradient descent (?) which can be applied to all kinds of optimization problems, incl SVD.

so it depends on your recommender system framework and if its trying to use SVD for recommendations, which is common, but not universal. if it is using SGD to compute the SVD, then that is very similar to the Funk algorithm except the Funk algorithm is probably more prone to get stuck in local minima.

in other words the SGD may find a superior solution but it may take longer. so basically both SGD/Funk are two approaches to computing the U,V matrices & you can do experimental testing to see which gives you the best results or desirable performance.

Funks algorithm is basically just straight gradient descent and SGD is stochastic gradient descent that adds a simulated annealing-like approach to the optimization where earlier in the convergence/search, weights are randomly perturbed to avoid local minima, and then as the search progresses & hopefully converges, the perturbation factor decreases.

fyi for SVD it can be possible to find the optimal solution using matrix based methods even for large matrices (esp if large distributed resources are available) and one could possibly compare either the Funk algorithm or SGD to the actual global optimum.


Finding number of numbers dividing n^m exactly p times Suppose I am given a number $n$ (less than $10^8$) and $m$ (less than $10^7$) and $p$ (less than $10^4$), I have to write a program to find number of numbers that divide $n^m$ exactly $p$ times.

Mathematically, I have to find number of distinct $x$ such that
$$ n^m \equiv 0 \mod x^p \qquad\text{and}\qquad n^m \ne 0 \mod x^{p+1} $$

(From UVa Online Judge)

What approach could be better than brute force?

Start by factoring $n$ (you can use a table of all primes of size at most $1e4$). Now you can write $n^m = \prod_i p_i^{c_i}$. Now come up with a criterion for $x = \prod p_i^{a_i}$ to divide $n^m$ exactly $p$ times, and use this criterion to answer your question.


Calculate the average Big O from a function? I was given this function: $T(N) = 3N\log^2 N + 5N^2\log N + \log N + 17N + 2$ and was asked to find the average Big O complexity.

If the Big(O) deals with an upper bound, would this algorithm be $O(N^2\log N)$ on average? But, because Big O is an upper bound, couldn't this also be $O(N^3)$, $O(N^4)$, etc.? Basically, is there a difference between Big O complexity and average Big O complexity of an algorithm?

Strictly speaking, there are no such things as "Big O complexity" or "average Big O complexity". Look at the definition of Big Oh and you can stop guessing.

The right mindset is that you can analyze whatever aspect (say, the number of steps taken by an algorithm) in some case you care about (say, in the worst case, however you define it). You write a function $f$ of the input size $n$ that captures this. You do not need to know anything at all about asymptotic analysis up to this point. Now you can look at the definition of Big Oh again, and express $f(n)$ as the Big Oh of something.

With that being said, I think the questioner should clarify the meaning of "average Big O complexity". Concepts should not be intuitive and come out of thin air, but have precise definitions.


Understanding basic operation of TM and FA As turing machine always halts on dead configuration,so consider the  case where it halts in final state,if on second last state by reading an input alphabet it comes to final state. Now in final state it will try to find the transition for the next symbol(i.e blank) and as there will be no transition on final state so machine will halt/dead in final and we can say string is accepted.

If i consider the case of Finite automate,now FA reaches the final state and the next is blank then we say machine will stop and string is accepted.But this is not dead configuration.

But in both cases the input is coming from tape and in case of FA ,it will halt when blank comes on tape and there is no dead configuration.But same behaviour in TM is having dead configuration behaviour.

Can someone please explain the difference in these two case from point of dead configuration.?

P.S:- By dead configuration,i mean that transition on the state is not defined for given alphabet

Turing machines (and RAM machines) and (most) finite automata operate in two different input models. Finite automata usually accept their input in a streaming fashion: they read one input symbol, do something, read another input symbol, do something, and so on. When the input is exhausted, they report their output. Turing machines, in contrast, get all their input on the input tape, and then do whatever processing they wish. They don't have to stop after they have scanned the entire input.

This difference in the input model explains the different semantics you have indicated. There are, however, finite automata which have input semantics similar to a Turing machine, namely two-way finite automata. Although behaving superficially like Turing machines, they are equivalent in power to deterministic finite automata (DFAs).


If a thread containing main terminates, can another thread do anything? I'm studying threads in C and I have this theoretical question in mind that is driving me crazy.
Assume the following code:

1) void main() {
2)     createThread(...); // create a new thread that does "something"
3) }

After line 2 is executed, two paths of execution are created. However I believe that immediately after line 2 is executed then it doesn't even matter what the new thread does, which was created at line 2, because the original thread that executed line 2 will end the entire program at its next instruction. Am I wrong? is there any chance the original thread gets suspended somehow and the new thread get its chance to do something (assume the code as is, no sync between threads or join operations are performed)

While the details will depend on the actual thread model of your thread library (eg. pthreads, the POSIX thread library), some general observations hold.

Without explicit or implied syncing you have no guarantees about the serialization of threaded code. The platform running your code might execute some of the thread's code first before resuming the spawning (main) thread of the process.
The thread-creating code of your program itself is just a thread - it does not need to be distinguished from any thread it creates.
Automatic program termination after a thread ends will be most inconvenient in most settings (Imagine a multi-threaded program where one thread enters a non-recoverable error state while another thread performs a backup job). So while the code/language may lack overt syncing primitives, usually there still exist mechanisms to allow for a controlled thread termination.


Computation of normalized first derivative in discrete case I am reading a paper on recognition of online handwritten characters. One of the features proposed in the paper is "normalized first derivatives, $(\hat{x}'_t,\hat{y}'_t)$", which they have defined as follows:

$$
\hat{x}'_t=\frac{x'_t}{\sqrt{(x'_t)^2+(y'_t)^2}}\quad\quad
\hat{y}'_t=\frac{y'_t}{\sqrt{(x'_t)^2+(y'_t)^2}}\,,
$$
where

$$
x'_t=\frac{\sum_{i=1}^2i(x_{t+i}-x_{t-i})}{2\sum_{i=1}^{2}i^2}\quad\quad
y'_t=\frac{\sum_{i=1}^2i(y_{t+i}-y_{t-i})}{2\sum_{i=1}^{2}i^2}$$
I have couple of doubts with respect to these definitions:

If the derivatives are to be normalized, what is the significance of the denominators in the definition of $x'_t$ and $y'_t$?
Why is the difference scaled by $i$ in the numerator? What I understand is that this scaling gives more weight to the points farther from the central point.

For the first part of your question, the significance is just to guarantee that the vector $(\hat{x}'_t,\hat{y}'_t)$ has length $1$. This means that it tells us in which direction $(x_t,y_t)$ is changing, but not by how much. For example, $(\hat{x}'_t,\hat{y}'_t)=(1,0)$ tells us that $x_t$ is increasing and $y_t$ is constant; $(\hat{x}'_t,\hat{y}'_t) = (-\sqrt{2}/2, \sqrt{2}/2)$ tells us that $x_t$ is decreasing, and $y_t$ is increasing at the same rate.

The second part isn't something I know about, so I'll leave that for somebody else.


Good beginner source to learn about how computers work I am a senior year high school student. I love programming and my chosen language is Java. I'm very much into high-level programming and Object Oriented design.

Recently, I started to show first interest in the low-level side of things. Especially the most basic level of how computers work (the more theoretical level, not the hardware side).

For example, how computers make basic calculations has always been a mystery to me. How is it that a computer can even come up with the result for 5 + 2? (As a kid I used to think that every computer stores the answers for all of the possible calculations.. lol)

I am also interested in the most basic level of how computers, well, generally do things internally. Again, at the most basic and fundamental level.

As you can see it's hard for me to phrase what I'm interested in learning, probably because I know almost nothing in computer science. But I hope you get the idea.

Could you direct me to a good source that I can learn from - at the most beginner level - this kind of knowledge? (A website or a book [preferably a website]).

Thanks

What I have got for you is :

Computer  Systems - A  Programmers Perspective
Computer Organization and Design
The Elements of Computer System
The Pattern on the Stone (Misleading title)
Code - The Hidden Language of Computer Hardware and Software

These books should help you understand how computer works. A bit knowledge of computer hardware is a must and it will surely speed up your learning process.


Given a sorted array $A$, how can it be efficiently determined whether $\exists i . A[i] = i$? Given an array $A$ of integers in ascending order, how efficiently can it be decided whether there exists an integer $i$ such that $A[i] = i$? How would an optimal algorithm for this problem work?

It can be done in $O(\log~n)$ for a $n$ element array $A$ by using a slightly modified version of binary search. This is possible because you stated that the input array is made of increasing integers and is therefore sorted. It does not matter what kind of integers your input actually contains: the integers may be negative, zero or positive as long as the array is sorted.

Your search for an index $i$ such that $A[i] = i$ is of course equivalent to searching for an index $i$ such that $A[i] - i = 0$ and the function $f(i) = A[i] - i$ is monotonically increasing so that the problem reduces to finding, if it exists, one point $i$ where the function value is zero. It follows that you are guaranteed that if a check fails you only have to explore one subarray, which leads to $O(\log~n)$ in the worst case.

Your algorithm starts by checking the middle element as usual. If the check succeeds (A[middle] - middle = 0), you have found the index you are searching for. If $A[middle] - middle < 0$, then you need to check the right subarray; otherwise ($A[middle] - middle > 0$), you have to check the left subarray.


How to calculate O-Notation? I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand;
What I would like to ask, if there is a certain way to find out O-Notation? Actually I know that the purpose of O-Notation, it helps us to estimate the effciency of algorithm. But in a specific questions like O(2^n) * O(n^10) I assumed that O(2^n * n^10) as in the worst case but learned that I was false, it should be 2^n and I don't know why? Shouldn't we think that which term would go faster to eternity, and in this case I thought that when I multiply both then it can go faster than 2^n, can't it? Could anyone explain please ? Just short and with beginner sight:)

We can show that $O(2^n\cdot n^{10}) \not\subset O(2^n)$:
As $2^n\cdot n^{10} \in O(2^n\cdot n^{10})$, then, if also holds $2^n\cdot n^{10} \in O(2^n)$ then we will have $2^n\cdot n^{10} \leqslant C 2^n$, which gives false $n^{10} \leqslant C$.


Reconstruction of drawing sequence from video I have a video that record the drawing sequence with a pencil by a painter.

I want to reconstruction the sequence from the video.
And I have google some keywords like "drawing sequence reconstruction", "sketch reconstruction", and have searched like "moving object detection" but cannot found what I want to find.

I want to know how to detect and recognize the drawing between different frames. I have thought the "line detect" algorithm may work but fail. And pixel comparison seems to be bad idea. Because that the new drawing may overlap the old ones.

Could you give me some information that I can read or some keywords to search? Sorry about that because I am not familiar with Computer Image Processing.

You should have a look at background segmentation algorithms. The hand is moving over the rather static drawing. One very simple approach would be to store the last N images and compute the variance of the color for each pixel. The pixels with a low variance will be your painting (and the canvas you draw an) so a subsequent thresholding should seperate the drawing from the canvas.


residual graph and augmenting path in max flow I thought I understood max flow perfectly until I got to the exam and we got this. I know how to compute a maximum flow by means of the Ford-Fulkerson algorithm, specify the residual network and augmenting path. But here they gave us a graph where some of the capacities were already full (if you can tell from the picture) and I couldn't find a new augmenting path. Is there another way to solve this?

A full edge, e.g. $a \rightarrow c$, has a residual capacity of $0$ in the residual network. So you can't make an augmenting path over that directed edge.
However the reversed edge, $c \rightarrow a$ has a residual capacity of $5$ (since $c_{c \rightarrow a} = 0$ and $f_{c \rightarrow a} = -5$). Therefore you can create an augmenting path using the reversed edge.
The residual network would be:

E.g. a possible augmenting path would be $s \rightarrow c \rightarrow a \rightarrow d \rightarrow t$. You can increase the flow along that path by 5 and get the following flow network:

This is also the maximal flow, since $\{s, c\} - \{a, b, d, t\}$ forms a saturated s-t-cut.


Validity of this formula in WS1S logic The following formulas are said to be defined in WS1S logic.

$Closed(Z, R) := ∀x ∀y(x ∈ Z ∧ R(x, y) → y ∈ Z)$
$(z_1, z_2) ∈ R^∗
:= ∀Z.(z_1 ∈ Z ∧ Closed(Z, R) → z_2 ∈ Z)$

However since WS1S formula requires bounded second order variables to be finite, I am not sure if the second formula is valid. $Z$ which is bounded here, can be an infinite subset of natural numbers. For example, when $R$ is a $succ$ relation.

There are no restrictions on $R$ stated in the reference.

In the paper Implementing WS1S via Finite Automata by James Glenn and William Gasarch :
$∀X∃Y ∀z(¬(z ∈ X) ∨ (z + 1 ∈ Y ))$ is stated to be a valid WS1S formula.
$∀x∃y(y < x)$ is stated as an invalid WS1S formula.

However if $X$ is finite in the first formula, $Y$ is infinite and hence I think this should not be a valid formula. In the second formula there are no second order variables and therefore it should be a valid formula. Please let me know what am I missing here.

The confusion comes mainly from different meanings of validity.

In the context of syntax, we are used to understand 'valid' as syntactically correct. As in '42["Hello world"] is a valid C expression'. I believe this is also how you understood Glenn&Gasarch. Their statement does make sense with semantic instead of syntactic validity.

Let me shortly recap semantics of WS1S. Generally, in second-order logic (weak or non-weak), the semantic of a formula is defined relative to an interpretation. The interpretation defines the meaning of all symbols. It consists of a structure and an assignment. The structure defines the universe and the meaning of the symbols from the base vocabulary. The assignment defines the meaning of the free variables. For a formula $\varphi$ and an interpretation $\mathcal I$, the semantics define whether $\mathcal I\models\varphi$ shall hold.

In WS1S, the structure is fixed: The universe is the natural numbers and the only other symbol is interpreted by the successor relation. Hence, for formulae $\varphi$ without free variables (sentences), the semantics can do without mentioning the interpretation. That could be written just $\models\varphi$, or $\models_{\text{WS1S}}\varphi$. And that is what Glenn&Gasarch mean with validity.

Let me stress that the finite-subset restriction of WS1S is not a syntactic one. The syntax of WS1S is the same as that of S1S (which has quantification over arbitrary subsets). Hence syntactic validity (well-formedness) is not jeopardized by concerns of what can or cannot be achieved with a finite subset. Indeed the only difference between WS1S and S1S is of semantic nature. By definition, $\mathcal I\models \exists X\varphi$ holds

(in case of S1S) if there is a subset $S$ of the universe such that $\mathcal I[\frac SX]\models\varphi$, or
(in case of WS1S) if there is a finite subset $S$ of the universe such that $\mathcal I[\frac SX]\models\varphi$.

Now to the other two formulae you asked about. Both are syntactically valid, if you allow binary second-order variables ($R$ in this case) as arguments (which is fine for defining subformulae as building blocks; in the end these variables will have to be substituted by other formulae). As they have free variables, we cannot say anything about semantic validity without having an assignment.

However, the names of the formulae suggest intended semantics. And we can compare the actual semantics to the intended ones.

The first formula holds (in the sense of $\models$) iff the set which is assigned to $Z$ is closed to the right under the relation assigned to $R$. That does seem to match the intention.
The second formula holds iff the element assigned to $z_2$ is reachable from the element assigned to $z_1$ by a path all of whose steps belong to the relation assigned to $R$, or if infinitely many elements are reachable in that way. That does not seem to match the intention.

But again, I would not use the notion of validity to discuss whether a formula fulfills its purpose.


Range of each building in array I have two arrays, X and H, where X is sorted. X[i] represents the coordinate of building i. Y[i] represents the height of building i. If building i collapses, all buildings in the interval [ X[i]+1, X[i]+H[i] ], both ends inclusive, will collapse, too. Those collapsed building may cause more buildings to collapse and so on, just like a domino effect. For each building, we want to find its range of effect, represented by the largest coordinate that will be affected.

Example

X = {5 6 9 11}

H = {2 3 1  5}

ans = {10 10 10 16}

Explanation: the collapse of building 0 will cause building 1 to collapse since 6 is in [5+1, 5+2]. The collapse of building 1 will cause building 2 to collapse since 9 is in [6+1, 6+3]. Finally, building 2 will affect [9+1, 9+1], which does not contain 11, the coordinate of building 3. So the range for building 0, 1 or 2 is 9+1=10. The range of building 3 is 11+5=16.

There is a $O(|X|)$ algorithm for this problem using a stack.

Algorithmic details:

For a building $i\in \{1, ..., n\}$, we will be pushing $i$ onto the stack $S$. For building $i$, let $X_i$ be its coordinate, $H_i$ be its height and $R_i$ be its range.
While iterating over the data (i.e. $i = 1 ... n$), we maintain the loop invariant that $S$ will only contain indices $j$ such that $R_j \ge X_i$ at the end of $i$-th iteration.
The loop invariant implies that for buildings $k$ and $k'$, where $k<k'$, which are next to each other in $S$, we have $R_k=\max(X[k]+H[k], R_{k'})$.
At the start of $i$-th iteration, to maintain the loop-invariant, we must pop all indices $j$ from top of $S$ such that $R_j \lt X[i]$.
The loop invariant also forces us to push $i$ on top of $S$ at the end of $i$-th iteration.
(Edit) Running time will be $O(|X|)$ because each $X_i$ gets pushed on to the stack $S$ (and subsequently popped off) only once for each $i \in \{1,...,n\}$. And we need not do more than $O(1)$ work with each operation on $S$.
(Edit) Space complexity will be $O(|X|)$. Observe the case where $X=\{1,2,3,...,n\}$ and $H=\{n,n-1,n-2,...,1\}$ for some $n\in \mathbb{N}$. That is, pushes onto the stack will happen before any pops.

Insight:

Think about maximal sets of buildings (not necessarily contiguous) where if one falls, then all the ones on its right within the same set will fall too. Now if we look at lowest and highest indices of buildings in such a set as endpoints of an interval, then intervals are either contained within one another or they don't overlap at all. That is, there is always at least one set of contiguous buildings. If this set is removed from the list of buildings, another set will now have contiguous buildings.

Code (Python 3.x):

import random

MAX_RANGE = 2**32

#implementation of the explained O(|X|) algorithm
def building_dominoes(X, H):
    ''' For building i, we store (i, X[i] + H[i]) on the stack
        to simplify some aspects of the implementation. Same is
        the reason for using MAX_RANGE. These can be done away
        with easily.
    '''

    s, result, rang = [], [0]*len(X), 0

    for i in range(len(X)):
        clear_stack(s, X[i], result)
        s.append((i, X[i] + H[i]))

    clear_stack(s, MAX_RANGE + 1, result)

    return result

def clear_stack(s, x, result):
    range_max = 0
    while s and s[-1][1] < x:
        j, new_range = s.pop()
        result[j] = range_max = max(range_max, new_range)

# brute-force version
def brute_force(X, H):
    n = len(X)
    res = [0] * n
    for i in range(n-1, -1, -1):
        res[i] = max([X[i] + H[i]] + [res[j] for j in range(i+1, n) if X[j] <= X[i] + H[i]])
    return res

# small set of tests
META_X = [
    [5, 6, 9, 11],
    [0, 1],
    [1, 2, 3, 4, 5],
    [1, 2, 3, 4, 5],
    [1, 2, 3, 6, 8, 10],
]
META_H = [
    [2, 3, 1, 5],
    [9, 1],
    [2, 4, 6, 8, 10],
    [10, 8, 6, 4, 2],
    [8, 3, 1, 2, 1, 1],
]

success = 0
for i in range(len(META_X)):
    if building_dominoes(META_X[i], META_H[i]) == brute_force(META_X[i], META_H[i]):
        success += 1
print(f"Passed {success} tests from the specified set of {len(META_X)} tests.")

# randomized tests
VALS = list(range(100000))
MIN_N, MAX_N = 10, 500
NUM_TESTS = 500
success = 0
for i in range(NUM_TESTS):
    size = random.randint(MIN_N, MAX_N + 1)
    X = sorted([random.choice(VALS) for _ in range(size)])
    H = [random.choice(VALS) for _ in range(size)]
    if building_dominoes(X, H) == brute_force(X, H):
        success += 1
print(f"Passed {success} tests from the set of {NUM_TESTS} randomized tests.")


Logarithmic reduction to another LOGSPACE problem For words of the same length $u = u_1..u_n, v = v_1..v_n$ over an alphabet $A$ let $$u \circ v = u_1v_1...u_nv_n$$

Prove that if $L$ over $A \times A$ in in LOGSPACE then $$L' = \{uv : u \circ v \in L\}$$
is also in LOGSPACE

My solution:
We try to log-reduce $L'$ to $L$. So, I mean when a machine $M_L$ tries to read an input then reducing function $f$ gives another input.

Let $I$ be an input tape, word $w = uv = u_1..u_nv_1..v_n, |w| = 2n$ and $w$ starts at 0th cell.

Now, we define $f$:
$$
      f(i) = \left\{\begin{array}{lr}
        I[i/2] & \text{for } i \ even \\
        I[i/2+n] & \text{for } i \ odd
        \end{array}\right]
  $$

My doubts:

Is it ok?
I used in $f$ division. Is is possible in $LOGSPACE$?

You are asking two questions. I will only answer the one about division. Division can be done in logspace, as shown in this answer, which cites the relevant literature.

However, in your case you are interested in division by 2, which is easier than general division. I bet you can show yourself that numbers can be divided by 2 in logspace (assuming that they're represented in binary). This operation is known as right shift.


HMM tagger - Baum Welch training I am trying to implement a trigram HMM tagger for a language that has over 1000 tags. In my training data I have 459 tags. Now if we consider that states of the HMM are all possible bigrams of tags, that would leave us with $459^2$ states and $(459^2)^2$ transitions between them, which would require a massive amount of memory.

Are there any workarounds around this?
What I thought of is considering only bigrams seen in the data, but it is still a lot of memory.

Actually, there are only $459^3$ transitions, not $459^4$ transitions.  That helps a lot.  This is because a state is a pair $(t,u)$ where $t,u$ are tags, and a transition has the form $(t,u)\to (u,v)$.  In particular, you can't have $(t,u) \to (w,x)$ where $u \ne w$ (given that the state represents the last two tags).  So, there are at most $459^3$ transitions, or at most about 100 million transitions.  You should be able to store that a graph with 100 million edges in memory without too much difficulty.

My guess would be that not all transitions actually occur in the training set, so it's possible this might be a sparse graph, and that might reduce the graph size further.


What real-world computer languages cannot be described by deterministic grammars? Are there any examples of real-world computer languages that are non-deterministic?

By computer languages I include programming languages, markup languages, query languages, modeling language, transformation languages, etc.

By non-deterministic I mean they cannot be parsed with deterministic grammars.

Yes.  Many modern programming languages have this property, including Algol 60, C, and C++; see below for details.

Algol 60 famously had the dangling else problem, for some programs, it was ambiguous how they should be parsed (what parse tree should be result).

Many modern languages resolve this by picking a grammar that resolves the ambiguity in a particular way.  However, this requires carefully constructing the grammar to eliminate ambiguity.  Often the most natural way to write the grammar leads to a grammar that is ambiguous, and you have to transform the grammar to avoid the ambiguity.

Another approach is to use a GLR parser, which can handle these grammars.  Then you can check at runtime whether there are multiple possible parsers, and resolve the ambiguity.

Another classic example is the C and C++ programming languages.  The reference grammar for C is not context-free, because when you see a name, you need to know whether it is the name of a type or of a variable to know how to parse the statement.  For instance, consider the expression

(A)*B

If A is a variable, this is the multiplication of two variables and is equivalent to A*B.  However, if A is the name of a type, then this is a pointer dereference and type-cast (so B is a variable name that holds a pointer type), and equivalent to (A) *B.

Similarly,

A*B;

could be either a variable declaration (if A is the name of a type, this is declaring a variable named B whose type is pointer-to-A) or a multiplication (if A and B are the names of variables).

Compilers typically fix this by including extra code that "goes outside" the language of pure context-free grammars.  They keep track of all variable names and type names in scope, and use this to guide parsing in case of this ambiguity.  See the lexer hack.

See also LL and LR in Context: Why Parsing Tools Are Hard and Bison's manual pages on its GLR parser (which includes a discussion of another ambiguous case in the C++ grammar).

Lastly: I think the question has some confusion about the difference between ambiguity vs non-determinism.  Automata and languages can be deterministic/non-deterministic, but not grammars.  Grammars and languages can be ambiguous/unambiguous.   See Are there inherently ambiguous and deterministic context-free languages? and Grammatical characterization of deterministic context-free languages and If a parser can parse a non-deterministic grammar, is the parser non-deterministic?.  The above examples actually qualify both as ambiguous grammars and non-deterministic languages.


$P/Poly \setminus P$. What langugage does reside there? What language is in $P/Poly \setminus P$? I was thinking of it by hours but I cannot come with an idea. Please help.

One example is the language
$$\{ 1^n : \text{the $n$th Turing machine halts on the empty input}\}.$$
This language has constant size circuits, but isn't computable.


Would a modern processor/ALU process data bit or byte wise? We look at 32 bit and 64 bit systems with octal-core processors.
What does all that mean? As in, does it have 8 processors that operate bit wise?
Or do they all operate on 32/64 bit blocks.
I was studying Crypto with stream and block ciphers. And this has been confusing me now.
Also, is it fair to say that a computer has no value for "bytes" as there aren't anything more than our way of grouping bits to make them more convenient to read?

Modern processors have 32/64 bits integer and 32/64/80 bits floating-point registers and ALUs. With the addition of SIMD instructions, extra vectorized ALUs are available and can perform operation on up to 64 bytes or 32 shorts (16 bits) or 16 ints (32 bits) or 8 long ints (64 bits) simultaneously and similar figures in floating-point (hence 512 bits at a time - Intel AVX).

A core is a full processing unit packaged in the same physical (multi-)processor.

So in a way, you can say that an octo-core can process 4096 bits of data at a time.

It is not fair to say that a processor ignores bytes, because the arithmetic operations need to know how many useful bits there are, to handle borrows, carries, overflows... Not to mention the floating-point data types, such that the value is split in several bit fields with different roles (sign, exponent, mantissa). In fact, a processor distinguishes dozens of data types of various lenghts.

It would be more true to say that processors don't known about bits because these are never handled individually, but as a minimum grouped in bytes. Even the very first microprocessor in history, the 4004, was handling nibbles (4 bits at a time).


Data hazard or forward in MIPS SW after LW in this case? so we know data hazards may occur on data that is not ready yet and we can solve them by forwarding data in between the pipes.

Look at this piece of code:

lw $6, -16($6)
sw $6, -16($5)

So the sw wants the data that comes from the MEM read and it wants it just for the MEM write. So we can use a bypass to forward the output of the MEM to the input of the MEM (in the data write input) and this is solving the hazard without a bubble (nop).

Is it implemented into the MIPS core and if not, what will it do?

It is unclear to me if you ask about the "real" MIPS chips, or about the simplified educational version one sees in class.

If you mean the former, then I would guess it does. Well, the CPU probably has way more steps in its pipeline, caches, and tons of other fancy machinery, but I think it is safe to assume that any valid code will run correctly on it.

As for the simplified 5-step pipelined MIPS: again, it depends on which version you refer to. Certain books have load-hazard circuits which are supposed to take care of most situations. But if you have a drawing of the circuits I guess you will be able to tell by yourself if forwarding units exist or not.

The moral is - the MIPS must run correctly any piece of code. If the code you present causes a hazard, then the MIPS hardware must$^*$ deal with it somehow. In most classes that teach MIPS they leave some parts off so maybe you saw a partial design that doesn't take care of it. If you have a specific version in hand, you can check.

$^*$Well, if the MIPS hardware doesn't take care of this, then the programmer (i.e., the compiler) must take care of it. This is less desirable.


How do you express the theorem statement about unsuccessful search on average-case for unsuccessful searches in hashing with quantifiers? I was reading CLRS and in theorem 11.1 it states:

  In a hash table in which collisions are resolved by chaining, an unsuccessful search takes average-case time $\Theta( 1 + \alpha )$, under the assumption of simple uniform hashing.

I was trying to understand how to express this theorem with quantifiers ($\exists, \forall$) and how it relates to "average-case" time (precisely, what they mean with average case time).

Is the theorem a statement that holds for all or any key? Or does it hold for all key on average and what does "on average" mean rigorously?

Usually, I like separating the terms expectation and average because the have different meanings. Expectation usually I think of it as the expected value of something according to some underlying distribution. For Average I think of the average value given a sample. So with these in mind, is the "average-case" scenario the same as the average running time for any key? i.e. Let $T_k$ denote the amount of time to search of a key $k$. This is a random quantity because it depends on the key we search for. Define the average-case runtime for any search to be $Search = \sum^n_{k=1} T_k$. Is the theorem statement in CLRS statement about the random variable $Search$ I just defined? (Which takes into account all keys at once and hence, applied for "any key" I guess). Or what do they mean by average-case precisely?

There are two prominent uses of the term "average" in algorithm analysis.

Average-case as a special case of expected costs

Here, "average case" just means "expected case w.r.t. uniform distribution". Since we usually analyse with uniform inputs in mind (everything else is hard, and there's not much reason to prefer one distribution over the other in most cases).

Example: the average-case running-time cost of sorting algorithms
is often analyzed w.r.t uniformly-random permutations.
Average cost in the classic sense.

When analyzing data structures, we can look at average costs across
the contained elements for a fixed instance -- no probability
distribution here (well, you could...).
That is, we may still have/want to consider a worst-, average- or
best-case instance.

Example: Consider BSTs. The average search cost of a given tree is
the total cost for searching all contained elements (one after the other)
divided by the number of contained elements. This is a classic quantity
in AofA called internal path length.

Note: There are situations where average and expected do not usually mean the same thing. For instance, the expected (also: average-case) height of BSTs is in $O(\log n)$ but the average height is in $\Theta(\sqrt{n})$. That is because "expected" is implicitly (by tradition) meant w.r.t. uniformly-random permutations of insertion operations whereas "average" means the average over all BSTs of a given size. The two distributions are not the same, and apparently significantly so!

Recommendation: Whenever you use "expected" or "average-case", be very clear about which quantities are random w.r.t. which distribution.

The specific sentence you quote is indeed not clear if read in isolation -- if you ignore that CLRS specify exactly what "simple uniform hashing" means on the very same page.

There are two potentially random variables here: 1) the content of the hashtable itself, and 2) the key searched for. Simple uniform hashing is a simple way of specifying both.

We abstract from sequences of insertions¹ and just assume that every one of the $n$ elements we inserted independently hashed to each of the $m$ addresses with probability $1/m$.
We assume that the searched key hashes to each address with probabilty $1/m$.

That's how the proof works: our search hits each list with probability $1/m$ (cf 2), and they all have the same expected length of $n/m$ (via 1). Hence, the expected cost (under this specific model) for searching for $x$ not in the table is proportional to

$\qquad\displaystyle\begin{align*}
  T_u(x,n,m) &= 1 + \sum_{i=1}^m \operatorname{Pr}[h(x) = i] \cdot \mathbb{E}[\operatorname{length}(T[i])] \\
              &\overset{1,2}{=} 1 +\sum_{i=1}^m \frac{1}{m} \cdot \frac{n}{m} \\
              &= 1 + \frac{n}{m}.
\end{align*}$

The "$+1$" is there to account for computing $h(x)$ and accessing $T[h(x)]$, the sum represents the cost for searching along the list.

That is fair since the sequence of insertions does not have as much impact on the resulting structure as for, say, BSTs. The hash function shakes everything up. We don't want to talk about the precise interaction of sequence and hash function, so we just assume that the result of both is independently uniform -- that's something we can work with. It may not represent reality, of course!


What is wrong with this reduction from vertex cover to binary programming? I am trying to polynomial-time reduce the decision version of vertex cover to the decision version of binary programming.  Here are the problem statements.

Vertex Cover Decision Problem

Instance: A graph $G=(V,E)$ and an integer $k$.

Question: Does $G$ have a vertex cover of size at most $k$?

Binary Programming Decision Problem

Instance: An integer $m \times n$ matrix $A$, an integer $m$-vector $b$, and an integer $l$.

Question: Is there a a 0-1 $n$-vector $x$ with at most $l$ 1's such that $Ax \geq b$?  Here $||x||_1= \sum_{i=1}^{n}x_i$.

I found a supposed transformation here that makes $A$ an $|E| \times |V|$ matrix, where $a_{e,v}=1$ if edge $e$ is incident on vertex $v$ and $0$ otherwise.  It also sets $b$ to an all 1's vector and $l=k$.

This transformation works in one direction: if you have a vertex cover you can build $x$ by letting $x_v=1$ if vertex $v$ is included in the vertex cover and $0$ otherwise.  However, in the other direction I can easily create an example where $Ax \geq b$ but the 1's in $x$ do not create a vertex cover in the induced graph.  Can anyone provide a hint as to how to correct this?

Your example does not hold since the first entry of $Ax$, 0 is smaller than 1, the first entry of $b$.

$$
\begin{array}{c c c}
&Ax &  &b\\
& \begin{bmatrix}0 \\1 \\2 \\1 \\1\end{bmatrix}
& \not\ge\
& \begin{bmatrix}1 \\1 \\1 \\1 \\1 \\\end{bmatrix}
\end{array}
$$

Please note the condition $Ax\ge b$ means every entry in $Ax$ is no less than the corresponding entry in $b$. In term of the corresponding problem, the vertex cover problem, it means every edge is incident to at least 1 vertex. It is not about the $L_1$ norm; otherwise, it should be written as, for example,  $||Ax||_1\ge ||b||_1$.

Yes, we want to minimize the number of 1's in $x$, which is the same as minimizing $||x||_1$. However, the condition $Ax\ge b$ is a requirement on $x$. The requirements on the variable that are usually read as "subject to ..." and the objective function could be seen as irrelevant or independent to each other.


Uniquely identifying bits Query: Given $m$ unique integers smaller than $2^n$, can we keep at most $k$ the same bits of each number to uniquely identify them?

Is this problem NP-Hard?

For example, given the $4$ unique numbers smaller than $2^3$

011
100
101
110
 ^^

The numbers are still unique if we remove the leftmost bit from each number. So for $k = 2$, the answer is yes: we keep bits {0, 1} (the rightmost bit is here defined as the bit with index 0).

I want to solve the above problem as a precomputation step for integers less than 20 bits, so for my application an exponential algorithms could be allowed. Then it would be great to minimize $k$ and then break ties in such a way that the number of gaps between the indices that are kept is minimized. For example, {0, 1, 2, 5, 7} has two gaps: between 2 and 5 and between 5 and 7. This precomputation should lead to a great hash function for a set of integers. In my application the sets of integers don't change later.

Your problem is NP-hard. To see this, you can reduce it from the minimum test cover (or test collection) problem: given a set $X$ of $\ell$ elements and a collection $C = \{C_1, \dots, C_k \}$ of $k$ subsets of $X$, find a minimum test cover for $X$ and $C$, i.e., a subset $C'$ of $C$ that has minimum size and satisfies the following property: for every pair of distinct elements $i,j \in X$ there is a set in $C'$ that contains exactly one of $i$ and $j$.

The reduction is as follows: for each element $x \in X$ create a number of $k$ bits $b_1,\dots,b_k$ where $b_i = 1$ if and only if $x \in C_i$.
There is a test-cover $C' = \{ C_{i_1}, C_{i_2}, \dots \}$ if and only if the $|C'|$ bits in positions $i_1, i_2, \dots$ suffice to distinguish all input numbers.

Since the above reduction sets $m=\ell$, the measures for two corresponding solutions of test-cover and your problem coincide, and test cover is not approximable within a factor of $o(\log \ell)$, this also shows that your problem is $o(\log m)$-inapproximable.

On the bright side, the converse reduction works too: given an instance of your problem you can create an instance of minimum test cover by considering the set $X$ containing your $\ell = m$ input numbers $x_1, \dots, x_m$ and $C = \{C_1, \dots, C_k \}$ as a collection of $k = n$ sets where $C_i = \{ x \in X \mid \text{the $i$-th bit of $x$ is } 1 \}$. This means that the $O(\log \ell)$-approximation algorithm for minimum test-cover immediately translates to a $O(\log m)$-approximation algorithm for your problem.

See this paper and this paper.


What does machine code actually look like while being run? When machine code is actually being executed by hardware and the CPU, what does it look like?

Would it look like binary, as in instructions being represented by ones and zeros, or would it be something made up of hexadecimal digits where opcodes are bytes presented as hex numbers which can be broken back down into binary numbers, like bytecode?

The best answer I can give is, it doesn't really "look" like anything. The instruction currently being executed by the CPU is represented by a series of wires, some of which have a high voltage, some of which have a low voltage.

You can interpret the high and low voltages as zeroes and ones, but you can equally well interpret groups of high and low voltages as hexadecimal digits, or as an assembly instruction like ADD $0 $1 (which is closest to how the CPU interprets it). These numbers and mnemonics themselves are conveniences for humans to read; internally, it's nothing but voltages on wires.

Out of these options, binary is "closest to the metal", in that the zeroes and ones map directly to the high and low voltages on the wires. But none of the others are incorrect, and they're frequently more useful: there's a reason people look at hex-dumps of executables, but almost never binary-dumps.


Unique keys in a binary search tree I'm studying for my finals and I can across this statement.

"For a fixed set of (unique) keys, any binary search tree containing those keys can
be converted to any other BST on the same set of keys via a sequence of left- and/or right-
rotations."

I'm interested in a proof. Does anyone know any references?

Here's a short method of transforming a BST $T_1$ into any other BST $T_2$ on the same set of keys, taken from notes written by Doug Hogan at Penn State:

  Define the right spine of a BST as the root and all descendants of
  the root that are reachable by following only right pointers from the
  root. A right-linear chain is a BST that has all n nodes in the
  right spine.

  Let $T'$ be the (unique) right-linear chain of $n$ keys.  Let $r = (r_1, r_2, ..., r_k)$
  be a sequence of right rotations that transforms $T_1$
  into $T'$, and let $r' = (r'_1, r'_2, ...,r'_{k'})$ be a sequence of
  right rotations that transforms $T_2$ to $T'$.  We know there exist
  sequences $r$ and $r'$ with $k, k' \leq n-1$, since a right rotation
  adds exactly one node to the right spine.  For each right rotation
  $r'_i$ let $l'_i$ be the corresponding left rotation.  Then, the
  sequence $(r_1, r_2, ..., r_k,l'_{k'},l'_{k'-1}, ..., l'_2, l'_1)$
  transforms $T_1$ to $T_2$ in at most $2n-2$ rotations.

...and here's another explanation, which gives a nice recursive algorithm.

Google search terms: binary search tree transform rotation proof.


Read After Write(RAW) hazard I am confused in finding RAW dependencies whether we have to find only in adjacent instructions or non-adjacent also.

consider the following assembly code

I1: ADD R1 , R2, R2;

I2: ADD R3, R2, R1;

I3: SUB R4, R1 , R5;

I4: ADD R3, R3, R4;

FIND THE NUMBER OF READ AFTER WRITE(RAW) DEPENDENCIES IN THE Above Code.

I am getting 2 dependency  I2-I1 and I4-I3.

Adjacency is not relevant for determining Read-After-Write dependences.  You simply list all the instructions where one of the source registers reads the value produced by some previous instruction.

So (assuming that your assembly language is OPERATOR DEST SRC1 SRC2) you are missing, for example, that the first source operand of I3 dependends on the value written by I1.  (You are missing several others as well.)


Modify max value multiple times of a list I have two lists say $A$ and $B$, each consisting of n positive integers. I make a list $C$ such that each element of $C$ i.e., $C_i=A_iB_i$ for each element $A_i \in A$ and $B_i \in B$.

Now I have to update the value of the maximum element of $C$ say $C_j$ by decreasing $B_j$ such that $B_j \geq 0$ and $C_j$'s updated value should be less than the second maximum element of $C$.

The above operation have to be applied $m$-times.

The approach I used was:

Build a Max Heap of list C
repeat $m$-times

update the value of max element of heap according to the given condition
Apply Max-Heapify

The above approach worked fine. So my question is "Is there any way to do the above task in a faster way than my approach?"

One solution is changing the underlying data structure;

In the binary heaps, Decrease_Key is $\mathcal{O}(\log n)$ cost in the worst case. If you use Fibonacci heaps1, Decrease_Key is  $\mathcal{\Theta(1)}$ in amortized time. With the binary heaps, you will have $\mathcal{O}(m \log n)$ whereas in Fibonacci heaps you will have $\mathcal{\theta(m)}$ in amortized time.

note : Fibonacci Heaps are theoretically better than Binary Heaps. But their the constant factors hidden are very high.

1 Introduction To Algorithms 3rd. Ed. Cormen et. al. at section 19.


Interactive Proofs for coNP I am trying to understand interactive proof systems and tried the following problem as an exercise. We know that $PH \subseteq PSPACE$ and $IP=PSPACE$, so come up with (easy to understand) interactive proof systems for $PH$?

An interactive proof system for $NP$ is trivial, but I failed to get an interactive proof system even for $coNP$. Do you know of an explicit interactive proof system (by explicit I mean without going through the $IP=PSPACE$ route) for $coNP$?

Wikipedia outlines such an example. Consider the coNP-complete problem UNSAT: given a CNF $\varphi$ on $n$ variables, we want to convince the verifier that $\varphi$ is not satisfiable. We arithmetize $\varphi$ to a polynomial $p$ and choose some large prime $q$. Let
$$p(x_1,\ldots,x_k) = \sum_{x_{k+1}=0}^1 \cdots \sum_{x_n=0}^1 p(x_1,\ldots,x_n).$$
The protocol proceeds as follows:

Prover sends verifier a prime $q \in (2^n,2^{n+1})$, and the latter verifies that $q$ is prime.
Prover sends verifier $p(z) \in \mathbb{Z}_q[z]$. Verifier verifies that $p(0) + p(1) = 0$, and sends prover a random $r_1$.
Prover sends verifier $p(r_1,z) \in \mathbb{Z}_q[z]$. Verifier verifies that $p(r_1,0) + p(r_1,1) = p(r_1)$, and sends prover a random $r_2$.
Eventually, verifier gets $p(r_1,\ldots,r_n) \in \mathbb{Z}_q$, and verifies that it has the correct value by evaluating $p$ directly.

Because the degree of $p$ is small compared to $q$, if the prover is cheating then the verifier will probably catch her (see Wikipedia for the proof, or work it out yourself using the Schwartz-Zippel lemma).


Does this pushdown automaton describe the language {$a^n b^n c^i \in \{a,b,c\}^*\ |\ n \ge 0,i\ge 0$}? I've just been learning about pushdown automata and I'm trying to create one that describe the following language:

{$a^n b^n c^i \in \{a,b,c\}^*\ |\ n \ge 0,i\ge 0$}

What I have is the following:

(state, symbol, top of stack), (next state, what goes to stack).

$(s,$e$,$e$),(f,$e$)$

$(s,a,$e$),(s,d)$

$(f,b,d),(f,$e$)$

$(f,c,$e$),(f,$e$)$

Where $s$ is the starting state, $f$ is the final state and e is the empty word.

Do I have the right idea? My worry is sending the automata to the final state while there are still entries in the stack - is that allowed?

As I am (not) yet certain of the PDA model you are using, I will not comment on correctness of your construction, but I have a general remark on PDA.

There happen to be two generic ways of defining languages for PDA: by final state and by empty stack. Let a configuration be a description of the PDA, its (yet unprocessed) tape, state, stack.

Using final state acceptance means that we accept any word that leads from the initial configuration of the automaton to a configuration that is in a final state (no matter what is the contents of the stack) after reading the complete input.
Similarly, empty stack acceptance means that we accept any word that leads from the initial configuration of the automaton to a configuration in which the stack is empty (no matter what is the state) after reading the complete input.

By standard constructions one is able to change a PDA into an equivalent one using the other acceptance type. so for practical reasons the two notions are interchangeable. When dealing with technicalities (in case of deterministic automata for instance) the acceptance type does matter.

In conclusion: if you are using final state acceptance, then do not worry about remaining stack symbols.


What's the difference between dynamic and static pipelines? I was trying to understand what a reservation table is in the context of pipelining, when I found this reference here, where the author mentions that there are static and dynamic pipelines. According to him/her,

  There are two types of pipelines: static and dynamic. A static pipeline can perform only one function at a time, whereas a dynamic pipeline can perform more than one function at a time. A pipeline reservation table shows when stages of a pipeline are in use for a particular function.

This definition sounds confusing to me: is "function" a synonym for "operation" in this case? So, a static pipeline can only process a batch of instructions that use the same operator? Like if the pipeline had to be "rewired" every time a new operator is issued? It makes no sense to me.

In order to get lost a bit more, I resorted to Wikipedia which states that

  A linear pipeline processor is a series of processing stages and memory access. A non linear pipelining (also called dynamic pipeline) can be configured to perform various functions at different times. In a dynamic pipeline there is also feed forward or feedback connection. Non-linear pipeline also allows very long instruction words.

So, static pipelines are linear, dynamic ones are non-linear and functions are indeed a synonym for operations in this context? And, finally, are static pipelines really reconfigured every time a new function is processed?

The reference I've mentioned is actually self-contained; i.e, the answer I was looking for was there all the time. But considering that others could have the same doubt, I will reproduce an snippet from that reference and answer my own question:

  Pipelines are usually divided into two classes: instruction pipelines and arithmetic pipelines. A pipeline in each of these classes can be designed in two ways: static or dynamic. A static pipeline can perform only one operation (such as addition or multiplication) at a time. The operation of a static pipeline can only be changed after the pipeline has been drained. (A pipeline is said to be drained when the last input data leave the pipeline.) For example, consider a static pipeline that is able to perform addition and multiplication. Each time that the pipeline switches from a multiplication operation to an addition operation, it must be drained and set for the new operation. The performance of static pipelines is severely degraded when the operations change often, since this requires the pipeline to be drained and refilled each time. A dynamic pipeline can perform more than one operation at a time.

So, yes, a "function" is a synonym for "operation" in this context, but nothing is said about linear and non-linear pipelines. I hope some fellow can confirm if those terms exist indeed with the same meaning used in the Wikipedia.


Infinite recognizable not decidable subsets If L is an infinite ($|L|=|\mathbb{N}| $) decidable language, prove that it contains:
a) An infinite subset that is not recognizable
B) An infinite subset that is recognizable and not decidable
For the (a) I considered all the subsets of L, i.e., $\mathbb{P}$(L)
So $|\mathbb{P} (L)| = |\mathbb{R}|$ so that means that it exists $A \subset L$ that is not recognizable
(for there are not enough Turing machines to recognize them all)
If A were finite, then it would be decidable so it would be recognizable which would be a contradiction.
Therefore A is infinite and not recognizable.
For (b) I thought about B=L\A.
Then B is recognizable because A is not?
But I'm not really sure

Let $K$ be the set of indices of Turing machines which halt on the empty input. Consider the following language:
$$X = \{ 0 w : |w| \in K \} \cup \{ 1 w : |w| \notin K \}. $$
You can check that neither $X$ nor its complement are recognizable.
Therefore your proof idea doesn't work. Here is a different idea. Let $w_1,w_2,w_3,\ldots$ be the words in $L$, enumerated according length and then lexicographically (so if $L = \Sigma^*$, the order would be $\epsilon,0,1,00,01,10,11,\ldots$). The language
$$ Y = \{ w_i : i \in K \} $$
is recognizable but not decidable.


Fastest way to check data against an envelope If I have two arrays containing max and min points which make up an envelope. It's quick to test if any point in a given data array goes outside of that envelope using:

 for (int i = 0; i < envMax.size(); i++)
    {
        if ((data[i] < envMin[i]) || (data[i] > envMax[i]))
        {
            return false;
        }
    }
    return true;

However, my data array can be large and I have to load the max and min envelope data from a file for each new data array which needs testing (just the way the system works). So it might be quicker to just use a smaller number of points for the envelope and interpolate. But whats the quickest way of doing this with a  reduced number of points. I can do (sudo code):

for each data point
find min and max envelope point before and after data point
calculate equation of line between two points
put in data "x" value
check resultant y value.

Alternatively I can just generate N max and min envelope points (where N is = length(data)) (same thing really)...

But this seems computational exhausting. I can't believe I am the first person to want to do this so is there an accepted (fastest) method / algorithm type?

EDIT:

The problem is essentially this: Check that the blue line is within the green lines. But doing it when the number of points describing the green lines is much less than the number of points describing the blue line.

From the short description you give, I infer that you consider that fetching the envelope data from disk is a bottleneck.

Even assuming that the envelope values change with every dataset (so that there is no reuse), you figure seems to show that there are as many data points as there are envelope points. So if you completely avoided the fetching of the envelope, you could at best hope for a threefold improvement, and virtually no improvement in case there is reuse.


Is the $x$ in $\frac{\mathrm{d}}{\mathrm{d}x}$ a symbol in the sense of Harper's PFPL? The role of $x$ in $\frac{\mathrm{d}}{\mathrm{d}x} y$ not only confuses my calculus students, it has also puzzled some well known mathematicians. Questions one might ask are:

Does the $x$ in the denominator bind the $x$ in $y$? (Clearly no, since $\frac{dx^2}{dx}=2x$.)
Can one substitute for $x$ in the denominator? (Looks like not, what should $\frac{dx^2}{d3}$ mean?)
Is the $x$ in the denominator itself bound?

I was wondering if interpreting that $x$ as a symbol, in the sense of Bob Harper's Practical Foundations for Programming Languages (Chapter 1.2 on abstract binding trees) might solve these riddles, and if this had already been worked out by someone?

Here's a quote from PFPL:

  It will often be necessary to consider languages whose abstract syntax
  cannot be specified by a fixed set of operators, but rather requires
  that the available operators be sensitive to the context in which they
  occur. For our purposes it will suffice to consider a set of symbolic
  parameters, or symbols, that index families of operators so that as
  the set of symbols varies, so does the set of operators. [...] The
  only difference between symbols and variables is that the only
  operation on symbols is renaming; there is no notion of substitution
  for a symbol.

Some mathematicians find it natural to substitute for the variable in the denominator of a derivative, writing things like $\frac{d \log V}{d\log p}$. This suggests that the $x$ in the denominator $\frac{dy}{dx}$ is neither bound nor binding nor a symbol.

Rather $\frac{dy}{dx}$ seems to be an operation on "variable quantities" $y,x$ requiring some side conditions, similar to how the usual division $a/b$ requires $b\neq 0$, or how the operation $\frac{v}{v_1^0\ldots v_i^1\ldots v_n^0}$ in my comment requires $v_1,\ldots,v_n$ to be linearly independent and $v$ to lie in their span.

I suspect that the side condition for $\frac{dy}{dx}$ should be analogous: $dx$ needs to be linearly independent and $dy$ has to be a multiple of $dx$.

With these side conditions we are not allowed to substitute a constant for $x$ in $\frac{dy}{dx}$ since then $dx=0$ and so $dx$ is not linearly independent. That would explain why we are not allowed to write $\frac{d x^2}{d3}$ or to take the derivative of equation $x=0$ w.r.t. to $x$ to conclude $1=0$.

I'd be interested in hearing if someone sees an immediate problem with this interpretation.

(I see some subtlety in the fact that $d(x|_{x=3})$ cannot mean the same as $(dx)|_{x=3}$, since otherwise I'd expect $\frac{dy}{dx}|_{x=3}$ to be the same as $\frac{d(y|_{x=3})}{d(x|_{x=3})}$ which would not be allowed by the side condition. On the other hand, that is not so strange from a differential geometric point of view if we read $|_{x=a}$ as restriction: there is a difference between restricting a differential form and pulling it back. But I need to think more about this.)


Hamiltonian non intersecting path in plane $N$ points are located in 2D plane. Some of the pair of the points are connected by line segments. What is the complexity of the problem of existence of Hamiltonian non intersecting path? What if we consider it in special cases of graphs.

Hamiltonian path problem remains NP-complete in planar graphs [1], so your problem is also NP-complete since in a planar graph, two edges cannot intersect with each other.

[1] Garey, M. R., Johnson, D. S., & Tarjan, R. E. (1976). The planar Hamiltonian circuit problem is NP-complete. SIAM Journal on Computing, 5(4), 704-714.


Auction where each bidder bids on a bundle of items Is there some optimal solution in an auction where each bidder bids on a bundle of items?

This problem is NP-hard, by reduction from 3-dimensional matching.

An instance of 3-dimensional matching involves three disjoint vertex sets $X,Y,Z$ and a set $T \subseteq X \times Y \times Z$ of triples of the form $(x_i,y_j,z_k)$.  The goal is to find a subset $T_0 \subseteq T$ such that each vertex of $X \cup Y \cup Z$ appears in at most one triple of $T_0$, and the cardinality of $T_0$ is maximized.

Given an instance of 3-dimensional matching, we can construct an auction with bidders $X$ and items $Y \cup Z$.  For each $(x,y,z) \in T$, we'll have $x$ bid \$1 on the pair of items $y,z$.  Now the optimal set of accepted bids for the auction is exactly the maximum 3-dimensional matching, so any algorithm to solve your problem would also solve 3-dimensional matching.

Since 3-dimensional matching is known to be NP-hard, it follows that your problem is also NP-hard, and in particular, there isn't likely to be any efficient algorithm for your problem.

The same reduction also shows that your problem is APX-hard, i.e., there is some $c>1$ such that there does not exist any $c$-approximation algorithm for your problem (unless P=NP).

I don't know whether there might be an approximation algorithm for some constant approximation factor.  It's known that 3-dimensional matching can be approximated in polynomial time with a $3/2 + \varepsilon$ approximation factor; you might check whether any of those algorithms can be adapted to provide suitable solutions for your problem.  For instance, one very simple approach might be to find a maximal matching of the associated hypergraph; this will give a $1+k$ approximation, if every bid mentions at most $k$ items.  I don't know if you can find maximal matchings in hypergraphs in polynomial time, like you can in ordinary graphs.

Practical algorithms

If you have to deal with this problem in practice, I suggest formulating it as an integer linear programming (ILP) problem and then applying an off-the-shelf ILP solver.

Introduce zero-or-one variables $x_i$, with the intended meaning that $x_i=1$ means that the $i$th bid is accepted.  Each constraint "at most one bid is accepted from each person" turns into a inequality of the form $\sum_{i \in S} x_i \le 1$.  Each constraint "each item appears in at most one accepted bid" turns into another inequality of the same form.  The objective function is a linear function of the $x_i$'s.  Now apply an off-the-shelf ILP solver, like CPLEX.


Computer science for programmers I'm a self-taught programmer and have been coding for 8 years. Due to this experience, I'm already very familiar with the principles of programming (such as if-statements, classes, polymorphism, etc.).

However, I never learned "computer science," only programming. What are some good resources for someone in my position to self-study computer science - that is, resources which move at a quick pace and assume basic programming knowledge?

Computer Science is a multifaceted discipline - and Algorithms and Data Structures is important part of it. You can try free video-courses, like Algorithms, Part 1, from Princeton University - it's running right now.

Another remarkable free video-course Algorithms: Design and Analysis, Part 1, from Stanford has finished recently - hopefully it will be repeated in the future. Part 2 of this course will start this Monday.


Does Google's PageRank count as a sorting algorithm? Is it correct to assume that PageRank is a sorting algorithm or does it fall in any other category?

The answer depends on what you mean by a sorting algorithm. The usual meaning is:

  A sorting algorithm is an algorithm that gets a list $L$ of comparable objects, and sorts them in (say) nondecreasing order. The algorithm could only work for a certain class of objects.

If you use this definition, then PageRank isn't a sorting algorithm. But it's up to you.


Can given grammar be parsed using recursive descent? I have this Grammar below:
Expr ::= Term "(" Term ")"

Term ::= Ident | "(" Expr ")"

Start symbol: <Expr>
Terminal symbol: Ident ::= [a-z]+

And I wonder if it is possible to construct a recursive descent parser for grammar G2?
I think this won't be able to do that?

You will be able to.
Consider what happens when you try parsing a string as an Expr: you will need to read a term. If your term is starts with an english alphabet character, then its an Ident and once you stop seeing letters a-z, then you have finished reading Term. If it does not start with an alphabet character, then you need to see a '(' and you will retry reading an expression from there (by induction this will work), and finally read a ')'.
So we can successfully read the first Term, and after that we just need to see a '(', another Term (and again by induction we can do that) and finally a ')'
This language has no ambiguity so its pretty easy to parse.


Can map-reduce speed up the count-min-sketch algorithm? Is there any possibility of improvement in the result of count-min-sketch algorithm if we will use Map Reduce approach?
Improvement in performance can be in terms of accuracy, time complexity or the work done needed.

yes. section 3.2 from here.

  A key feature of the operations which manipulate the sketch is that
  they are largely oblivious to the current state of the data structure.
  That is, the updates to the sketch do not require inspection of the
  current state. This means that data structure is highly suitable for
  parallelization and distributed computation. Firstly, each row of the
  sketch is updated independently of others, so the sketch can be
  partitioned row-wise among threads on a single machine. But more than
  this, one can build sketches of different subsets of the data (after
  agreeing on the same parameters w, d and set of hash functions to
  use), and these sketches can be combined to give the sketch of the
  union of the data. Sketch combination is straightforward: given sketch
  arrays of size w × d, they are combined by summing them up,
  entry-wise. This implies that sketches can be a useful tool in large
  scale data analysis, within a distributed model such as MapReduce.
  Each machine can build and “emit” a sketch of its local data, and
  these can then be combined at a single machine (i.e. a single reducer
  simply sums up all the sketches, entry-wise) to generate the sketch of
  a potentially huge collection of data. This approach can be
  dramatically more efficient in terms of network communication (and
  hence time and other resources) than the solution of computing exact
  counts for each item, and filtering out the low counts.


Minimizing sum of recursive pairwise sums What is the best algorithm for this?

We are given an array of positive integers and we want to minimize the total cost of recursively adding together all the integers to one integer, two integers at a time. The cost of each addition is the sum of the two integers, and this sum adds up cumulatively. After each addition, the two integers are removed from the array, but their sum is added, until only one value remains.

I think I have figured out so far that the optimal solution is to add up the two smallest values in the array at every step (as the earlier the figure is used the more times it is included in the cumulative cost.) Perhaps there is another way to think about the problem, though.

Is there some mathematical fact that trivializes the solution perhaps?

Example A:

Input: [1, 5, 3, 7]
Adding 1 and 3 together (Cost 1+3 = 4)
State: [5, 7, 4]
Adding 4 and 5 together (Cost 4+5 = 9)
State: [7, 9]
Adding 7 and 9 together (Cost 7+9 = 16)
State: [16]

Total cost: 4 + 9 + 16 = 29

Example B:

Input: [1, 1, 1, 1, 1]
Adding 1 and 1 together (Cost 1+1 = 2)
State: [1, 1, 1, 2]
Adding 1 and 1 together (Cost 1+1 = 2)
State: [1, 2, 2]
Adding 1 and 2 together (Cost 1+2 = 3)
State: [2, 3]
Adding 2 and 3 together (Cost 2+3 = 5)
State: [5]
Total cost: 2 + 2 + 3 + 5 = 12

(I made these examples up myself; let me know if the examples are not actually the optimal solutions, although I am pretty confident they are.)

This problem can be solved using a min heap. You have to construct a min heap initially with all the elements of array. Now you simply take the top element of this heap and add it to the next top element of heap. Then reinsert the sum obtained in the heap. Keep a variable to track the total cost. This will ensure that you are adding the minimum elements and the final cost is minimum. This is analogous to the problem of connecting n ropes with minimum cost.


Can a 2-way set associative mapping have just one set? Though unintuitive, can a 2-way set associative mapping have only one set. For e.g., Cache size 8 bytes, block size 4 bytes and main memory size as 16 bytes. Here the number of cache lines are 2 and given 2 way set associative the set count is only 1. Can I map the 4 blocks (0,1,2 and 3) in the main memory to a 2-way set associative mapping?

If I can, what would be the set index? Since the set size is 1 = 20. is set index always 0. [in CPU OS simulator, it is not throwing any error when I try to set the cache and block size and mapping as 2-way]

Set index will be 0 or no set index.
Set associative mapping has set identification algorithm the same as direct  mapping which is j mod m, where j is the main memory line and m is the total set count. Here in this case, main memory has 4 main memory lines ( 0, 1, 2 and 3 with each having 4 bytes). Now set count is 1, hence 0 mod 1, 2 mod 1, 3 mod 1 and 4 mod 1 are all 0 which means all blocks will get mapped to Set 0 and within the set 0, the mapping is fully associative. The behaviour and mapping is more like fully associative mapping. hence for a set-associative mapping, a 2-way set associative mapping with 2 cache lines or a 4-way set associative mapping with 4 cache lines etc., behaves like fully associative and set index width is 0.
Generalizing, a K-way set associative mapping with K cache lines only will behave like a fully associative mapping.


Solving a T(n) recursion without Master Theorem i have a problem solving the recursion $T(n) = T(n-20)+log(n)$, because
the Master Theorem is not applicable in this case.

This is my attempt:
$T(1) = 1$(given)
$T(n) = T(n-20)+log(n)$
$T(n) = T(n-20-20)+log(n-20)+log(n) $
...
...
$T(n) = T(n-k)+log(n-(k-20))+....+log(n)$

Let be $ k = n-1$
$T(n) = T(n-(n-1)) +log(n-(n-1-20)+...+log(n)$
$T(n) = T(1)+log(21)+....+log(n)$

Which results in:
$ 1+ \sum_{n=1}^{\frac{n}{20}} ???$(i dont know if this is correct)

I am searching for a final result, which should be $\Theta(nlog(n))$

Start with
$$T(1)= 1$$
$$T(21)= T(1)+\log(21)$$
$$T(41)= T(21)+\log(41)$$
$$\dots$$
$$T(20k+1)= T(19k+1)+\log(20k+1)$$
Then move $T(i)$s from the right side to the left side
$$T(1)= 1$$
$$T(21) - T(1) = \log(21)$$
$$T(41) - T(21) = \log(41)$$
$$\dots$$
$$T(19k+1) - T(18k+1) = \log(19k+1)$$
$$T(20k+1) - T(19k+1) = \log(20k+1)$$
And sum the left and right sides

$$T(20k+1) = 1 + \log(21) + \dots + \log(20k+1) \leq 1 + \sum_{i=1}^{k}{\log(21i)} = $$
$$1 + \sum_{i=1}^{k}{[\log(21)+\log(i)]} \leq 1+ \sum_{i=1}^{k}{\log(21)}+ \sum_{i=1}^{k}{\log(k)} = $$
$$1 + k\log(21) + k\log(k)$$ which is $O(n\log{n})$. This was only upper bound.

More general case

There is nothing special with the integers 1 and 20. You could take any positive integers instead of 1 and 20 and solve the relation

$$T(b) = c$$
$$T(n)= T(n-s) + \log{n}$$
as
$$T(b) = c$$
$$T(s+b) = T(b) + \log{(s+b)}$$
$$T(2s+b) = T(s+b) + \log{(2s+b)}$$
$$\dots$$
$$T((n-1)s+b) = T((n-2)s+b) + \log{((n-1)s+b)}$$
$$T(ns+b) = T((n-1)s+b) + \log{(ns+b)}$$
which gives
$$T(ns+b) = c + \log{(s+b)}+\log{(2s+b)}+\dots + \log{(ns+b)}$$

Is $n\log{n}$ a lower bound for this relation?

UPDATE: Omar's post attempts to establish a lower bound.