search problem vs optimization problem This is mostly a terminological question: Is there a fundamental difference between "optimization problems" and "search problems"? Apologies if this is an obvious question
As I understand it, we can define the two as follows (note, I consider the problem for a fixed input size for brevity):

Search problem. Given a set $X$ of candidate solutions, and a property $P:X\to \{\text{True}, \text{False}\}$, find an $x\in X$ such that $P(x)$.
Optimization problem. Given a set $X$ of candidate solutions, and a criterion function $F:X\to \mathbb R$, find an $x\in X$ such that $x\in \arg\max_{y\in X} F(y)$.

But it seems to me that to say that a search problem $P_S$ is "reducible" to an optimization problem $P_O$ is an understatement: They seem to be exactly the same apart from a "stylistic" difference:

Given a search problem $P_S=(X,P)$, define optimization problem $P_O=(X,F)$ where $F(x) = \begin{cases}1 \quad \text {if }  P(x)\\0\quad \text {if } \neg P(x) \end{cases}$
Given a optimization problem $P_O=(X,F)$, define search problem $P_S=(X,P)$, with $P(x)=  \begin{cases}\text{True} \quad \text { if }  x \in \arg\max_{y\in X} F(y)\\\text{False}\quad \text { if } x \notin \arg\max_{y\in X} F(y)\end{cases}$

Is there really not a fundamental difference between these two problems? Or are they fundamentally different in some way that I'm overlooking?

The fundamental difference in these two problems lies in the verification of a proposed solution.

The solution of a search problem is only as hard to verify correct as the predicate itself.

The solution of an optimization problem needs special arguments or proofs to avoid having to search the entire domain to verify a solution correct, which often may not exist or are not known.

This means that simply finding a solution is enough for a search problem, but without a proof or exhaustive search an instance for an optimization problem is uncertain.

I think search problem is to search for a solution (or many solutions) that satisfies a condition.
Whereas, Optimization problem is to search for the best solution that satisfies a condition.
When the search space becomes large, we can't expect to be able to find out the optimal solution, then we turn the search problem into an optimization problem, with the hope that as searching for the best solution we may find some acceptable one. By doing so, we are using the optimization techniques which do not promise to find the optimal solution, instead of using the search techniques, which always do.


Show that any monotone Boolean function is computable by a circuit containing only AND and OR gates A Boolean function $f : \{0, 1\}^n → \{0, 1\}$ is called monotone if changing any of the $n$ input bits $x_1, \ldots , x_n$ from $0$ to $1$ can only ever change the output $f(x_1, \ldots ,x_n)$ from $0$ to $1$, never from $1$ to
$0$.

I know how to do a simple proof of exhaustion for $f : \{0, 1\}^1$ and $f : \{0, 1\}^2$, but I do not know how to prove the following statement for $f:\{0,1\}^n$: any monotone Boolean function is computable by a circuit containing only AND and OR gates.

Any Boolean function can be written as a DNF. Each clause in the DNF specifies one truth assignment for which the function holds. For example, the DNF form of XOR is $(x \land \lnot y) \lor (\lnot x \land y)$.

The main observation is that if the function is monotone, you can remove all the negated literals (why?). Once you do that, you get a formula for the function which uses only AND and OR. Some clauses in this formula subsume others (for example, $x$ subsumes $x \land y$). If you drop all the subsumed clauses, you arrive at the minterm representation of the function. (A minterm is a minimal satisfying assignment.)

It's a bit more confusing, but you can also do everything using CNFs. This way you arrive at the maxterm representation.

In the expression $OR(x,y)$, if I define x as 0 and y as $f:\{0,1\}^{n-1}$, OR(x,y) is monotone and can represent any monotone function. This statement is in $f:\{0,1\}^{n}$, which means $f:\{0,1\}^{n}$ contains any monotone function.


Counting frequencies of Element in an array Given an array of size $N$. I need to find the count of values in range $[L, R]$ which are repeated at least three times in successive positions (i.e., the value occurs contiguously three times).

For eg-
\begin{align*}
    A&= 1,1,1,2,2,1,5,1,1,2,2,2,5,5 \\
    L&=0,\ R=3\,,
\end{align*}
the answer would be 1 (1,1,1) and 2 (2,2,2).

I tried it by doing the following:

  answer = 0
  count[] = 0
  for i in {l..r}:
    count[array[i]]++
    if count[array[i]] == 3:
      answer++

But this will count frequencies all over the range and not just the contiguous ones. So the answer will include $5$ as well where as it shouldn't.

How do I treat any element that starts again after some other integers come in between to be different (like here I need to treat $5$'s count differently) and consider it again for it be $\geq 3$ ? Like can I hash them somehow?

Update :Logic being same, some modification in code. I shift the $L,R$ as the function is called multiple times and increase and decrease the count.

add(position):
  count[array[position]]++
  if count[array[position]] == 3:
    answer++

remove(position):
  count[array[position]]--
  if count[array[position]] == 2:
    answer--

currentL = 0
currentR = 0
answer = 0
count[] = 0
for given L,R
  // currentL should go to L, currentR should go to R
  while currentL < L:
    remove(currentL)
    currentL++
  while currentL > L:
    add(currentL)
    currentL--
  while currentR <= R:
    add(currentR)
    currentR++
  while currentR >R+1 :
    remove(currentR)
    currentR--
  output answer

I need to calculate for many pairs of L,R .So I need an efficient algorithm.
The above algorithm seems to do so.

But How do I differentiate the contiguous triplets here ?

Maybe this:

answer = 0
lastVal = -1    //some value not inside [L,R]
count = 0
for i in {l..r}:
  if (array[i] != lastVal)
     count = 1
     lastVal = array[i]
  else
     count++
     if (count == 3)
        count = 0
        answer++

Edit: This code assumes that the set (1,1,1,1) is counted as one triplet not two.
i.e.: (1,1,1) and (1), not (1,1,1) and (1,1,1)

answer = 0
last = null
count = 0
foreach value in array
   if (last != null)
       if (value == last)
          count++
       else
          if count >= 3 then answer++
          count = 0
   last = value
if count >= 3 then answer++


What exactly is polynomial time? I'm trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn't find an exact definition anywhere. I assume it is the complexity that is not exponential.

Do linear/constant/quadratic complexities count as polynomial? An answer in simple English will be appreciated :)

An algorithm is polynomial (has polynomial running time) if for some $k,C>0$, its running time on inputs of size $n$ is at most $Cn^k$. Equivalently, an algorithm is polynomial if for some $k>0$, its running time on inputs of size $n$ is $O(n^k)$. This includes linear, quadratic, cubic and more. On the other hand, algorithms with exponential running times are not polynomial.

There are things in between - for example, the best known algorithm for factoring runs in time $O(\exp(Cn^{1/3} \log^{2/3} n))$ for some constant $C > 0$; such a running time is known as sub-exponential. Other algorithms could run in time $O(\exp(A\log^C n))$ for some $A > 0$ and $C > 1$, and these are known as quasi-polynomial. Such an algorithm has very recently been claimed for discrete log over small characteristics.

In layman terms it the running time of your algorithm.

The order of algorithms (growth) can be in Big-oh (O), little-oh(o), omega (Ω) or theta(Θ).

If you are having problems calculating RR please view some questions i asked before and vote if you understand.

Say you have a for loop:

 for(i=1 to n)
     x++

The order or time complexity of this piece of code is: O(n)

Why big-oh? Because we want the worst case at which this piece of code runs.

Read here (these define the complexity of an algorithm and informs you of how algorithms are done in polynomial time):

 http://en.wikipedia.org/wiki/NP_(complexity)

 http://en.wikipedia.org/wiki/NP-complete

 http://en.wikipedia.org/wiki/NP-hard

Summary:

http://www.multiwingspan.co.uk/a23.php?page=types


Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations? I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in logarithmic time. The closest I've found to this is the order statistic tree which achieves logarithmic add and delete operations but has logarithmic time complexity for accessing the kth smallest element.

Any ideas along these lines would be much appreciated.

Clarification: kth smallest means that for any variable k value (non-constant), the data structure should be able to retrieve that value

An array is the only thing that will get you consistent lookup in constant time.

Removal & Insertion time $\in O(n)$

If you can fit your data to a model (I.e. a polynomial) and the size of your elements remains somewhat constant you can have almost constant lookup with log addition/removal

Kth smallest number in a dynamic stream of numbers.
Idea from the above source.

Have two heaps, one a max heap with $k$ elements (all the elements less than the $k$th largest element and the $k$th largest element itself are here) and the rest of the elements are in the other min heap.

Inserting a new element: If the new element is less than the top of the max heap (which is the current $k$th largest element), then insert it into the max heap, after that (I mean to say after the heapification following the insertion) pop the top element and insert it into the min heap.
If the new element is greater than or equal to the current $k$th largest insert it into the min heap.
Deletion: If the element is in the min heap (ie., greater than equal to the $k$th largest) then simply delete from the min heap*. Else delete the element from the max heap and pop the top of the min heap and insert it into the max heap.
Look up: simply output the top of the min heap.
You'll have to suitably handle the corner case where there aren't enough elements ie. the total number of elements are less than $k$.

Please look into deletion of element in $O(\log n)$ time. It's a little complicated – you've gotta keep track of the positions of the elements in the heap so that you have $O(\log n)$ if you use a set (in C++) or $O(1)$ amortized if you use hash tables/unordered set. After finding the element in heap you've gotta replace it with the last element in the heap and let it sift down or up, which is $O(\log n)$.


Collectively pay the bill problem There are $n$ people at a table. The $i$th person has to pay $p_i$ dollars.

Some people don't have the right bills to pay exactly $p_i$, so they come up with the following algorithm.

  First, everyone puts some of their money on the table. Then each individual takes back the money they overpaid.

The bills have a fixed set of denominations (not part of the input).

An example:
Suppose there are two people, Alice and Bob.  Alice owes \$5 and has five \$1 bills.  Bob owes \$2 and has one \$5 bill.  After Alice and Bob put all their money on the table, Bob takes back \$3, and everyone is happy.

Of course, there are times where one doesn't have to put all his money on the table. For example, if Alice had a thousand \$1 bills, it's not necessary for her to put them all on the table and then take most of them back.

I want to find an algorithm with the following properties:

The input specifies the number of people, how much each person owes and how many bills of each denomination each person has.
The algorithm tells each person which bills to put on the table in the first round.
The algorithm tells each person which bills to remove from the table in the second round.
The number of bills put on the table + the number of bills removed from the table is minimized.

If there is no feasible solution, the algorithm just return an error.

If you restate the problem in a slightly different (but equivalent) way, an algorithm becomes more obvious:

There are $n$ parties involved: $n-1$ persons, and one restauarant.  Let $p_i$ be the amount of money party $i$ should have after the meal is finished and paid for.  For example, if Alice has \$36 and owes \$25, Bob has \$12 and owes \$11, and Carl has \$30 and owes \$25, we say that $p_0$ is the restaurant and have:

$p = (61, 11, 1, 5)$

That is, when the meal is over the restaurant should have \$61, Alice should have \$11, Bob should have \$1 and Carl should have \$5.

Now let $b$ enumerate all of the $m$ bills involved.  For example:

$b = (1, 5, 10, 20, 1, 1, 5, 5, 10, 20)$

The denominations of the bills do not matter, but I have chosen denominations of paper US currency for this example because they are familiar.

We are seeking to minimize the number of bills that change hands, so we associate a "cost" with person $i$ leaving with bill $j$ by using a $\{0,1\}$ matrix $C$.  Entries of 0 in this matrix indicate which bills each party starts with ($C_{0,j} = 0$ for all $j$ because the restaurant starts with no bills).

Continuing our example:

$$
C = \left[ \begin{array}{cccccccccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\
\end{array}
\right]
$$

indicates that Alice started with \$1, \$5, \$10, \$20, Bob started with \$1, \$1, \$5, \$5, and Carl started with \$10 and \$20.

Again, the goal is to minimize the number of bills that change hands.  In other words:

$$
\begin{align}
\text{Minimize:} & \sum_{i=0}^{n-1}{\sum_{j=0}^{m-1}{C_{i,j} x_{i,j}}} \\
\text{subject to:} & \sum_{i=0}^{n-1}{x_{i,j}} = 1  \text{ for } 0 \le j \lt m, \\
& \sum_{j=0}^{m-1}{x_{i,j}b_j = p_i} \text{ for } 0 \le i \lt n, \\
\text{and} & x_{i,j} \ge 0
\end{align}
$$

The first constraint says that the solution can only assign a particular bill to one party, and the second ensures that everyone pays the appropriate amount.

This is the 0,1 INTEGER PROGRAMMING problem and is NP-complete (see [Karp 1972]).  The Wikipedia page about linear programming has information on different algorithms that can be used for these types of problems.

There are potentially multiple optimal solutions; by hand the first solution to the example I came up with was:

$$
x = \left[ \begin{array}{cccccccccc}
0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
\end{array}
\right]
$$

which means Alice pays exactly \$5 and \$20, Bob pays exactly \$1, \$5 and \$5, and Carl overpays \$10 and \$20 and then removes a \$5 from the table.

I also used the Mixed Integer Linear Program module of the Sage Math system which has the ability to use different solver backends (GLPK, COIN, CPLEX, or Gurobi).  The first solution it gave was

$$
x = \left[ \begin{array}{cccccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
\end{array}
\right]
$$

which is almost the same except that Carl took the "other" $5 that Bob put on the table.

Formulating the problem in this way satisfies all the properties you list (you can extrapolate which bills end up where from $C$ and the solution matrix $x$).  The exception is perhaps #4 which was discussed in the comments of the question.  It is not clear to me what you would like to do in the situation that there is no feasible solution to the set of linear equations:

Identify a subset of people that can pay the reduced total?  Or perhaps a subset of people which could still pay the entire bill, i.e. they pay for their friend.

Your final statement makes it seem like you are interested in the case that the denominations of the bills are fixed, this doesn't change the problem however.

In any case, there is also an $O(1)$ solution in which every person pays with a credit card.

Certainly some basic starts could be to include the smallest bills available to reach the total amount of the overall bill.  If you don't care to allow \$2 bills, each person could simply remove the largest bill they can take from the pool then and would get there relatively quickly.  The \$2 bill throws that off as it doesn't sub-divide nicely in to the other denominations and greatly complicates the problem.  There are also certainly a number of other optimizations that could be done to make observations about the need for further funds to be added during round 1 (for example, if the total number of \$1 bills is ever sufficient to cover the bill, then everyone can stop putting in unless they have not yet put in enough for their bill).


How to tell if a Heuristic is monotonic I've applied a Heuristic to a puzzle where I need to move all off the B's the the right of the W's. my Heuristic is the total distance of the B's from the right most W's. my initial state is (B,B,B,*,W,W,W), where * represents a blank space. A piece can move into a blank space and can jump over one or two other pieces into a blank space. I've attached a picture of the graph.

This Heuristic is Admissible because the distance to the goal is ALWAYS more than the distance from the B's to the rightmost W.

The thing I'm not sure of is if this Heuristic is monotonic. My understanding of Monotonic is that the cost of going to an adjacent node plus the estimate of the new node have to be less than the total distance to the goal. How would I determine if this Heuristic is monotonic?

If your heuristic is essentially the original problem, but with some constraints removed, it is monotonic.
Otherwise, you must prove that there is no transition which does not uphold the formula in Caesar's answer.


Why do Computers use Hex Number System at assembly language? Why do computer use Hex Number System at assembly language? Why don't they use any other number system like binary, octal, decimal? What thing forced computer designer to use hex system at assembly? Why it looked so beneficial to them?

Computers don't use the hexadecimal number system for assembly language. Assembly language, or rather machine code, uses base 256 (typically): instructions are encoded in units of bytes. When displaying machine code, it is customary to use octal or hexadecimal. The reason is that in many cases, the byte is further subdivided into bitstrings, and identifying these bitstrings is easier when using a base which is a power of 2. Hexdecimal is particularly compact since each byte can be encoded using exactly two hexadecimal digits.

Hexidecimal (TM copyright IBM) is a notation. It incorporates a familiar numeric system, the Binary Coded Decimal (BCD) of 10 symbols 0-9 in a 4 bit representation system, the remaining 6 values of the 16 possible combinations are represented by a,b,c,d,e,f or A,B,C,D,E,f respectively. In this fashion a 'nibble' of 4 bits can conviently represent all the possible values in a simple notation.


Proof that no O(n) multiplication algorithm exists For the multiplication of two $n$ digit numbers, the best known algorithm has complexity $O(n \log n)$. Has it been proven that this is the best possible, or that an algorithm $O(n)$ is not possible?

There is a conditional $\Omega(n\log n)$ lower bound due to Afshani, Freksen, Kamma, Green Larsen, Lower Bounds for Multiplication via Network Coding.

You could do it in O(1), kinda...

Precompute a lookup tables of log and log-1 values.
Get absolute values
Look up the two numbers,
Add the log of the two numbers
Look up log-1
Change to negative if one of the original numbers was negative.

Boom! O(1)

If you work with 32bit signed ints then that would only take 8gb of of memory for the first table (312 x 4bytes) and 16gb for the second (312 x 8bytes). (It may be possible to compress them a bit for the small logs and log-1s)

Quite a bit of memory yes, but readily available on consumer grade laptops.

If you have lots of 32 signed ints it may be worth the large contact overhead?!


How to show working for summing of Big O notation The equation below is intuitively correct, but how do you show that this is actually the case? What is the working out needed?
$$\sum_{i=1}^{n-1}O(lg n) = O(nlgn)$$

Summand inside sum is not depend on summation index, then pull it out and you have n−1 before log.


Algorithm to add sum of every possible xor-sum sub-array I participated in one algorithmic competition. I got stuck in one problem, I am asking the same here.

Problem Statement

XOR-sum of a sub-array is to XOR all the numbers of that sub-array.
An array is given to you, you have to add all possible such XOR-sub-array.

Example

Input

Array :- 1 2

Output :- 6

Explanation

F(1, 1) = A[1] = 1, F(2, 2) = A[2] = 2 and F(1, 2) = A[1] XOR A[2] = 1 XOR 2 = 3. Hence the answer is 1 + 2 + 3 = 6.

I found an $O(N^2)$ solution, but it was too inefficient one and wasn't accepted in the competition.

I saw the best solution of this problem on Code Chef. But in this code, I didn't understand below module, please help me to understand that.

for (int i=0, p=1; i<30; i++, p<<=1) {
    int c=0;
    for (int j=0; j<=N; j++) {
        if (A[j]&p) c++;
    }
    ret+=(long long)c*(N-c+1)*p;
}

In pseudocode:

Set $r = 0$
For $i$ from $0$ to $29$, let $p = 2^i$.

Set $c=0$
Iterate over the array $A$. For each element $A[j]$:

If $A[j] \mathbin\& p \ne 0$ then increment $c$. ($\&$ is bitwise and.)

Add $c \times (N-c+1) \times p$ to $r$

After the first couple of lines the array $A$ contains the XOR of every prefix of the input numbers in binary. So a $1$ bit at position $k$ in $A[j]$ tells us that there are an odd number of input numbers in the range $0...j$ with $1$ at their position $k= \log p$.

For every $i,j$ s.t. $i \leq j$, if the $k$th bit of $A[i-1]$ is $1$ and the same bit in $A[j]$ is $0$ then there are an odd number of $1$s at bit-position $k$ of the input numbers in the range $i...j$. The same conclusion would be true if the $k$th bit was $0$ for $A[i-1]$ and $1$ for $A[j]$. Please observe that these are the only two situations where the number of ones at position $k$ is odd in the range $i...j$.

Therefore the number of pairs $(A^k[i-1],A^k[j])=(0,1)$ or $(1,0)$ is equal to the number of ranges in the input such that their XOR at position $k$ is $1$. Every such range contributes $p=2^k$ to the total sum. In that code, $c$ is the number of ones and $(N-c)$ is the number of zeros at position $k = \log p$. The "$+1$" is to count for the ranges of length one and a $1$ in their $k$th position.

Just do the OR operations of all numbers and multiply the answer with power(2,N-1) where N is the length of your array.
For array given in question:
1 OR 2 = 3
Now, 3*(power(2,(2-1))) = 6 which is the answer.
The point here is that, Each set bit of any number occurs exactly in power(2,N-1) sub arrays.


Differences and relationships between randomized and nondeterministic algorithms? What differences and relationships are between randomized algorithms and nondeterministic algorithms?

From Wikipedia

  A randomized algorithm is an algorithm which employs a degree of
  randomness as part of its logic. The algorithm typically uses
  uniformly random bits as an auxiliary input to guide its behavior, in
  the hope of achieving good performance in the "average case" over all
  possible choices of random bits. Formally, the algorithm's performance
  will be a random variable determined by the random bits; thus either
  the running time, or the output (or both) are random variables.

  A nondeterministic algorithm is an algorithm that can exhibit
  different behaviors on different runs, as opposed to a deterministic
  algorithm. There are several ways an algorithm may behave differently
  from run to run. A concurrent algorithm can perform differently on
  different runs due to a race condition. A probabilistic algorithm's
  behaviors depends on a random number generator. An algorithm that
  solves a problem in nondeterministic polynomial time can run in
  polynomial time or exponential time depending on the choices it makes
  during execution.

Are randomized algorithms and probabilistic algorithms the same concept?

If yes, are randomized algorithms just a kind of nondeterministic algorithms?

Non-deterministic algorithms are very different from probabilistic algorithms.

Probabilistic algorithms are ones using coin tosses, and working "most of the time". As an example, randomized variants of quicksort work in time $\Theta(n\log n)$ in expectation (and with high probability), but if you're unlucky, could take as much as $\Theta(n^2)$. Probabilistic algorithms are practical, and are used for example by your computer when generating RSA keys (to test that the two factors of your secret key are prime). Probabilistic algorithm which don't use any coin tosses are sometimes called "deterministic".

Non-deterministic algorithms are ones which "need a hint" but are always correct: they cannot be fooled by being given the wrong hint. As an example, here is a non-deterministic algorithm that factors an integer $n$: guess a factorization of $n$, and verify that all the factors are prime (there is a "fast-in-theory" deterministic algorithm for doing that). This algorithm is very fast, and rejects false hints. Most people think that randomized algorithms can't factor integers that quickly. Clearly this model of computation isn't realistic.

Why do we care about non-deterministic algorithms? There is a class of problems, known as NP, which consists of decision problems which have efficient non-deterministic algorithms. Most people think that the hardest problems in that class, the so-called NP-complete problems, do not have efficient deterministic (or even randomized) algorithms; this is known as the P vs NP question. Since many natural problems are NP-complete, it is interesting to know whether in fact they are not solvable efficiently, in the worst case (oftentimes, the instances which arise in practice are in fact solvable in reasonable time).

Randomized (polynomial time, boolean result) algorithms are in the RP computational complexity class, which is a subset of NP where non-deterministic (polynomial time, boolean result) algorithms reside and a superset of P where deterministic (polynomial time, boolean result) algorithms reside.

Subsetting complexity is about reducing problems in one set to another set. Thus RP ⊆ NP does exclude the possibility of randomized algorithms which are also non-deterministic because definitionally a superset contains the subset. Subset means every RP algorithm (or any RP-complete algorithm) can be reduced to some NP algorithm (or any NP-complete algorithm). P is a subset of RP because every problem in P can be reduced to a problem in RP where the amount of uncontrolled entropy is 0.

Tangentially, this is analogous to how every problem in NC (parallel computation) can be reduced to a problem in P by simulating the parallel computation in a reduction to a serial problem in P but it is not yet proven that the converse is true, i.e. that every problem in P is reducible to a problem in NC, nor proven not true, i.e. the implausible proof that a P-complete problem is not reducible to a problem in NC. It may be possible that there are problems that are inherently serial and can't be computed in parallel, but to prove that prove P ≠ NC seems to be implausible (for reasons too tangential to discuss in this answer).

More generally (i.e. not limited to boolean result types), randomized algorithms are distinguished from deterministic algorithms in that some of the entropy is externally sourced. Randomized algorithms are distinguished from non-deterministic algorithms because the entropy is bounded, and thus randomized (and not non-deterministic) algorithms can be proven to always terminate.

The unpredictability of nondeterministic algorithms is due to inability to enumerate all the possible permutations of the input entropy (which results in unpredictability of termination). The unpredictability of a randomized algorithm is due to inability to control all of the input entropy (which results in a unpredictability of an indeterminate result, although the rate of unpredictability can be predicted). Neither of these are statements about unpredictability of the correct answer to the problem, but rather the unpredictability manifests in the side-channel of termination and indeterminate result respectively. It seems many readers are conflating unpredictability in one area with unpredictability of the correct result, which is a conflation I never wrote (review the edit history).

It is key to understand that non-determinism is always (in any science or usage of the term) the inability to enumerate universal (i.e. unbounded) entropy. Whereas, randomization refers to accessing another source of entropy (in programs entropy other than and thus not under the control of the input variables) which may or may not be unbounded.

I added the following comment below the currently most popular answer to the other thread that asks a similar question.

  All sciences use the same definition of nondeterminism unified on the
  concept of unbounded entropy. Unpredictable outcomes in all sciences
  are due to the inability to enumerate a priori all possible outputs of
  an algorithm (or system) because it accepts unbounded states, i.e. NP
  complexity class. Specifying a particular input to observe whether it
  halts and noting that the result is idempotent is equivalent in other
  sciences to holding the rest of the entropy of the universe constant
  while repeating the same state change. Computing allows this entropy
  isolation, while natural sciences don't.

Adding some of the best comments to add clarification of my point about the only salient distinction between randomized and nondeterministic.

It is really quite elegant and easy to see the distinction, once you all stop muddling it by trying to describe it from an operational point-of-view instead of from the salient entropy point-of-view.

  @reinierpost everyone is conflating the difference between randomized
  and nondeterministic. This causes your comment to be muddled. The
  algorithm responds to the interaction of the input (variable) entropy
  and its source code (invariant) internal entropy. Nondeterminism is
  unbounded entropy. Invariant entropy can even be internally unbounded
  such as expanding the digits of
  π. Randomized is some of the
  entropy is not coupled to the input as defined (i.e. it may be coming
  from a system call to /dev/random, or simulated randomness e.g. NFA or
  a PRNG).

.

  @Raphael formal definition of non-deterministic finite automa (NFA) is
  finite input entropy (data: the 5-tuple). Thus every NFA can run on a
  deterministic Turing machine, i.e. doesn't require a nondeterministic
  Turing-complete machine. Thus NFAs are not in the class of
  nondeterministic problems. The notion of "nondeterminism" in NFA is
  that its determinism (while clearly present since every NFA can be
  converted to a DFA) is not explicitly expanded — not the same as
  nondeterminism of computation

.

  @Raphael the claimed "non-determinism" in NFAs is really randomness is
  sense of my definition of the distinction between randomness &
  nondeterminism. My definition is that randomness is where some of the
  entropy that is not under the control, knowledge (, or desired
  non-explicit expansion in the case of a NFA) of the input to the
  program or function. Whereas, true nondeterminism is the inability to
  know the entropy in any case, because it is unbounded. This is
  precisely what distinguished randomized from nondeterminism. So NFA
  should be an example of the former, not the latter as you claimed.

.

  @Raphael as I explained already, the notion of non-determinism in NFAs
  couple the non-deterministic with the finite entropy. Thus the
  non-determinism is a local concept of not expanding the determinism as
  a form of compression or convenience, thus we don't say NFAs are
  non-deterministic, rather they possess appearance of randomness to an
  oracle unwilling to compute the deterministic expansion. But it is all
  a mirage because it call be expanded deterministically bcz the entropy
  is not unbounded, i.e. finite.

Dictionaries are tools. Learn to use them.

  random
  adjective

  Statistics. of or characterizing a process of selection in which each
  item of a set has an equal probability of being chosen.

  being or relating to a set or to an element of a set each of whose
  elements has equal probability of occurrence

Thus randomization only requires that some of the input entropy be equiprobable, which is thus congruent with my definition that some of the input entropy not be controlled by the caller of the function. Notice that randomization does not require that the input entropy be undecidable w.r.t. to termination.

  In computer science, a deterministic algorithm is an algorithm which,
  given a particular input, will always produce the same output, with
  the underlying machine always passing through the same sequence of
  states.

  Formally, a deterministic algorithm computes a mathematical function;
  a function has a unique value for any input in its domain, and the
  algorithm is a process that produces this particular value as output.

  Deterministic algorithms can be defined in terms of a state machine: a
  state describes what a machine is doing at a particular instant in
  time. State machines pass in a discrete manner from one state to
  another. Just after we enter the input, the machine is in its initial
  state or start state. If the machine is deterministic, this means that
  from this point onwards, its current state determines what its next
  state will be; its course through the set of states is predetermined.
  Note that a machine can be deterministic and still never stop or
  finish, and therefore fail to deliver a result.

So this is telling us that deterministic algorithms must be completely determined by the input state of the function, i.e. we must be able to prove that the function will terminate (or not terminate) and that can't be undecidable. In spite of Wikipedia's muddled attempt to describe nondeterministic, the only antithesis to deterministic as defined above by Wikipedia, is are algorithms whose input state (entropy) is ill-defined. And the only way the input state can be ill-defined is when it is unbounded (thus can't be deterministically preanalyzed). This is precisely what distinguishes a nondeterministic Turing machine (and many real world programs which are written in common Turing complete languages such as C, Java, Javascript, ML, etc..) from deterministic TMs and programming languages such as HTML, spreadsheet formulas, Coq, Epigram, etc.. Wikipedia sort of alludes to this:

  In computational complexity theory, nondeterministic algorithms are
  ones that, at every possible step, can allow for multiple
  continuations (imagine a man walking down a path in a forest and,
  every time he steps further, he must pick which fork in the road he
  wishes to take). These algorithms do not arrive at a solution for
  every possible computational path; however, they are guaranteed to
  arrive at a correct solution for some path (i.e., the man walking
  through the forest may only find his cabin if he picks some
  combination of "correct" paths). The choices can be interpreted as
  guesses in a search process.

Wikipedia and others try to conflate randomization with nondeterminism, but what is the point of having the two concepts if you are going to not distinguish them eloquently?

Clearly determinism is about the ability to determine. Clearly randomization is about making some of the entropy equiprobable.

Including random entropy in the state of an algorithm doesn't necessary make it indeterminable. For example a PRNG can have the required equiprobable statistical distribution, yet also be entirely deterministic.

Conflating orthogonal concepts is what low IQ people. I expect better than that from this community!


How does a computer work? I have been a computer nerd for many many years. I can program in quite a few languages, and I can even build them.  I sat down with a buddy the other day and asked how a computer actually takes electricity and does something with it, and we just couldnt figure it out, and Google wasn't much help either.

I mean, how does a computer take a constant flow of electricity and turn it into 1's and 0's and then actually do something with those 1's and 0's like turn a light on for 15 seconds?

I understand gates (AND, OR, NOR, NAND, NOT) and a little about diodes, resistors and transistors, but I figured this would be the perfect place to have it explained in true laymens terms!

Can anybody point me in the right direction or give me a brief explanation?

This is a broad question that does not have an easy answer; it's a long way from electrons skittering along copper wires to rendering a website in Firefox. I will attempt to give you an overview from bottom to top and point you towards the right things to look up.

Encoding Numbers

The basic motivation is to compute things, as in doing arithmetics¹. The first thing to look at is how to represent numbers. There have been many approaches, using decimal or ternary and I think even octal systems, but in the end, binary won out. Now we know we have to build devices that deal with two values -- let's call them $0$ and $1$.

Note that there are also multiple ways to encode numbers in binary. After you build up your first processor, you realise advantages of doing things in certain ways. Popular examples are the two-complement and IEEE floats. For starters, restrict yourself to plain natural numbers.

Gates

Assume we use binary encoding. Think of how you learned adding in primary school and write down the same for binary numbers. As it turns out, the building blocks of Boolean algebra are already there for you; it is easy to build a basic adder (and other arithmetic functions) using logic gates.

How to build such gates is outside of the scope of computer science; eletrical engineering has provided multiple solution using e.g. tubes or transistors. Head over to Electrical Engineering Stack Exchange for questions on this.

Clock and State

Not all gates are equally fast and not all parts of a computation have the same number of gates. Therefore, we have to take extra care that individual operations do not overtake each other. It has proven useful to use a global clock; the result of a given network of gates is the state of the output wires at the end of the cycle (which may change wildly while the gates cascade towards their individual final states).

That means that results of one cycle may have to be stored until the next cycle starts, e.g. if you wire up loops. There are a number of basic elements you can use to varying effect, all build up from gates; some are called flip-flops. Those are also used to build registers, elements that store numbers for as many clock cycles as needed.

Architecture and Commands

Now you have a myriad of design choices to make. What arithmetic operations does your processor provide? What do your commands look like? It may be educational to look at the MIPS architecture whose early forms are easy compared to other designs. Have a look at the plans:

Original from http://ube.ege.edu.tr/~erciyes/CENG311

Essentially, it's fetching and and disassembling commands, a set of registers, an ALU and control. Commands encode which ALU operation to perform on which operands (by the number of the register they are held in), how to manipulate the program counter² or which register to load/store from/to memory³.

Further Considerations

By now you have a working processor in the modern sense, assuming you figured out how to build a memory and a way to feed it commands. On its way to a modern machine, many choices have to be made. Here are some:

Do you want a von Neumann architecture or would you rather keep commands and data separate?
Do you want regularity and simplicity or abstraction and space economy in your instructions?
Depending on your memory implementation, you might want to have caches.
Do you want your processor to handle multiple operations at the same time using a pipeline?
Are all operations (and memory addresses) available to all programs, or do you have an operating system?
How do you implement I/O?

Alternatives

The above is heavily influenced by how history turned out. In a different world with different minds, computers may work differently. In fact, there is a plenty of models of computation, some of which have advantages that make them useful as abstraction for real machines in many cases. There are also attempts to imitate the way our brains work, that is to enable neural computing, or more generally to exploit problem-solving and information-storing strategies observed in nature, most prominently DNA and quantum computing.

So maybe (hopefully?) the information above is all ancient history another 50 or 100 years from now.

All the fancy things we do with computers today are broken down into many small arithmetic tasks which the processor executes one by one.
If your model allows the program to manipulate control flow, this would be the memory address the processor gets the next instruction from. You can also conceive machines that only read a fixed set of instructions from, say, a tape. In fact, early implementations did that. No jumps meant no loops; a program was a completely unrolled/unfolded series of instructions depending on the data. Obviously, being able to use the same program for multiple input data is more powerful.
Assuming you have memory; your processor works fine without but can then only deal with so many values at once. Early computers did read in all their data from tapes and kept them in registers. There was no memory, let alone writable, persistent storage as we know it today.

There are several ways to do a delay function or convert the binary data to decimal data or signal strength. When you input value "15", the computer displays a bitmap image of the number 15 on the screen. This is actually the binary value, at the moment the binary code of your keyboard also sent to cpu. It will be parsing the data then turning the code to ALU (arithmetic logic unit) processing unit to convert it to a pulse to DAC chip. The analog signal is now being controlling the frequency (the frequency from khz to hz) of a flip-flop circuit. Now the frequency output will be directed to the RAM, and the cpu read RAM to match if the data is "1111". So that's 4 seconds.


Corresponding noun for "side-effect-free"? For functions or computations we have terms like:

Deterministic – Determinism
Pure – Purity

Now what is the correct corresponding noun for side-effect-free?

"Side-effect freeness"? "Side-effect freedom"? "Non-side-effective"?

A good rule of thumb for grammatical questions is, if it's so complicated that you need to ask, it's better to just rephrase the sentence.  For example, "Side-effect-freedom of the function guarantees X" is more simply and elegantly written, "Because the function is side-effect free, X is guaranteed" or even, "The function has no side-effects, so X is guaranteed."

Having said that, keywords for articles are expected to be noun phrases so that would be a place to use "side-effect freedom".

(By the way, "non-side-effective" is an adjective.)

You probably want "orthogonality". It seems to fit your definition exactly.


Why is NFA minimization a hard problem when DFA minimization is not? I know that we can minimize DFAs by finding and merging equivalent states, but why can't we do the same with NFAs?  I'm not looking for a proof or anything like that--unless a proof is simpler to understand.  I just want to understand intuitively why NFA minimization is so hard when DFA minimization is not.

For DFA there is a nice algebraic structure that determines which states can be equivalent, the Myhill-Nerode equivalence on strings is related to minimization of DFA.

For NFA the situation is complicated as there is no unique minimal NFA in general.

Here is an example for the finite language $\{ ab, ac, bc, ba, ca, cb\}$. The two automata are both state-minimal. The example is from the paper A note about minimal non-deterministic automata by Arnold, Dicky and Nivat.

This answer tries to express the fact that the two problems are "technically" different. See the answer by vzn for details how the problems differ in computational complexity.

This paper claims to provide minimized NFA in linear time: https://www.tandfonline.com/doi/abs/10.1080/03057920412331272153


Why is addition as fast as bit-wise operations in modern processors? I know that bit-wise operations are so fast on modern processors, because they can operate on 32 or 64 bits on parallel, so bit-wise operations take only one clock cycle. However addition is a complex operation that consists of at least one and possibly up to a dozen bit-wise operations, so I naturally thought it will be 3-4 times slower. I was surprised to see after a simple benchmark that addition is exactly as fast as any of the bit-wise operations(XOR, OR, AND etc). Can anyone shed light on this?

Addition is fast because CPU designers have put in the circuitry needed to make it fast.  It does take significantly more gates than bitwise operations, but it is frequent enough that CPU designers have judged it to be worth it.  See https://en.wikipedia.org/wiki/Adder_(electronics).

Both can be made fast enough to execute within a single CPU cycle.  They're not equally fast -- addition requires more gates and more latency than a bitwise operation -- but it's fast enough that a processor can do it in one clock cycle.  There is a per-instruction latency overhead for the instruction decoding and control logic, and the latency for that is significantly larger than the latency to do a bitwise operation, so the difference between the two gets swamped by that overhead.  AProgrammer's answer and Paul92's answer explain those effects well.

Let me correct a few things that were not mentioned that explicitely in your existing answers:

  I know that bitwise operations are so fast on modern processors, because they can operate on 32 or 64 bits on parallel,

This is true. Labeling a CPU as "XX" bit usually (not always) means that most of its common structures (register widths, addressable RAM etc.) are XX bits in size (often "+/- 1" or somesuch). But in regards to your question, you can safely assume that a CPU with 32 bit or 64 bit will do any basic bit operation on 32 or 64 bits in constant time.

  so bitwise operations take only one clock cycle.

This conclusion is not necessarily the case. Especially CPUs with rich instruction sets (google CISC vs. RISC) can easily take more than one cycle for even simple commands. With interleaving, even simples commands might break down into fetch-exec-store with 3 clocks (as an example).

  However addtion is a complex operation

No, integer addition is a simple operation; subtraction as well. It is very easy to implement adders in full hardware, and they do their stuff as instantaneously as basic bit operations.

  that consists of at least one and possibly up to a dozen bitwise operations, so I naturally thought it will be 3-4 times slower.

It will take up 3-4 times as many transistors, but in comparison to the big picture that is neglectible.

  I was surprised to see after a simple benchmark that addition is exactly as fast as any of the bitwise operations(XOR, OR, AND etc). Can anyone shed light on this?

Yes: integer addition is a bitwise operation (with a few more bits than the others, but still). There is no need to do anything in stages, there is no need for complicated algorithms, clocks or anything else.

If you wish to add more bits than your CPU architecture, you will incur a penalty of having to do it in stages. But this is on another level of complexity (programming language level, not assembly/machine code level). This was a common problem in the past (or today on small embedded CPUs). For PCs etc., their 32 or 64 bits are sufficient for the most common data types for this to start to become a moot point.


How does a Single Pass Compiler does parsing,analyzing and generating code all at once? I would like to know how a single pass compiler does parsing,analyzing and generating code all at once as said in P.14 of SIngle Pass Compilers.Is it possible to do all these at once since you can't generate an code without parsing or analyzing it which should be done earlier before producing the object code?

PROGRAM Demo
{
  INTEGER i;
  i= 4;
  WRITELN(i + 5);
}.

Line 1: enter the program name in the symbol table. Generate the program prologue.
Line 3: enter the declaration of variable i in the symbol table.
Line 4: evaluate the constant expression and generate code for the initialization of i.
Line 5: parse the function call and the argument expression. Generate code for the evaluation of the expression i + 5, the push on the stack and the call of the WRITELN predefined function.
Line 6: Generate the program epilogue.

Done.


Common Algorithms without Asymptotically Tight Bounds I can think of functions such as $n^2 \sin^2 n$ that don't have asymptotically tight bounds,  but are there actually common algorithms in computer science that don't have asymptotically tight bounds on their worst case running times?

This is somewhat of an anomaly, but yes - technically you could say that there are such algorithms. For example, consider an algorithm that checks whether a number in unary encoding is a prime - the first thing the algorithm can check is whether the number is even, this takes $O(n)$ time.

If it is, the algorithm rejects, otherwise it applies some primality test that takes $\omega(n)$ (at the very least by first converting it to binary, which takes $\theta(n\log n)$).

The point is that on every input of even length, the algorithm stops "quickly", so there is no asymptotically tight bound.

But this is clearly a stupid example.
One way to avoid this problem is to define the running time of an algorithm on inputs of length $n$ to be the worst case running time on inputs of length at most $n$. This way  you can get a tight bound.

A real-life example is any of the simple sorting algorithms. E.g. insertion sort takes $\Omega(n)$ and $O(n^2)$, and those bounds can't be improved (best case is already ordered, in which case it just checks it is ordered in linear time; worst case is reverse order, and the time is quadratic).


Word- or byte-addressable? Correct terminology Seemingly, a byte has established itself to be 8bit (is that correct?). RAM and NOR-flash can be normally accessed on a quite granular level, but it is up to the system architecture to determine if the smallest addressable unit is 8bit, 16bit or any other power of two bit number. Would the correct terminology be to call this word-addressable? Or asked differently, is a word the size of smallest addressable unit? Or is there some other term to describe this?

Are mabye nibble, byte, word, double word all variable in bit-length and only defined by the architecture? And it is therefore only coincidence that a byte is always 8 bit? E.g. someone could design some new CPU and memory type and define her byte to be 16bit?

Main question: What is the precise term for the smallest addressable memory block?

Side question: What is the antonym to this word I'm looking for (e.g. used in NAND-flash)? Page-addressable, block-addressable? Are both correct or is one inprecise?

From a computer architecture point of view, and with the caveat that nomenclature sometimes varies, especially when there is a family of related architectures which has evolved for a long time, or when the marketing department decides to that the usual terms have to used in another way (either to put the product in better light by using a bigger number, or to have a simple number to differentiate more or less related products).

A word has the size normally used for integer operations (often expressed as size of the integer or the general purpose registers, i.e. not address or data, internal or external buses, not address registers, not index registers).  A common issue is that when an architecture is an evolution of a previous one, one often keep the term word for the initial size and one use "double word" or "quad word" for what is a word if you look at the architecture in isolation.  Historically words have not always been a power of two (I know of sizes: 12, 16, 18, 24, 32, 36, 60, 64 and I don't think my knowledge is exhaustive).

Word addressable means that the memory is considered as arrays of words, and thus no smaller unit has an individual addresses.

A byte has various definitions.  The term was introduced to mean the unit used in character encoding at a time where multi-byte encoding didn't exist.  It is often used to means the smallest addressable unit for machine which are not word addressable (well as long at it is not one bit). I don't think those two definitions have ever given a different size. (nor a size different from 6 or 8 bits). For word addressable machine it often means some unit smaller than a word that the machine has some support for (for instance the PDP-10 -- a 36 bits word addressable computer -- had byte instructions which could manipulate any size from 1 to 35 or 36 bits).  Nowadays it is also often 8 bits.  Often several of those definitions are practically equivalent.

Byte addressable characterizes machines where the memory is considered as arrays of bytes in one of the above meaning.

AFAIK nibble has only been used for 4 bits quantities.

  E.g. someone could design some new CPU and memory type and define her byte to be 16bit?

Yes, but I'm not sure if it would make much sense to do so if one keeps the CA usage to use byte for something smaller than the word.  Having a word addressable 16-bit processor with no support for something smaller than a word may be a good choice for a special purpose processor.

  Secondarily, what is the antonym to this word I'm looking for? Page-addressable, block-addressable?

Bit-addressable, byte-addressable and word-addressable are the only terms I've seen use.  It doesn't make much sense to address only units bigger than the word at the architectural level.  Word-addressable is nowadays only used for special purpose processors such as DSP.  I don't think bit-addressability has been used for anything else than special purpose one excepted the IBM Stretch.

About your new main question

  What is the precise term for the smallest addressable memory block?

I know of none used in Computer Architecture (byte has been used for something smaller in word adressable machines), but is the definition used by C for byte.

Our computer system used by default Byte addressable memory. Its one cell is pointing to 8-bits information. And cell size does not depend on the processor length.
In word addressable memory one cell is pointing to one word information, but the word length depends on the processor length.
When we use words addressable memory than its creates an ambiguity. So our computer use by default byte addressable memory.


Are there current benchmarks for algorithms solving Travelling Salesman? I'm researching the travelling salesman problem and looking for data regarding the current state of affairs regarding solutions and performance. So far the only data I've states that the current record for optimality is held by 'Concorde' which found a solution for a graph containing 85,900 cities. I've also found benchmarking data for Concorde, as well as data pertaining to the current best performance for a world map.

Is this data still accurate? It looks like a lot of this hasn't been updated since the early 2000s.

TSP has many variants under study eg Euclidean vs noneuclidean, exact vs approximations, interrelated but also at times separate threads of research. heres a recent nontechnical survey from early 2013 on TSP by an expert mathematical writer Klarreich, Computer Scientists Take Road Less Traveled that sheds some insight on recent improvements/ theoretical advances & can be mined for some refs. an old approximation algorithm by 1976 Christofides has been unrivalled for decades but some minor theoretical improvements have been made recently. as indicated in the article some theoretical TSP research that is not nec (practically) implemented veers into what is referred to as Galactic algorithm territory by expert RJ Lipton.

as a more applied resource/ angle, also a leading group/ site for benchmarking is DIMACS, NSF center for discrete math & CS, which also has a TSP page with algorithms/ benchmarks updated 2013.


Is Category Theory useful for learning functional programming? I'm learning Haskell and I'm fascinated by the language. However I have no serious math or CS background. But I am an experienced software programmer.

I want to learn category theory so I can become better at Haskell.

Which topics in category theory should I learn to provide a good basis for understanding Haskell?

In a previous answer in the Theoretical Computer Science site, I said that category theory is the "foundation" for type theory.  Here, I would like to say something stronger.  Category theory is type theory.  Conversely, type theory is category theory.  Let me expand on these points.

Category theory is type theory

In any typed formal language, and even in normal mathematics using informal notation, we end up declaring functions with types $f : A \to B$.  Implicit in writing that is the idea that $A$ and $B$ are some things called "types" and $f$ is a "function" from one type to another.  Category theory is the algebraic theory of such "types" and "functions".  (Officially, category theory calls them "objects" and "morphisms" so as to avoid treading on the set-theoretic toes of the traditionalists, but increasingly I see category theorists throwing such caution to the wind and using the more intuitive terms: "type" and "function".  But, be prepared for protests from the traditionalists when you do so.)

We have all been brought up on set theory from high school onwards.  So, we are used to thinking of types such as $A$ and $B$ as sets, and functions such as $f$ as set-theoretic mappings.  If you never thought of them that way, you are in good shape.  You have escaped set-theoretic brain-washing.  Category theory says that there are many kinds of types and many kinds of functions.  So, the idea of types as sets is limiting.  Instead, category theory axiomatizes types and functions in an algebraic way.  Basically, that is what category theory is.  A theory of types and functions.  It does get quite sophisticated, involving high levels of abstraction.  But, if you can learn it, you will acquire a deep understanding of types and functions.

Type theory is category theory

By "type theory," I mean any kind of typed formal language, based on rigid rules of term-formation which make sure that everything type checks.  It turns out that, whenever we work in such a language, we are working in a category-theoretic structure.  Even if we use set-theoretic notations and think set-theoretically, still we end up writing stuff that makes sense categorically.  That is an amazing fact.

Historically, Dana Scott may have been the first to realize this.  He worked on producing semantic models of programming languages based on typed (and untyped) lambda calculus.  The traditional set-theoretic models were inadequate for this purpose, because programming languages involve unrestricted recursion which set theory lacks.  Scott invented a series of semantic models that captured programming phenomena, and came to the realization that typed lambda calculus exactly represented a class of categories called cartesian closed categories.  There are plenty of cartesian closed categories that are not "set-theoretic".  But typed lambda calculus applies to all of them equally.  Scott wrote a nice essay called "Relating theories of lambda calculus" explaining what is going on, parts of which seem to be available on the web.  The original article was published in a volume called "To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism", Academic Press, 1980.  Berry and Curien came to the same realization, probably independently.  They defined a categorical abstract machine (CAM) to use these ideas in implementing functional languages, and the language they implemented was called "CAML" which is the underlying framework of Microsoft's F#.

Standard type constructors like $\times$, $\to$, $List$ etc. are functors.  That means that they not only map types to types, but also functions between types to functions between types.  Polymorphic functions preserve all such functions resulting from functor actions.  Category theory was invented in 1950's by Eilenberg and MacLane precisely to formalize the concept of polymorphic functions.  They called them "natural transformations", "natural" because they are the only ones that you can write in a type-correct way using type variables.  So, one might say that category theory was invented precisely to formalize polymorphic programming languages, even before programming languages came into being!

A set-theoretic traditionalist has no knowledge of the functors and natural transformations that are going on under the surface when he uses set-theoretic notations.  But, as long as he is using the type system faithfully, he is really doing categorical constructions without being aware of them.

All said and done, category theory is the quintessential mathematical theory of types and functions.  So, all programmers can benefit from learning a bit of category theory, especially functional programmers.  Unfortunately, there do not seem to be any text books on category theory targeted at programmers specifically.  The "category theory for computer science" books are typically targeted at theoretical computer science students/researchers.  The book by Benjamin Pierce, Basic category theory for computer scientists is perhaps the most readable of them.

However, there are plenty of resources on the web, which are targeted at programmers.  The Haskellwiki page can be a good starting point.  At the Midlands Graduate School, we have lectures on category theory (among others).  Graham Hutton's course was pegged as a "beginner" course, and mine was pegged as an "advanced" course.  But both of them cover essentially the same content, going to different depths.  University of Chalmers has a nice resource page on books and lecture notes from around the world.    The enthusiastic blog site of "sigfpe" also provides a lot of good intuitions from a programmer's point of view.

The basic topics you would want to learn are:

definition of categories, and some examples of categories
functors, and examples of them
natural transformations, and examples of them
definitions of products, coproducts and exponents (function spaces), initial and terminal objects.
adjunctions
monads, algebras and Kleisli categories

My own lecture notes in the Midlands Graduate School covers all these topics except for the last one (monads).  There are plenty of other resources available for monads these days.  So that is not a big loss.

The more mathematics you know, the easier it would be to learn category theory.  Because category theory is a general theory of mathematical structures, it is helpful to know some examples to appreciate what the definitions mean.  (When I learnt category theory, I had to make up my own examples using my knowledge of programming language semantics, because the standard text books only had mathematical examples, which I didn't know anything about.)  Then came the brilliant book by Lambek and Scott called "Introduction to categorical logic" which related category theory to type systems (what they call "logic").  It is now possible to understand category theory just by relating it to type systems even without knowing a lot of examples.  A lot of the resources I mentioned above use this approach to explain category theory.

Category theory is a very sophisticated branch of mathematics and mastering it will unify most of your previous learnings by making them instances of same abstract objects. So it is very useful and very intuitive. But it is vast and broad, and you will find yourself in a plenty of new concepts that will don't even know which one is suitable for your needs and which one you should skip. So your purposeful approach needs choice among concepts, otherwise mastering in it inevitably needs long time and is really not a self study domain.

By the way, I suggest a very well start point for your purpose to be here.


How do modern Operating Systems detect process starvation? So first off do the modern operating systems like windows and linux have a method for detecting starvation? if not, why? and if they do, then how are they going to detect starvation of a process? (this was a question in our exam)

my take was this so correct me if this is not good or not possible:

i said we should implement a linked list of waiting processes (that are waiting for a resource or etc) then we periodically run a function(using interrupts) which checks this list and we have a variable for each process and we increase that everytime, when it reaches certain point then we would know its starving(but i still dont know how to know this "certain point")

so is this correct? if so then how can we know this "certain point"? ( I suppose one way is just look at the statistic of average waiting time of processes and do a little math?)

if not, what is your solution?

Inline with @chi 's comment;  lets say process "x" gets starved in linux or windows, then for example if we are in the windows, wouldn't we get an error message saying the process "x" is not responding? Approximately no.

Now let's assume we want to detect process "x",before starvation nor aging;we have to read it's  arrival time, burst time,process id, priority from the text file and calculate the average waiting time and show the central processing unit utilization of each cycle,for instance;

Time 1 process X arrives

Time 2 process X runs

Time  3 process B arrives

Time 4 process X finishes..........,randomly.

Hope this can give you a little bit of insight.


Can a list with $\mathcal{O}(1)$ access have an insertion complexity better than $\mathcal{O}(n)$? It seems intuitive that there's no list data structure which has $\mathcal{O}(1)$  worst case time complexity for random access and a worst case complexity better than $\mathcal{O}(n)$ for insertion: if insertion is allowed to affect only a small part of the list, then there's no way for it to always keep the entire list in a structure that allows for constant time element access.

Is there any proof (or counterexample) of this?

Yes, you can have both as fast as possible random access and faster-than-full-rebuild insertion time.

I assume you know how dynamically growing arrays work. Also, I assume you know how to make them work in $O(1)$ worst-case. These techniques allow us to focus on the problem for lists of limited size only.

Let $n$ be the maximal size (capacity) of the list. Let’s divide the list into $O(\sqrt{n})$ blocks of equal size $B$ (which is $O(\sqrt{n})$ too). Let also $b_j$ denote a cyclic shift of the $j$-th block.

When you need to access $i$-th element of the list, you calculate its position as follows in $O(1)$:

$$f(i) = (b_j + i \mod B) + B \times j$$

where $j = \lfloor \frac{i}{B} \rfloor$.

When you need to insert something into $i$-th position, you first make a cyclic shift of everything from $j$-th block to the end:

Decrement all $b$ values starting from $j$.
Swap the elements on the boundaries of consequtive blocks, so that every element is in its right place.
Then you fix $j$-th block by rebuilding it from scratch.

This gives you $O(\sqrt{n})$ insertion complexity.

As accessing to an element is in $O(1)$, it would be something like an array. And, if this assumption is true, your discussion would be near the concept of "Dynamic Array". It's insertion to the array is $O(1)$ and amortized cost of $n$ insertion to the data structure is $O(n)$.
It might be helpful for what you want to reach.


Is Green's the best 16-input sorting network so far? Every paper says that Green's construction is the best 16-input sorting
network as for now.

But why does Wikipedia says: "Size, lower bound: 53"?

I thought "lower bound" meant:"If there exists at least an algorithm that can...". Am I wrong?

No, a lower bound means that somebody has proved that anything smaller than 53 is impossible. That doesn't mean that a 53-gate network is known or even necessarily possible; just that there cannot be a smaller one than that.

there are relatively new results in this area using SAT solvers and some new theory. optimal networks up to n=16 are now known/ constructed. this paper explains the techniques and following is a link given in the paper to optimal sorting network constructions up to n=16. (the paper does not mention Greens construction in particular but it does reference Knuth and maybe that is enough to correlate precisely if Knuth refers to Greens construction.)

Optimal-Depth Sorting Networks / Bundala et al
https://www.cs.bgu.ac.il/~mcodish/Papers/Appendices/SortingNetworks/


Why we still need Short Term Memory if Long Term Memory can save temporary data? If RAM is a short term memory and SSD is a long term memory, why don't microarchitecture of computer nowadays use SSD or another long term memory for saving temporary data like hidden variable for programming?
If it's about speed, then SSD can improve its speed, is it possible that SSD will become faster than RAM at some point?
If SSD has address for memory location and data for
opcode/instruction/operand like RAM, then will it possibly act like RAM?

There's two simple reasons, one fundamental and one related to our current technology. First the technical one: volatile storage is (generally) faster than non-volatile storage. It has fewer requirements - it only needs to store the data for a short while until it gets refreshed, so it's not a surprise that it often is faster.
But the fundamental reason is that memory gets slower to access the bigger it is. This is why modern architectures don't just have 'RAM' and 'disk', there's layers upon layers of increasing size memory, with only the topmost layer being non-volatile:

CPU registers
L1 cache
L2 cache
L3 cache
RAM itself
Cache on the disk micro-controller
The disk itself

And also, programs designed today rather expect there to be a difference between 'things I want to persist' and 'things that I want to go away on exit'.  If that suddenly changed to 'everything persists' then we'd have to code a little differently.
Not to mention concurrency. Suppose I write a program that has a variable 'foo'.  Now I'm running 17 copies of that program.  Clearly I don't want all of those variables to resolve to the same persistent storage location; we need process-local storage.  So there are 17 different mappings of my address space to persistent storage.  Now those 17 processes exit, but I suppose that the 17 instances of 'foo' still exist in this new 'everything persists' regime.  Will they ever be useful again?   I start a new instance of the program.  Which of those 17 old instances does my new 'foo' map to?
We can imagine that the persistent copy is erased on program exit, but then we're using persistent storage to simulate ephemeral storage, which seems like adding complication for no gain.
Conclusion: As a programmer, I want ephemeral storage. And since I want that, there's little point in mapping it to persistent storage.


What is the optimal way to cut B chocolate bars to share equally between N people? What is the optimal way to cut B chocolate bars to share equally between N people?

Here is an example of different cuts for B = 5 chocolate bars and N = 6 people.

Strategy 1: cut each chocolate bar in 6 equal parts and, then, give 5 parts for each person. Number of cuts: 5 x 5 = 25.

Strategy 2: cut 3 bars in 2 equal parts and cut 2 parts in 3 equal parts and, then, give 1/2 bar and 1/3 bar for each person. Number of cuts: 3 x 1 + 2 x 2 = 7.

What is the optimal solution for the general problem?

Thanks, Humberto.

If optimal means having less cuts, can do this:

1. Line the chocolate bar up.
   [bar 0][bar 1][bar 2]

2. Treat that as a big bar.
   [big bar            ]

3. Divide the big bar equally.

Only about N cuts needed (if B < N)

If B > N, just give everyone equal number of bars. Then divide the remaining bars with the above algorithm.

Or 1 cut:

[bar 0]
  [bar 1]
    [bar 2]

cut vertically once.

I am sure there might be easier way to line it up... if optimal means that we don't need to use a ruler to measure the chocolates in real life.

Considering the minimum common multiple of N and B: mcm, it is the worse case for the given N and B. (You will find no N+B where the optimal cut is worse than its MCM)

  e.g. B=5, N=6 -> mcm = 30

The value of mcm can be factorized into prime numbers (factors). Each of the mcm little chunks could be grouped using those values and minimize the number of cuts.

Each factor can be used or not depending of your custom rules, in this case, allowing only chunks of equal size for all N persons.

Example of algorithm:

orderFactorsDecreasing(factors)
remainingB = B
foreach (f in factors)
{
    while ( acceptChunkGrouping( f ) ) // yes, can be flattened easily.
    {
        distributeToEachPerson( f*B/mcm )
        remainingB -= N *  (f*B/mcm )
    }
}

  Following your example of B=5, N=6, mcm=30:  factorization of 30 is:
  (1), 2, 3, 5, 6:

  Chunks of 6*(1/6) -> rejected as there are no N x (1/6) chunks available.
  Chunks of 5*(1/6) -> rejected as there are no N x (5/6) chunks available.
  Chunks of 3*(1/6) -> Allowing N x (3/6) -> remaining 2 bars.
  Chunks of 2*(1/6) -> Allowing N x (2/6) -> remaining 0 bars.
  chunks of 1*(1/6) -> rejected as there are no N x (1/6) chunks available.

To force each person having chunks of the same size, the test could be:

var chunksPerBar = floor(1 / (factor*B/mcm))
if (chunksPerBar*remainingB >= N) then acceptTheFactor
else rejectTheFactor

  An other example:

  B=26, N=4;
  mcm = 52;
  factors: 13, 2, (2), 1

  13 is rejected.
  2 is accepted, giving 6 full bars to each N persons.
  1 is accepted, giving 0.5 bars to each N persons.

  Each person get 6 full bars + 1/2 bar.


Is subset sum with a fixed target sum NP-complete? I've read that subset sum is NP-complete. What happens when I change the decision problem to look for a  constant number? So the decision problem would look like this:

  Input:
  A collection of nonnegative integers A and a nonnegative integer b,

  Output:
  Boolean value indicating whether some subset of
  the collection sums to 10

Would this still be NP-complete? I don't believe you would be able to reduce every other NP-complete problem to it.

We can throw away all zeroes in $A$. If a subset of $A$ sums to $10$, then this subset contains at most $10$ elements. There are at most $10|A|^{10}$ such non-empty subsets, so we can go over all of them in polynomial time.

Subset sum problem with only one number is probably not NP-complete, because there is a polynomial algorithm that solves this problem.
If it is NP-complete, then P=NP.


How to prove greedy algorithm is correct I have a greedy algorithm that I suspect might be correct, but I'm not sure.  How do I check whether it is correct?  What are the techniques to use for proving a greedy algorithm correct?  Are there common patterns or techniques?

I'm hoping this will become a reference question that can be used to point beginners to; hence its broader-than-usual scope. Please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!

Ultimately, you'll need a mathematical proof of correctness.  I'll get to some proof techniques for that below, but first, before diving into that, let me save you some time: before you look for a proof, try random testing.
Random testing
As a first step, I recommend you use random testing to test your algorithm.  It's amazing how effective this is: in my experience, for greedy algorithms, random testing seems to be unreasonably effective.  Spend 5 minutes coding up your algorithm, and you might save yourself an hour or two trying to come up with a proof.
The basic idea is simple: implement your algorithm.  Also, implement a reference algorithm that you know to be correct (e.g., one that exhaustively tries all possibilities and takes the best).  It's fine if your reference algorithm is asymptotically inefficient, as you'll only run this on small problem instances.  Then, randomly generate one million small problem instances, run both algorithms on each, and check whether your candidate algorithm gives the correct answer in every case.
Empirically, if your candidate greedy algorithm is incorrect, typically you'll often discover this during random testing.  If it seems to be correct on all test cases, then you should move on to the next step: coming up with a mathematical proof of correctness.
Mathematical proofs of correctness
OK, so we need to prove our greedy algorithm is correct: that it outputs the optimal solution (or, if there are multiple optimal solutions that are equally good, that it outputs one of them).
The basic principle is an intuitive one:
Principle: If you never make a bad choice, you'll do OK.
Greedy algorithms usually involve a sequence of choices.  The basic proof strategy is that we're going to try to prove that the algorithm never makes a bad choice.  Greedy algorithms can't backtrack -- once they make a choice, they're committed and will never undo that choice -- so it's critical that they never make a bad choice.
What would count as a good choice?  If there's a single optimal solution, it's easy to see what is a good choice: any choice that's identical to the one made by the optimal solution.  In other words, we'll try to prove that, at any stage in the execution of the greedy algorithms, the sequence of choices made by the algorithm so far exactly matches some prefix of the optimal solution.  If there are multiple equally-good optimal solutions, a good choice is one that is consistent with at least one of the optima.  In other words, if the algorithm's sequence of choices so far matches a prefix of one of the optimal solutions, everything's fine so far (nothing has gone wrong yet).
To simplify life and eliminate distractions, let's focus on the case where there are no ties: there's a single, unique optimal solution.  All the machinery will carry over to the case where there can be multiple equally-good optima without any fundamental changes, but you have to be a bit more careful about the technical details.  Start by ignoring those details and focusing on the case where the optimal solution is unique; that'll help you focus on what is essential.
There's a very common proof pattern that we use.  We'll work hard to prove the following property of the algorithm:
Claim: Let $S$ be the solution output by the algorithm and $O$ be the optimum solution.  If $S$ is different from $O$, then we can tweak $O$ to get another solution $O^*$ that is different from $O$ and strictly better than $O$.
Notice why this is useful.  If the claim is true, it follows that the algorithm is correct.  This is basically a proof by contradiction.  Either $S$ is the same as $O$ or it is different.  If it is different, then we can find another solution $O^*$ that's strictly better than $O$ -- but that's a contradiction, as we defined $O$ to be the optimal solution and there can't be any solution that's better than that.  So we're forced to conclude that $S$ can't be different from $O$; $S$ must always equal $O$, i.e., the greedy algorithm always outputs the correct solution.  If we can prove the claim above, then we've proven our algorithm correct.
Fine.  So how do we prove the claim?  We think of a solution $S$ as a vector $(S_1,\dots,S_n)$ which corresponds to the sequence of $n$ choices made by the algorithm, and similarly, we think of the optimal solution $O$ as a vector $(O_1,\dots,O_n)$ corresponding to the sequence of choices that would lead to $O$.  If $S$ is different from $O$, there must exist some index $i$ where $S_i \ne O_i$; we'll focus on the smallest such $i$.  Then, we'll tweak $O$ by changing $O$ a little bit in the $i$th position to match $S_i$, i.e., we'll tweak the optimal solution $O$ by changing the $i$th choice to the one chosen by the greedy algorithm, and then we'll show that this leads to an even better solution.  In particular, we'll define $O^*$ to be something like
$$O^* = (O_1,O_2,\dots,O_{i-1},S_i,O_{i+1},O_{i+2},\dots,O_n),$$
except that often we'll have to modify the $O_{i+1},O_{i+2},\dots,O_n$ part slightly to maintain global consistency.  Part of the proof strategy involves some cleverness in defining $O^*$ appropriately.  Then, the meat of the proof will be in somehow using facts about the algorithm and the problem to show that $O^*$ is strictly better than $O$; that's where you'll need some problem-specific insights.  At some point, you'll need to dive into the details of your specific problem.  But this gives you a sense of the structure of a typical proof of correctness for a greedy algorithm.
A simple example: Subset with maximal sum
This might be easier to understand by working through a simple example in detail.  Let's consider the following problem:
Input: A set $U$ of integers, an integer $k$
Output: A set $X \subseteq U$ of size $k$ whose sum is as large as possible
There's a natural greedy algorithm for this problem:

Set $X := \emptyset$.
For $i := 1,2,\dots,k$:

Let $x_i$ be the largest number in $U$ that hasn't been picked yet (i.e., the $i$th largest number in $U$).  Add $x_i$ to $X$.

Random testing suggests this always gives the optimal solution, so let's formally prove that this algorithm is correct.  Note that the optimal solution is unique, so we won't have to worry about ties.  Let's prove the claim outlined above:
Claim: Let $S$ be the solution output by this algorithm on input $U,k$, and $O$ the optimal solution.  If $S \ne O$, then we can construct another solution $O^*$ whose sum is even larger than $O$.
Proof. Assume $S \ne O$, and let $i$ be the index of the first iteration where $x_i \notin O$. (Such an index $i$ must exist, since we've assumed $S \ne O$ and by the definition of the algorithm we have $S=\{x_1,\dots,x_k\}$.)  Since (by assumption) $i$ is minimal, we must have $x_1,\dots,x_{i-1} \in O$, and in particular, $O$ has the form $O=\{x_1,x_2,\dots,x_{i-1},x'_i,x'_{i+1},\dots,x'_n\}$, where the numbers $x_1,\dots,x_{i-1},x'_i,\dots,x'_n$ are listed in descending order.  Looking at how the algorithm chooses $x_1,\dots,x_i$, we see that we must have $x_i > x'_j$ for all $j\ge i$.  In particular, $x_i > x'_i$.  So, define $O^* = O \cup \{x_i\} \setminus \{x'_i\}$, i.e., we obtain $O^*$ by deleting the $i$th number in $O$ and adding $x_i$.  Now the sum of elements of $O^*$ is the sum of elements of $O$ plus $x_i-x'_i$, and $x_i-x'_i>0$, so $O^*$'s sum is strictly larger than $O$'s sum.  This proves the claim. $\blacksquare$
The intuition here is that if the greedy algorithm ever makes a choice that is inconsistent with $O$, then we can prove $O$ could be even better if it was modified to include the element chosen by the greedy algorithm at that stage.  Since $O$ is optimal, there can't possibly be any way to make it even better (that would be a contradiction), so the only remaining possibility is that our assumption was wrong: in other words, the greedy algorithm will never make a choice that is inconsistent with $O$.
This argument is often called an exchange argument or exchange lemma.  We found the first place where the optimal solution differs from the greedy solution and we imagined exchanging that element of $O$ for the corresponding greedy choice (exchanged $x'_i$ for $x_i$).  Some analysis showed that this exchange only can only improve the optimal solution -- but by definition, the optimal solution can't be improved.  So the only conclusion is that there must not be any place where the optimal solution differs from the greedy solution.  If you have a different problem, look for opportunities to apply this exchange principle in your specific situation.

if you are not able to prove and it's getting difficult then just find one test case that contradicts your greedy approach and you are good to go


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.

You could start off with Java at http://www.learnjavaonline.org/. And once you are clear with syntax of Java, you could try http://codingbat.com/java. Its got some really good programming exercises.


Building a tree with the heap property from an array and preserving its order How efficiently can I build a binary tree satisfying the heap property from an array and such that the inorder traversal of the tree is the original array?

For example, if I have:

  2 1 5 6 2 3

I want to build:

  1
 / \
2   2
   / \
  5   3
   \
    6

Because it has the heap property and its inorder is the original array 2 1 5 6 2 3.

An O(n)-time algorithm for the problem has been published by Gabow et al. (1984) in the context of "Cartesian trees": https://dl.acm.org/doi/10.1145/800057.808675
As pointed out above by Raphael, there is a close relationship to treaps.
You may also want to visit the corresponding Wikipedia entry: https://en.wikipedia.org/wiki/Cartesian_tree

Just refere wiki: https://en.wikipedia.org/wiki/Binary_heap
it a trivial algoritm using sift down operation.
 But advise you to do in on your own. Should be simple.
Why do you need unbalances tree by the way? Should work for unbalances, I think.


Give a grammar to show whether a language is regular or context-free I have to generate a grammar for the language $L = \{ w \in \{ a, b\}^* \mid |w| \in 2\mathbb{N},  w \neq w^R\}$ and give the type of the language.

I've generated the grammar

$\qquad \begin{align}
  S &\to aSa \mid bSb \mid aAb \mid bAa \\
  A &\to abA \mid baA \mid aaA \mid bbA \mid \varepsilon
\end{align}$

This grammar is a context free grammar. I now can say that $L$ is a context free language. But how can I say for sure that this language isn't regular ?

Regular languages are closed under complement and intersection. The complement of $L$, intersected with the regular $\{w : |w| \equiv 0 \pmod{2}\}$ is the language of even palindromes. If you must, you can easily show that it is not regular using pumping lemma.

Language categories are sets, and the context-free language set contains the regular language set. In other words, every regular language is context-free. It's useful to know that context-free contains LR, which contains LL, which contains regular.

Your language is regular because its definition conforms to the regular definition (strings that can be formed over an alphabet by applying the operations of concatenation, union, and closure).

There's an algorithm for converting a regular definition into a grammar. I believe that the algorithm would produce the following grammar for your language:

S -> aS
S -> bS
S -> ε

I'm not quite sure that the grammar you posted corresponds to the regular language definition. It's better to stick to proven stuff.


HandyAR finger tip detection and tracking I am reading this paper Handy AR.

As suggested I am adding certain quotes from paper to get basic idea of what is it about :

Intro

  In this paper, we present and evaluate a method to use a
  user’s bare outstretched hand in the same way a cardboard AR
  marker would be used, enabling spontaneous tangible user interfaces
  in mobile settings

Steps:

Adaptive Hand Segmentation

  Given a captured frame, every pixel is categorized to be
  either a skin-color pixel or a non-skin-color pixel. An adaptive
  skin color-based method 17 is used to segment the hand
  region. According to the generalized statistical skin color
  model 14, each pixel is determined to be in the hand region
  if the skin color likelihood is larger than a constant threshold.
  In order to adapt the skin color model to the illumination
  change, a color histogram of the hand region is learned for
  each frame and accumulated with the ones from the previous
  n frames (n = 5 works well in practice). Then the probability
  of skin color is computed by combining the general skin
  color model and the adaptively learned histogram.

Accurate Fingertip detection

  Fingertips are detected from the contour of a hand using a
  curvature-based algorithm similar to the one described in [2].
  We then fit the curvature points to ellipses in order to increase
  the accuracy. The curvature of a contour point is measured on
  multiple scale levels in order to detect fingertips with various
  sizes as follows: The points with higher curvature values than
  a threshold (on any scale level) are selected as candidates for
  fingertips.
  Since the detection algorithm may produce false positives
  of fingertips for initial detection, we choose the most frequently
  detected points above the center of the hand for a
  certain number of consecutive frames as our final fingertips.
  Thus, for initial detection, the hand has to be held fingers
  up, which is the most convenient and by far the most common
  pose anyway. After fingertips have been detected, we
  eliminate false positives by tracking a successful configuration
  over time.

FingerTip Tracking

  Once fingertips are detected, we track them based on
  matching the newly detected fingertips to the previously
  tracked fingertips. Similar to 21, we track the fingertip trajectory
  by a matching algorithm that minimizes the displacement
  of pairs of fingertips over two frames. In addition, we
  use our knowledge about the centroid of the hand blob to effectively
  handle large movements of the hand as follows: The
  matching cost is minimized as the formula I mentioned below.

I have a couple of doubts in this :
1. In the 2nd paragraph of the 2nd points of steps:

  After fingertips have been detected, we
  eliminate false positives by tracking a successful configuration
  over time.

What does 'successful configuration over time' mean?
If we already are tracking a successful configuration , then why are there false positives.

2.In the next section, Fingertrip tracking has been explained. From what I understood , it has two parts

Using a matching algorithm
Using centroid to effectively handle large movenments.

My doubt is in the second part, I am not able to understand properly how does it handle large movenments and also the correctness proof of that statement.

Formula for fi+1

where fi fi+1 are the sets of N fingertips at the ith and
i + 1th frame and
 Ci , Ci+1 are centroids at ith and i + th frame.

Citation -

I got this from 1 paper published by Taehee Lee, Tobias Hollerer in 2007 11th IEEE International Symposium on Wearable Computers

Handy AR

What does 'successful configuration over time' mean?...  why are there false positives.
I am not able to understand properly how does it handle large movements

they are repeatedly scanning a similar form, the "hand blob", so any outliers from the usual successful input will hopefully be ignored. (maybe if someone nearby passes you something and it thinks their hand is yours for a few frames)

the paper says they register the "hand blob" or centroid of skin color as an easier tracking target for large movements. the "one time calibration" is probably about where your hand is, and it's predominant shade, in relation to the device. then it makes sure the fingers are there and orientates using the thumb. there is no difference to the formula for large movements except where Ci+1 actually is compared to Ci.

I really am looking forward to real time interaction with augmented reality.
are there many more papers you know of like this? id love to read them too.

Edit: hello again raphael.  this is someone of my lvl of understanding and the attempt has been made to fill all of the exceedingly strict criteria for a simple question. this guy is interested, like many are, but has been told off and deleted by you lot before. i can tell.


Is the set of codes of Deterministic Finite-State Automata a regular language? Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is a regular language?

For example for Turing machines, the set of codes of Turing machines over a fixed alphabet is decidable, and we can speak of decidable sets of Turing machines (through their codes).

Of course we can also speak of regular sets of DFA's (through their codes). Is the set of all DFA's regular in this sense?

This answer is, in a sense, a completely cheating approach, but it is indeed possible to encode all DFAs as strings.

We can write out a DFA by writing out its transition table.  We can write out the transition table using just 0s and 1s as follows: first, write out a number of 1s equal to the number of states, then a 0.  Then, write out a number of 1s equal to the number of symbols in the alphabet, then a zero.  Then, write out each row of the transition table by writing out each entry as a number of 1s indicating which state should be transitioned into, then a 1.

Now, this particular encoding of a DFA is not regular.  However, what we can do is the following.  Consider the set of all such encodings.  We can then order them in length-lex order, and then can number the DFAs produced this way 0, 1, 2, 3, 4, ..., etc. based on their ordering.  In this case, we now have a bijection between $\mathbb{N}$ and the set of all DFAs.  From there, we can then consider the regular language consisting of all natural numbers written out in binary.  This set is definitely regular; here's a regular expression for it:

  0 | 1(0|1)*

So we now have a regular language consisting of encodings of DFAs.  The encoding is not at all easy to work with - you'd have to start listing off all encodings of DFAs until you found the one you were looking for - but mathematically it is well-defined.

I have no idea, but my intuition is that you couldn't.
You are basically asking if you can implement a regexp matcher with a push-down automaton, and I don't think you can... The regexp can be arbitrarily complex, so there is no way you can store all the state necessary in the push-down automaton states, so you'll need to use the push-down to store the state of where you are in the regexp (and/or the word)... And the problem with the push-down, is that you won't be able to do backtracking if you take a wrong turn in the regexp (in a normal automaton you have a state covering for each wrong turn possible, because all the possible combinations are known when you determine the number of states for the automaton, but I think that doing this in the push-down would require backtracking, and I don't think you can implement that)...


how to calculate time complexity of non terminating loops I'm studying about data structures and algorithms in that Time complexity  and calculating time complexity of the programs.

I just wondered that how to calculate time complexity of  non terminating loops such as infinite loops

If the program runs forever, its running time is infinite.  So, if it always enters an infinite loop, its running time is infinite.

This is a degenerate case.  Normally we focus only on algorithms that are certain to terminate (but see footnote).

See also How to come up with the runtime of algorithms? and Is there a system behind the magic of algorithm analysis?.

Footnote: When studying randomized algorithms, this gets relaxed a bit, and we frequently look at algorithms that in principle could run forever if they keep getting an unlucky choice of random bits, but whose expected running time is finite.  However, if you're just starting with algorithms, it's likely that you are dealing with deterministic algorithms, not randomized algorithms, so this is unlikely to come up.

Basically time complexity usage makes it easy to calculate the running time of a program and this complexity is depicted in Big-O notation.
But since the loop never ends  it has no "algorithmic time complexity"
Trying to estimate such loop's complexity would be weird and of no good use as infinity is not a real number.