Why is factoring large integers considered difficult? I read somewhere that the most efficient algorithm found can compute the factors in $O(\exp((64/9 \cdot b)^{1/3} \cdot (\log b)^{2/3})$ time, but the code I wrote is $O(n)$ or possibly $O(n \log n)$ depending on how fast division and modulus are. I'm pretty sure I've misunderstood something somewhere, but I'm not sure where. Here's what I wrote in pseudo code form.

function factor(number) -> list
    factors = new list
    if number < 0
        factors.append(-1)
        number = -number
    i = 2
    while i <= number
        while number % i == 0
            factors.append(i)
            number /= i
        i++
    return factors

You are confusing the number $n$ with the number of bits needed to represent $n$.  Here $b = $ the number of bits needed to represent $n$ (so $b \approx \lg n$).  This makes a huge difference.  A $O(n)$-time algorithm is a $O(2^b)$-time algorithm -- exponential in the number of bits.  In comparison, the "efficient" algorithm you found has a running time that is subexponential in $b$.

Example: Consider $n = 2,000,000$ (2 million).  Then $b=21$ bits are enough to represent the number $n$.  So, an algorithm that is $O(2^{b^{1/3}})$ will be much faster than an algorithm that is $O(2^b)$.  An $O(n)$ algorithm falls into the latter category, i.e., very slow.

See https://en.wikipedia.org/wiki/Integer_factorization


Can someone let me know if my understanding of amortized run time in a dynamic array list is correct? Am I right in my understanding for amortized time for insertion in a dynamic array list? (dynamic means create a copy double its size and copy existing elements to new one WHEN we reach the current size limit). Please validate my explanation/understanding.

If we insert X elements into an array of initial size 0, it will perform the double/copy operation only at insertion number 1,2,4,8,16,..,X where each operation costs a function of X f1(X), f2(X), etc.

all other insertion operations like 3,5,6,7,9,10,11, etc is O(1).

the function of X which I mentioned above is because f1(X) + f2(X) +..+ fi(X) = 2X. where i is the number of double/copy insertions.

Hence, total execution time is O(2X+j.O(1)) where j is the number of easy operations. (3,5,6,7, etc) THIS is the part I want to verify if my understanding is right or not

therefore, total time is O(2X) = O(X)

but since we are looking for the time of only inserting one element, it is O(X) / X = O(1)

hence amortized time is O(1)

Last question: why is it called amortized? Where did I amortize anything?

Thank you!!

The cost of adding one item at the end of the array of size n can be as large as O(n), but usually is much faster. That's why we use the term "amortized time". The work you did to add item #512 pays back for items 513 to 1023. It is "amortized".

The amortized cost per items is O(1), since the cost of adding n items individually is O(n).

There are various reasons why you have to be carefully with amortized cost: If you have a real time system where taking O(n) to add a single item in rare cases is not acceptable. For example, a system controlling the brakes of your car that has an amortized cost of 0.001 seconds for using the brakes once, but every 10,000 times takes 10 seconds is going to kill you.

There's also a difference between k individual operations, and combining k operations. If you have a sorted array of n items, and add a random item, keeping the array sorted, that takes O(n). However, if you want to add k items all in one go, keeping the array sorted, that takes O (n + k log k) (by sorting the k items first, then inserting them in one go). It is quite often that doing k operations can be done faster than doing one operation k times.


Why Does The Division Alorithim Need [Register Size] + 1 Iterations Following this flow diagram for division hardware I made a program to "simulate" division on $N^+$.

# 4 bit version
def div(dividend, divisor)
  quotient = 0
  remainder = dividend
  divisor <<= 4

  for i in 1..5
    remainder -= divisor
    if remainder >= 0
      quotient <<= 1
      quotient |= 1
    else
      remainder += divisor
      quotient <<= 1
    end
    divisor >>= 1
  end

  return quotient
end

What I don't understand is why there needs to be an "extra" iteration of the loop. If the divisor is being shifted down the register by 1, and the register is say 64 bits, then it would take 64 iterations to clear the register. Or in my case 4. However without that extra step the algorithm does not produce the correct result. Why is that?

"Why is that?"

Because divisor <<= 4 means original_divisor * (2**4), where I use original_divisor to denote the value of divisor when you began computing div(dividend, divisor).

Every time you do divisor >>= 1, you divide that divisor by 2. So you will get original_divisor * (2**3), original_divisor * (2**2), original_divisor * (2**1), original_divisor * (2**0).

Notice there are 5 of them, corresponding to original_divisor times $2^4, 2^3, 2^2, 2^1, 2^0$ respectively or 16,8,4,2,1 respectively. You should have noticed how 4 is changed to 5 by now. There are 4 possible shifts to the left, by 4 bits, by 3 bits, by 2 bits and by 1 bit. There is also a non-shift, or shift by 0 bit.

What you have experienced is the most famous/infamous error in computer programming, off-by-one error or off-by-one errors. I must have made this error hundreds if not thousands of times.

Just in case you have not heard of the most famous joke in computer programming, here it is. "There are two hard things in computer science: cache invalidation, naming things, and off-by-one errors." Or a shorter version, "There are two kinds of errors, off by one errors".


Are there any implementations of computability logic? I'm currently looking into Japridze's computability logic. It looks great, but I was wondering whether any programming languages or systems implement it.

Does anyone know of any implementation?

Thanks.

There doesn't seem to be any implementations of it in any current programming languages. It is rather new (introduced in 2003), so that may be a factor.

The author does define some "systems" that implement it, which are listed in the Wikipedia references. For example, Introduction to clarithmetic I, and a few related articles.

  “Clarithmetic” is a generic name for formal number theories similar to Peano arithmetic, but based on computability logic instead of the more traditional classical or intuitionistic logics. Formulas of clarithmetical theories represent interactive computational problems, and their “truth” is understood as existence of an algorithmic solution. Imposing various complexity constraints on such solutions yields various versions of clarithmetic. The present paper introduces a system of clarithmetic for polynomial time computability, which is shown to be sound and complete. Sound in the sense that every theorem T of the system represents an interactive number-theoretic computational problem with a polynomial time solution and, furthermore, such a solution can be efficiently extracted from a proof of T. And complete in the sense that every interactive number-theoretic problem with a polynomial time solution is represented by some theorem T of the system. The paper is written in a semitutorial style and targets readers with no prior familiarity with computability logic.

GitHub doesn't reveal anything either.


Decision tree and information-theoretic lower bound Consider the following problem :

Consider the problem of finding the median of a three-element set {a, b, c}.
a. What is the information-theoretic lower bound for comparison-based
algorithms solving this problem?
b. Draw a decision tree for an algorithm solving this problem.

The answer of this problem is shown below :

My problem is with number a. According to my understanding  the information theoretic lower bound = ceil (log2(2!)) , so in this question it should be equal to ceil (log2(6)) =3 because here we have 6 leaves not 3 ?

No.  The outcome is the median, not the sorted list. Thus, there are only 3 possible outcomes, not 3! outcomes.  The information-theoretic lower bound says that if there are N possible outcomes, then it takes at least $\lceil \lg N \rceil$ comparisons.  (Proof: given $k$ comparisons, you can only produce $2^k$ different outcomes.)  Here $N=3$.


Quick groupby - is this a well known algorithm? I am interested in an algorithm that accepts an array that places identical elements contiguously but the array doesn't necessarily have to be sorted.

E.g. if input is

array = ["a", "a", "c", "b", "c"]

then output

groupby(array) = ["a", "a", "c", "c", "b"]

or

groupby(array) = ["c", "c", "a", "a", "b"]

etc. The point being the final order of the array isn't important; the only requirement is that identical elements have to be placed contiguously.

One algorithm that is inspired by quicksort is to pick an element, called it pivot, and divided the array into 3 segments with the first segment being all elements that equal pivot; and the other two begin those are "less than" and "greater than" pivot. Elements within each segment have to be placed contiguously.

The segmentation can be achieved in n time using a simple adaption of the pivoting in quicksort and then apply the algorithm recursively on the "less than" and "greater than" segment.

Is this algorithm well known and has a name? Or is it a novel algorithm?

Asymptotically and under usual assumptions, the problem you state is as hard as sorting, by reduction from duplication.

If you had a $o(n \log n)$ algorithm to solve your problem, you could combine it with a constant number of array scans to produce a $o(n \log n)$ time procedure to test whether the array contains a pair of identical elements, in contradiction with the well-known $\Omega(n \log n)$ lower bound on that problem.

I don't think there's much to be gained with custom-tailored algorithms in practice, either: a well-optimized implementation of a generic sorting algorithm should be -- without further assumptions -- as efficient as you can get.


Algorithm to explore every node in a graph I need an algorithm to explore every node in a graph (starting at any given node). Each node can have multiple parent nodes and multiple child nodes.

The following algorithm (in psuedocode) appears to gather every node but results in duplicate nodes (I think because the recursive 'paths' crossover at some points):

rFindAll(Node ID, Array currentpath) //current path passed by value
{
  Array connectedNodes = getConnectedNodes(ID);

  for_each_node (Node n : connectedNodes)
  {
     if(find(currentpath, n) == NOT_FOUND) // check to ensure id not in current recursive path
     {
        // every n is a node which is within the same graph as the original node
        currentpath.add(n);
        rFindAll(n, currentpath);
     }
  }

}

I was just wondering whether anyone has a better suggestion to do this. I've looked on google/wikipedia and there was nothing which would obviously help.

Thanks

The standard way to solve this is called whatever-first search. (Because depth-first and breadth-first and best-first and others are all special cases of it.)

The algorithm goes like this:

Pick a starting node
Add the starting node to a "bag" (arbitrary data structure)
While the bag isn't empty:
    Take a node out of the bag
    Mark this node as "explored"
    [Do whatever you like with this node]
    Add all this node's unexplored neighbors to the bag

The choice of "bag" is up to you. A stack makes depth-first search, a queue makes breadth-first search, a priqueue makes best-first search, and so on, but you can use anything you like, as long as you can put things into it and take things out of it.


How can repeated addition/multiplication be done in polynomial time? I can see how adding 2 unsigned $n$-bit values is $O(n)$. We just go from the rightmost digits to the leftmost digits and add the digits up sequentially. We can also perform multiplication in polynomial time ($O(n^2)$) via the algorithm we all learned in grade school.

However, how can we add up or multiply say $i$ numbers together in polynomial time? After we add up 2 numbers together, we get a bigger number that will require more bits to represent. Same with multiplication.

How can we ensure that these extra bits do not produce exponential blowup?

From what you said, I suppose that you consider complexity in terms of number of bits of the input.

Say you add up two numbers $a$ and $b$, with respectively $n_1$ and $n_2$ bits, then the result is at most $\max(n_1, n_2) + 1$ bits since $a + b \leq 2 \times \max(a, b)$.

For the multiplication, the result is at most $2 \times \max(n_1, n_2)$ bits since $a \times b \leq \max(a, b)^2$.

The important thing is that the number of bits necessary to represent the sum / product of two numbers is polynomial in the number of bits to represent those numbers. Hence, for $i$ numbers, the number of bits necessary to represent the answer is still polynomial in the number of bits of the input (since composition of polynomial functions yields polynomial functions).

Edit: actually, the really important thing is that $i$ is not part of the input, it is fixed. Otherwise, if you take for instance $2 \times 2 \times \ldots \times 2 = 2^i$, the answer takes $2^{i-1}$ bits, while the input takes $i + \log i$ bits. But if $i$ is fixed, then $2^{i-1}$ is a constant. This kind of distinction happens quite often in computer science, especially in the field of fixed parameter tractability.


What is so special about a majority and why is it the key for Paxos to work? (Paxos made simple) Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

I was studying Paxos from:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

and I was wondering, what is so special about a majority of nodes having a value? Why is that the key fact for consensus to work on Paxos?

It says on the paper that "any two majorities have at least one acceptor in common, this works if an acceptor can accept at most one value" (page 2). Its true that if we have two majorities then at least one node between the two must be the same one, but I was not entirely sure if I fully appreciated why that was special for consensus. How does this guarantee that a single value gets accepted? Or how does it aid in that goal?

Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research

Let's assume there were more than 1 Majority. Then at least 1 acceptor would contribute to all majorities. This mandates, however, that this acceptor accepts at least 2 different values, a behaviour ruled out by assumption.


Falsifying the "Circular Wait" Condition - Deadlock Prevention In the Circular Wait condition for Deadlock Prevention section of this, it is described as follows:

  One
  way to ensure that this condition never holds is to impose a total ordering of
  all resource types and to require that each process requests resources in an
  increasing order of enumeration.
  To illustrate, we let R = {R1, R2, ..., Rm} be the set of resource types. We
  assign to each resource type a unique integer number, which allows us to
  compare two resources and to determine whether one precedes another in our
  ordering. Formally, we define a one-to-one function F: R → N, where N is the
  set of natural numbers.

  For example, if the set of resource types R includes
  tape drives, disk drives, and printers, then the function F might be defined as
  follows:
      F (tape drive) = 1
      F (disk drive) = 5
      F (printer) = 12
  We can now consider the following protocol to prevent deadlocks: Each
  process can request resources only in an increasing order of enumeration.

My question is that whether these numbers are assigned as fixed for all processes or when each process is called, it assigns a new number to each resource each time that process is called?

Because if these are fixed, then let suppose there is a process which requires disk drive first (whose number is let's say 5) and then it requires tape drive (whose number is 1 and which is less than 5); then how can it access tape drive? Because whenever it will run, it will find the same ordering / numbering of resources and it will never be able to access the tape drive.

It's fixed.  Your example violates the protocol.  If the process needs mutually exclusive access to both the tape drive and the disk drive, then it needs to take locks in increasing order, i.e. first the tape drive then the disk drive.  If it wants to use the disk drive before the tape drive, that's fine, it will just be holding the tape drive lock in the mean time.

The ordering and protocol is a global invariant.  All code everywhere at all times needs to follow the protocol to avoid deadlock.  In practice, this is pretty difficult to enforce in realistic code unless there's a manager that handles resource access.


How to show that some problem is in NP and that it's NP-complete I need some help with the following question:

Recall the subset sum problem, which is known to be NP-complete:
"Given a finite set of natural numbers and a number $n$, decide whether a subset of the given set exists such that the numbers in that subset sum up to $n$."
We consider the great subset sum problem:
"Given a finite set of natural numbers adding up to $N$ and a number $n > N/2$, decide whether a subset of the given set exists such that the numbers in that subset sum up to $n$."
a. Show that the great subset sum problem is in NP by giving the notion of certificate and arguing that the certificate can be checked in polynomial time.
b. Show that the great subset sub problem is NP-complete.
(Hint: extend the set by adding one large number.)

This was my "proof" but I think it lacks details and I feel it's wrong because I didn't use the hint for part B. Can someone tell me if did something wrong? But please, don't get use too many technical terms as we mainly use text and I might not understand your explanation.

a) A certificate for the great subset sum problem is a subset of the given set of natural numbers.
Certificate checking is done by adding up the numbers in the subset and comparing the result to the number n without forgetting the extra requirement that n > $N/2$.
Clearly, if m is the size of the original set of numbers (i.e., the size of the input), then the verification requires at most $m-1$ additions, one comparison, and final checking step, so it can be done in $O(m)$.
$O(m)$ because of the following: Adding 2 numbers takes O(1), you have to do that m-1 times. Then do one computation which also takes O(1) and finally do one comparison which also takes O(1), so in total that's O(m).
b) From the first part of the exercise it already follows that the great subset-sum problem is in NP.
To show that the great subset-sum problem is NP-complete, it remains to prove that it is NP-hard. The latter we can do by showing a polynomial-time reduction from the subset sum problem to the great subset sum problem.
Let S be a set of natural numbers and let n be a natural number. Let  $S^\prime$ be obtained from S by dividing every number in S by 2; clearly, $S^\prime$ can be obtained by an algorithm whose running time is linear in the size of S. Note that S has a subset such that the numbers in that subset add up to n if, and only if, $S^\prime$ has a subset such that the numbers in that subset add up to n where n > $N/2$.
So, we have now presented a polynomial-time reduction from the subset-sum problem to the great subset-sum problem. Since the subset sum problem is NP-hard, it follows that the great subset sum problem is NP-hard too.

When performing a reduction it is important to keep in mind exactly what you are doing. In particular you are trying to reduce from a known hard problem (here subset sum, $\mathsf{SS}$) to your problem (here great subset sum, $\mathsf{GSS}$) such that yes-instances of the hard problem map to yes-instances of your problem and no-instances map to no-instances.

As mentioned in the comments, if you simply divide each number in $S$ by two (and also divide $n$ by two) you do not get an instance of $\mathsf{GSS}$; it might not be the case that $\frac{n}{2} \geq \frac{N}{2}$.

Please think about the problem a bit more before looking at the solution below.

   Let our $\mathsf{SS}$ instance be $S = \{s_1, ..., s_k\}$ with $\sum_{s_i \in S} s_i = N$ and target $n$. We construct the following $\mathsf{GSS}$ instance: $S' = \{s_1, ..., s_k, N\}$ with target $n' = N + n$. Observe that this is a $\mathsf{GSS}$ instance since $n' \geq \frac{1}{2}\sum_{s \in S'} s = N$. It remains to show that yes-instances map to yes-instances and no-instances map to no-instances. If some subset $A \subseteq S$ adds up to $n$ then $A \cup \{N\}$ adds up to $N + n$. If not then no subset of $S'$ adds up to $n'$ since $n' > N$ so this subset must contain $\{N\}$ and a subset of $S$ which adds up to $n$.


Bounds in NP-completeness proofs According to the polynomial-time-reduction definition

"If problem $Y$ can be reduced to problem $X$ in polynomial time, we denote this by $Y \leq_p X$."

If $X$ is one of already known NP-complete problem then we can say that $Y$ is NP-complete.

From my understanding, $p$ should be always polynomial and this cannot be an exponential function such as $2^n$ or $3^n$.

However, my question is if $Y$ or $X$ already has a lower bound that is not polynomial, which is $2^n$ or $3^n$ then can I still say that $Y$ is NP-complete?

In other words, does lower bounds for $X$ and $Y$ matter?

Note that you got it wrong in the question. What you have is that if $Y \leq^p_m X$ and $Y$ is NP-hard, then $X$ is also NP-hard. This is true by definition, unconditional on any other lower bounds known for $X$ or $Y$ (though, as Ryan points out, such lower bounds could be very interesting).

If $X$ is in NP and has a lower bound on its computational complexity that is super-polynomial, it would mean that $P \neq NP$.


Why is $A \leq_T \bar{A}$? I know there's some easy proof for this, but why is $A \leq_T \bar{A}$ ? ... Suppose that $\bar{A}$ is c.e. and could loop, does this mean that the oracle $TM$ $M^{\bar{A}}$ could also loop?

But shouldn't $\leq_T$ mean that $M^{\bar{A}}$ be decidable?

A language $A$ Turing-reduces to $\overline{A}$ since a Turing machine with an $\overline{A}$-oracle can compute $A$. On input $x$, it determines whether $x \in \overline{A}$ using the oracle, and then outputs the reverse answer.


Given a sorted dictionary of words, find order of precedence of letters This question is found at: https://www.geeksforgeeks.org/given-sorted-dictionary-find-precedence-characters/

Given a sorted dictionary (array of words) of an alien language, find order of characters in the language.

Examples:

Input:  words[] = {"baa", "abcd", "abca", "cab", "cad"}
Output: Order of characters is 'b', 'd', 'a', 'c'
Note that words are sorted and in the given language "baa"
comes before "abcd", therefore 'b' is before 'a' in output.
Similarly we can find other orders.

Input:  words[] = {"caa", "aaa", "aab"}
Output: Order of characters is 'c', 'a', 'b'

Notice that the solution calls for comparison of adjacent word-pairs only, when discovering new edges. It is unnecessary to add edges from comparing non-adjacent words. This seems straightforward and intuitive to me, but how do we prove it?

An edge-discovery is done by comparing two strings, iterating through their characters, and finding the first pair of characters which differ. The former string's character precedes the latter string's character. In the case of the former string being a substring of the latter, then the edge discovery fails to return a pair. (It's impossible for the latter string to be a substring of the former)

Given a directed acyclic graph built from pairwise edge-discoveries of adjacent pairs <word[1], word[2]>, <word[2], word[3]>, ..., <word[n-1], word[n]>. Prove that comparing any two words which are not adjacent will not yield any new information, i.e. the edge-ordering discovered by the new comparison will already have been present, or implied by transitivity of edge-orderings in the existing graph.

Edit to add: I have a prefix-tree-based proof, but I'm no good at writing proofs and would welcome better-written proofs.

Let's denote the words by $w[1],\ldots,w[n]$. Suppose that $i < j$ and that $w[i],w[j]$ first differ on the $t$th coordinate. In symbols, $w[i]_{<t} = w[j]_{<t}$ but $w[i]_t < w[j]_t$ (I hope the notation is obvious).

I first claim that $w[k]_{<t} = w[k+1]_{<t}$ for all $k \in \{i,\ldots,j-1\}$. Indeed, suppose that $w[k]_{<t} < w[k+1]_{<t}$ for some $k \in \{i,\ldots,j-1\}$. Then $w[i]_{<t} \leq w[k]_{<t} < w[k+1]_{<t} \leq w[j]_{<t}$, contradicting the assumption $w[i]_{<t} = w[j]_{<t}$.

Call an index $k \in \{i,\ldots,j-1\}$ special if $w[k]_t < w[k+1]_t$. Let the special indices be $k_1,\ldots,k_m$. Then
$$
w[i]_t = w[k_1]_t < w[k_1+1]_t = w[k_2]_t < w[k_2+1]_t \cdots w[k_m]_t < w[k_m+1]_t = w[j]_t.
$$
This shows that $w[i]_t < w[j]_t$ follows from $w[k_1]_t < w[k_1+1]_t,\ldots,w[k_m]_t < w[k_m+1]_t$ by transitivity. (Here we are using the fact, proved earlier, that $w[k_r]_{<t} = w[k_r+1]_{<t}$ for $r \in \{1,\ldots,t\}$.)


Introductory explanation of the Big-Oh properties I've noticed that Big-Oh notation actually has some properties such as summation, product but i couldn't find an introductory explanation for their use or how they can help to solve asymptotic problems.

1) Is it possible to explain these properties in plain English?

2) Can these properties be applied to Big-Omega and Big-Theta notations?

Please leave any intuitive material that can help the understanding of these properties (and others).

Thanks.

Let's start by considering the positive numbers. There is a notion of order:
$$ x \leq y. $$
We can add and multiply numbers, and the order relation respect these operations:
$$
x \leq y, z \leq w \Longrightarrow x + z \leq y + w, xz \leq yw.
$$
Big O notation is very similar. We consider, for simplicity, functions which accept a natural number as input, and output a positive real. We define an order relation:
$$
f = O(g) \text{ iff there exists } C > 0 \text{ such that } f(n) \leq Cg(n) \text{ for all } n.
$$
(The funny notation $f = O(g)$ is just a notation for an order relation. Sometimes $f \ll g$ is used instead, but this is not common in computer science.)
This is similar to what we had above, with two important differences:

Since we have a function rather than a single value, we need the inequality to hold for all inputs.

We put in the extra constant $C$. This has the effect of identifying functions which differ only by a constant factor.
In more details, if $Af(n) \leq g(n) \leq Bf(n)$ for all $n$ then $g$ is "equivalent" to $f$ in the sense that $f = O(h)$ iff $g = O(h)$ and $h = O(f)$ iff $h = O(g)$.

The big O order relation also respects addition and multiplication:
$$
f = O(g), h = O(k) \Longrightarrow f + h = O(g + k), fh = O(gk).
$$

For positive numbers, we have not only $\leq$ but also $\geq$. These are related by
$$ y \geq x \text{ iff } x \leq y. $$
The relation corresponding to $\geq$ for functions is $g = \Omega(f)$, defined by
$$
y = \Omega(x) \text{ iff } x = O(y).
$$
This order relation also respects addition and multiplication.

What happens if $f = O(g)$ and $f = \Omega(g)$? When this sort of situation happens in the universe of numbers, that is when $x \leq y$ and $x \geq y$, then the two numbers are equal: $x = y$. In the case of functions, we don't get equality, but rather the notion of equivalence that was mentioned above: $Af(n) \leq g(n) \leq Bf(n)$ for some positive $A,B$. In this case we write $f = \Theta(g)$.
You can think of $f = \Theta(g)$ as an analog of equality. Indeed, it is possible to quotient by this equivalence relation and work with functions "up to constant factors", but there is no need to understand this point of view when working with asymptotic notation. It suffices to understand that if $f = \Theta(g)$ then, for the most part, $f$ and $g$ are interchangeable.
(They are not interchangeable when appearing in the exponent: for example, $n^2$ and $n^3$ don't have the same asymptotic rate of growth, although $2 = \Theta(3)$. They are also not interchangeable if appearing at the base of a non-constant exponent: $2^n$ and $3^n$ have different rates of growth.)
An important special case is $Cf = \Theta(f)$ (for $C > 0$). That is, in most cases $f$ and $Cf$ are interchangeable. In other words, asymptotic notation hides constant factors. This is one of the advantages of big O notation.

Big O notation satisfies the following peculiar property:
$$
f + g = \Theta(\max(f,g)).
$$
This useful property allows us to simplify expressions: for example, $n^2 + n = \Theta(n^2)$. Generalizing this, if $f$ is a degree $d$ polynomial, then $f = \Theta(n^d)$.


Are there any problems that get easier as they increase in size? This may be a ridiculous question, but is it possible to have a problem that actually gets easier as the inputs grow in size?  I doubt any practical problems are like this, but maybe we can invent a degenerate problem that has this property.  For instance, perhaps it begins to "solve itself" as it gets larger, or behaves in some other bizarre way.

No, it's not possible: at least, not in an asymptotic sense, where you require the problem to keep getting strictly easier, forever, as $n \to \infty$.

Let $T(n)$ be the best possible running time for solving such a problem, where $n$ is the size of the input.  Note that the running time is a count of the number of instructions executed by the algorithm, so it has to be a non-negative integer.  In other words, $T(n) \in \mathbb{N}$ for all $n$.  Now if we consider a function $T: \mathbb{N} \to \mathbb{N}$, we see there is no such function that is strictly monotonically decreasing.  (Whatever $T(0)$ is, it has to be finite, say $T(0)=c$; but then since $T$ is monotonically strictly decreasing, $T(c) \le 0$ and $T(c+1) \le -1$, which is impossible.)  For similar reasons, there is no function that is asymptotically strictly decreasing: we can similarly prove that there's no running time function $T(n)$ where there exists $n_0$ such that for all $n \ge n_0$, $T(n)$ is monotonically strictly decreasing (any such function would have to become eventually negative).

So, such a problem cannot exist, for the simple reason that running times have to be non-negative integers.

Note that this answer covers only deterministic algorithms (i.e., worst-case running time).  It doesn't rule out the possibility of randomized algorithms whose expected running time is strictly monotonically decreasing, forever.  I don't know whether it's possible for such an algorithm to exist.  I thank Beni Cherniavsky-Paskin for this observation.


Why can't we run Bellman Ford from the source and relax edges out from the neighbours recursively and do a single pass through the edges? At each $k$ th iteration of BF, we can are guaranteed to have computed the shortest paths that are at most $k$ long. That makes perfect sense me. If we relax a set of edges $k$ times, then we for sure have computed shortest paths with $k$ length. However, the part that I don't quite understand is why not only relaxing the edges that are directly connected to the source on the first iteration and then the neighbors' edges of those on the second iteration, and then the neighbouring eges of those and so forth?

The idea, is a similar algorithm to BFS I guess. We start from the frontier of edges relaxed and we make sure that we are connected to a node that we have computed its shortest path and since we are always relaxing edges that are connected like that, then we compute the shortest path in 1 pass rather than $O(EV)$ passes. I am sure I am wrong but I don't understand why. Of course it works in a straight line graph, but what type of worst-case input does it make that we need about at least $\Omega(EV)$?

I am mostly interested to understand, is the EV runtime in the worst case. I also do not care about improvements in practice or constant factors. Only asymptotics.

This would work, with a minor modification.  In other words, the resulting algorithm would be correct: it would correctly compute distances.

However, it doesn't help much.  It doesn't change the asymptotic running time of the algorithm.  In many graphs, after about $O(\lg n)$ iterations, essentially every vertex is reachable from the starting point.  Therefore, you might save a little bit on the first $O(\lg n)$ iterations, but after that, you still have to relax all edges.  Thus, this makes only a minor improvement -- far too small to show up in the asymptotic running time.  And, in practice, on most graphs, the improvement will probably be small -- perhaps so small as to be outweighed by the extra bookkeeping required.

Finally, this makes the algorithm more complicated.  From a pedagogical perspective, when the purpose is to teach algorithms, unnecessary complications are best avoided, as they just make it harder to understand an already-challenging subject.

The minor modification you need to make is: in the $k$th iteration, relax all edges $(u,v)$ where $u$ is at most $k$ edges from the source [rather than where $u$ is exactly $k$ edges away from the source].  This is important, because the shortest path from $s$ to $u$ (the one where the sum of the distances on the edges in the path) need not be the same as the path from $s$ to $u$ with the fewest edges.


Can quantum computer compute the sum of $n$ natural numbers in $\Theta(\log n)$ time? Classical computer always requires no matter what $\Theta(n)$ time to compute the sum of $n$ natural numbers, but can quantum computer do that in $\Theta(\log n)$ time?

Given that $a$ is an infinite sequence of natural numbers defined either iteratively or recursively by some math formula and $a_i$ is an arbitrary natural number, an element of the infinite sequence $a$, for any arbitrary index $i \in \mathbb{N}.$

Then to compute the sum of the first $n$ natural numbers of the infinite sequence $a$ or in other words to compute $\displaystyle \sum_{i=1}^{n} a_i$

Classical computer always requires $\Theta(n)$ time to do that, but what about quantum computer? How much time does quantum computer requires? Can quantum computer do this computation in $\Theta(\log n)$ time?

Please assume that computation of $a_i$ for any index $i \in \mathbb{N}$ requires
no longer than $\Theta(1)$ time.

No, a quantum computer can't sum $n$ outputs from a black box function in $O(\lg n)$ queries.

For example, you could use magic summing power to easily do asymptotically better than Grover's algorithm at searching for solutions to a predicate. Except Grover's algorithm is proven to be asymptotically optimal. Contradiction.

Also, magic summing would trivially prove that $NP \subseteq BQP$. To determine if problem X has a solution or not, you'd simply sum up the outputs of the black box "if input is a solution for problem X then output 1 else output 0".


Trying to understand max heapify I tried watching http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-4-heaps-and-heap-sort/ to understand heaps and heapsort but did not find this clear.

I do not understand the function of max-heapify. It seems like a recursive function, but then somehow it's said to run in logarithmic time because of the height of the tree.

To me this makes no sense, because what if you run max-heapify on a min-heap? It'll have to reverse every single node, which I don't see how this can be done without it touching every single node.

$Q_1:$ I do not understand the function of max-heapify. It seems like a recursive function, but then somehow it's said to run in logarithmic time because of the height of the tree.

max-heapify can be described as a recursive function. There is no particular prevention from a recursive function running in logarithmic time. For max-heapify, the recurrence is $T(n) \le T(2n/3) + \Theta(1)$ (here $2n/3$ is the worst case when the leaves is exactly half full; where $n$ is the size of the subtree rooted at the node under max-heapify). You can solve it by Master Theorem.

Another way of looking at max-heapify is to unfold the recursions: it "floats down" a value through a path of the subtree, whose length is $\sim \Theta(\lg n)$.

  $Q_2:$ To me this makes no sense, because what if you run max-heapify on a min-heap? It'll have to reverse every single node, which I don't see how this can be done without it touching every single node.

The answer is simple: We don't run max-heapify on a min-heap. Use min-heapify for min-heap instead.


Recover an array from its insertion indices An array is built starting with an empty array, and then a sequence of insertions:

insert $a_1$ at index $z_1=1$
insert $a_2$ at index $z_2$
insert $a_3$ at index $z_3$
...

and so on.  When we insert element $a_i$ and index $z_i$ the result is that $a_i$ is now at index $z_i$, whereas everything before index $z_i$ is unchanged and everything after has its index increased by 1. (With one-based indexing) E.g., the sequence
$(3,1), (5,2), (1,2)$ gives $[3]$ then $[3,5]$ then  $[3,1,5]$. All of the instructions will make sense, i.e., $1 \leq z_i\leq i$.

My question is about how to calculate the final array. The naive approach would be to start with an empty array, and literally obey the instructions;  but in the language I program, insertions have a worst case time complexity of $O(\# $elements shifted$)$; if, for example, all the insertion indices were $1$, this would result in $O(N^2)$ time.

Supposing we have access to all the instructions simultaneously, how can we calculate the final array in faster than $O(N^2)$ time? I would be happy with a name if this problem is well studied. I did make the following (family of) observations:

the element which ends up at index 1 was the last one which arrived with index 1.
the element which ends up at index 2 arrived with index 1 or 2. If it arrived with index 2, then none came after it with either index 1 or 2. If it arrived with index 1, then exactly one came after it with index 1, after which came none with index 2.
the element which ends up at index 3 arrived with index 1, 2, or 3. If it arrived with index 3, then none came after it with index 1, 2 or 3. If it arrived with index 2, then exactly one element with index 1 or 2 followed it, then none after that with index 1, 2, or 3. If it arrived with index 1, then it was followed by one with index 1, then one with index 1 or 2, and then none after that with index 1, 2, or 3.

... and so on.
However I can't think of the algorithms or data structures that would make this information useful.

Update: There are two $O(n\log n)$ solutions below: the first one, which I accepted, that uses an AVL tree, and one which I learned of afterward that uses a semgent tree, and is somewhat simpler.

Prelimiaries

You can augment an AVL tree to support all the usual operations plus the following:

  Shift$(a,b)$ increases all keys $k \ge a$ by $b \ge 0$ in $O(\log n)$ time (where $n$ is the number of elements in the tree).

To do so add a value $x_v$ to each node $v$ in the tree. This value represents an offset to be added to all keys stored in the subtree rooted at $v$. The Search, Insert, and Shift operations, along with the required rotations can be implemented as follows (I won't be using the Delete operation, but it can also be implemented).

Search
The search operation work as usual except that you now keep track of the cumulative offset in the path from the current node to the root.

Insert
To insert a node with key $k$, use the search operation to find the position where a node with key $k$ would need to be placed and the cumulative offset $\overline{x}$ up to that point. Add a leaf in that position and store its key as $k - \overline{x}$. Perform the necessary rotations to rebalance the tree (see the sequel).

Rotations To perform a right rotation on $u$ let $v$ be its left child.
"Push down" the offset of $u$ as follows: increment the stored key of $u$ by $x_u$, add $x_u$ to the offsets of the children of $u$, and set $x_u$ to $0$. Similarly, "push down" the offset of $v$. Perform the rotation as usual. Left rotations are symmetric.

Shift$(a,b)$. Find the node $u$ with key $a$ or, if no such node exists, find its successor (if the successor doesn't exist either, we are done). Increase the stored key of $u$ by $b$. If $u$ has a right child $v$ then increase $x_v$ by $b$ as well. Walk from $u$ to the root of the tree. Every time you walk to a vertex $w$ from its left child, increase the key of $w$ by $b$ and the offset $x_z$ of the right child $z$ of $w$ by $b$ (if $z$ exists).

Solving your problem

Keep an augmented AVL tree $T$ and consider the operations one at a time. At the end of the generic $i$-th step, the tree will contain $i$ nodes that collectively store the elements of the first $i$ operations.
Each node $u$ is associated with one element of the array. The key of $u$ is exactly the position of $u$'s element in the array, as of the $i$-th operation, while the element's value is stored as satellite data in $u$.

When the operation $(a_i, z_i)$ is to be processed do a Shift$(z_i, 1)$ operation on $T$. Then, insert a new node with key $z_i$ and satellite data $a_i$ in $T$.

At the end of the process you can traverse the tree and recover the final position (the node's key) of each array element (the node's satellite data).

The total time required is $O(n \log n)$.


Minimize sum of squared error I have an array of real numbers, I want to partition them into k sets. In each set, I calculate the sum of squared error. Then, I add up all the sum of squared error for all the set. I want to minimize this number. For example:

1 3 5 9

if k=2, I would partition them into (1 3 5) and (9), the sum of squared error of (1 3 5) is (3-1)^2+(3-3)^2+(5-3)^2=8 and the sum of squared error of (9) is 0. So the total sum of squared error is 8. I think 8 is the minimum sum of squared error in this case.

I want to use the traditional prim's method to solve this problem. i.e. to use connect n-k edges, then stop. But the problem is whenever I add 1 more integers to the subset, the mean changes. So, it seems that I cannot use Prim's method...Anyone give me some insight on this? Thanks!

You are looking for an optimal 1-dimensional k-means algorithm.  The k-means objective function for partitioning the data $x_1, \ldots, x_n$ into $k$ sets $S = \{S_1, \ldots, S_k\}$.

$$
\sum\limits_{i=1}^k \sum\limits_{x \in S_i}\lVert x - \mu_i \rVert^2
$$

where $\mu_i$ is the mean of $S_i$ [1].

You can apply a dynamic programming algorithm to the problem [2].

Let the data $x_1, \ldots, x_n$ be sorted in non-decreasing order.
Fill a $(n + 1) \times (k + 1)$ array, $D$, with the minimum sum of squared errors, for the first $i$ entries, using $m$ clusters.  This can be calculated as

$$
   D[i,m] := \min\limits_{m \le j \le i} \left\{ D[j-1,m-1] + d(x_j, \ldots, x_i) \right\}
   $$

where $d(x_j, \ldots, x_i)$ is the sum of squared errors from their mean.  For $1 \le i \le n$ and $1 \le m \le k$, and the base cases are $d[i,m] = 0$ if $i=0$ or $m=0$.

Thus, the entry $D[n,k]$ contains the optimal sum of squared errors for the original problem, now all that is left to do is to extract the answer.

Note that $d(x_j, \ldots, x_i)$ can be computed iteratively to speed up the algorithm, as

$$\begin{align*}
   d(x_j, \ldots, x_i) &= d(x_j, \ldots, x_{i-1}) + \frac{i-1}{i} (x_i - \mu_{i-1})^2 \\
   \mu_i &= \frac{x_i + (i - 1) \mu_{i-1}}{i}\end{align*}
   $$

Thus, $D$ can be computed in $O\left(n^2k\right)$ time, since there are $nk$ entries, and each takes $O(n)$ time to compute.
Now, we fill a $n \times k$ array, $B$, whose entries, $B[i,m]$, contain the index of the smallest (first) element in the cluster that contains entry $i$, which can be calculated as

$$
   B[i,m] := \arg\min\limits_{m \le j \le i} \left\{ D[j-1,m-1] + d(x_j, \ldots, x_i) \right\}
   $$

for $1 \le i \le n$ and $1 \le m \le k$.  This takes $O\left(n^2k\right)$ time.

Thus, we can backtrack from $B[n,k]$ to find the clustering.  The clusters are defined recursively as

$$\begin{align*}
   S_k &= \{B[n,k], \ldots, x_n\} \\
   S_i &= \{B[x_j,k], \ldots, x_j \mid x_{j+1} := \min S_{i+1}\}
   \end{align*}$$

The backtracking takes $O(k)$ time.

The algorithm runs in $O\left(n^2k\right)$ time, and requires $O(nk)$ space.

[1] http://en.wikipedia.org/wiki/K-means_clustering

[2] http://journal.r-project.org/archive/2011-2/RJournal_2011-2_Wang+Song.pdf


What is the LTL expression for "there is a value of y whose next value is 8"? Basically i have a program which increases a variable by 1 in each iteration and resets it to 0 as soon as y becomes 8 (i.e. mod 8).

It is a quite simple example but it still bugs me out because i cannot clarify if my LTL-formula is correct for the property "there is a value of y whose next value is 8". For this i came up with the:

$$FX(y \doteq 8)$$

which means "somewhere in the future the next value of y is 8".

Is it the correct LTL formula for my question (even though it is of course invalid for my application)?

The important thing that is missing from your question is how you model your program, and specifically, what are the atomic propositions you allow.

If your atomic propositions are "y=0",...,"y=8", and your transition system is modeled accordingly, then the formula $FX y=8$ means the eventually, the next position would have "y=8". Note that this is equivalent to the formula $XF y=8$, which basically says that y=8 sometime after the first position.

However, you phrased your requirement as "there is a value of y whose next value is 8", and it's not clear what this means. What is the "next value of y"? LTL does not recognize y as an entity, only the propositions mentioned above. So you cannot really talk about values of variables in LTL, without first adding all possible values as propositions.


Can a semi-decidable problem be also decidable? As far as I understand, a semi-decidable (recursively enumerable) problem could be:

  decidable (recursive) or
  undecidable (nonrecursively enumerable)

This post made me wonder if this is not conventionally followed. This is my answer to it and as far as I understand it is correct:

  A semidecidable problem (or equivalently a recursively enumerable
  problem) could be:

  Decidable: If the problem and its complement are both semidecidable
  (or recursively enumerable), then the problem is decidable
  (recursive).

  Undecidable: If the problem is semidecidable and its complement is not
  semidecidable (that is, is not recursively enumerable).

  Important note: Remember that a decidable (recursive) problem is also
  semidecidable (recursively enumerable). Conversely, if a problem is
  not recursively enumerable (semidecidable), then is not recursive
  (decidable).

What the Wikipedia entry says is that:

  Partially decidable problems that are not decidable are called
  undecidable.

  In general, a semidecidable problem (recursively enumerable) could be
  decidable (recursive) or undecidable (nonrecursively enumerable).

  Also note that a problem and its complement could both (or just one of
  them) be not even semi-decidable (nonrecursively enumerable). Also
  note that, if a problem is recursive, its complement is also
  recursive.

Is it conventionally (always) understood this way? Is there some literature that presents semi-decidability (partially decidable, recursively enumerable) problem as an equivalent of undecidability?

Yes, a recursively enumerable language may be either decidable or undecidable. To see this, you ust look at the definitions of the terms.

A language $L$ is recursive (aka decidable) if there is a Turing machine that halts for all inputs, accepting every word in $L$ and rejecting every word not in $L$. $L$ is recursively enumerable (aka semi-decidable) if there is a Turing machine that halts and accepts any input in $L$ and, for any input not in $L$, it either halts and rejects or it does not halt.

Therefore, every recursive language is recursively enumerable. The machine that decides the recursive language is a special case of the machine required for a recursively enumerable language: specifically, it is allowed to either loop forever or reject for words not in $L$; in fact, it always rejects and never uses the option of looping forever.


draw DFA with {w|w= Σ*0100}∩{w|w≠Σ*11Σ*} So i need to draw a DFA for this language, i know i need to separate for 2 DFAs and than combine them both.

What is the approach ?
How do i do the $\Sigma^*$ inside the DFA ?
The 0100 condition is kinda easy, also the 11 language.

How to draw $\{w|w≠\Sigma^*11\Sigma^*\}$:

Three states $S_0, S_1, S_2$ are needed. $S_0$ is both a initial state and an accepted state, $S_1$ is an accepted state. Whenever you read a $1$, go from $S_i$ to $S_{i+1}$. Finally let $S_2$ be the dead state.

Similarly you can draw the $\{w|w=\Sigma^* 0100\}$.

In the end, we combine these two DFAs with a cartesian product. You can look up here: https://stackoverflow.com/questions/7780521/how-to-use-the-intersection-construction-to-form-a-dfa


How connected are information theory and algorithmic information theory? In the book by Cover and Thomas on information theory, there is a chapter on algorithmic information theory (kolmogorov complexity and so forth).

As far as I understand, algorithmic information theory was developed separately from information theory, and Kolmogorov didnt formalize AIT in terms of shannon entropy and so forth (am I wrong?)

How connected are the two fields? Are they really about quite separate things? Are there only some marginal connections? Or are they deeply connected?

I don't have the background to give a deep answer about how deeply connected the fields are, but Li and Vitanyi's An Introduction to Kolmogorov Complexity and Its Applications--probably the most widely known textbook on AIT--repeatedly incorporates mathematical and conceptual material from information theory (such as Shannon entropy) into its presentation of AIT.  Here is a quotation from the third edition (p. 73) that illustrates a connection that might be considered deep:

  We are interested in a measure of information content of an individual
  finite object, and in the information conveyed about an individual
  finite object by another individual finite object. Here, we want the
  information content of an object x to be an attribute of x alone, and
  not to depend on, for instance, the means chosen to describe this
  information content. Making the natural restriction that the
  description method should be effective, the information content of an
  object should be recursively invariant (Section 1.7) among the
  different description systems. Pursuing this thought leads
  straightforwardly to Kolmogorov complexity.

(Apart from the fact that most of the paragraph clearly seems to be discussing Shannon information, it comes immediately after a paragraph that discusses a quotation by Shannon.)


Why does this pumping lemma application "prove" that 0*1* is not regular? Here is a proof that $0^*1^*$ is not regular, even though it is regular. I'm having a hard time figuring out what is wrong with the proof.

Assume $0^*1^*$ is regular. Let $p$ be the pumping length as defined by the pumping lemma. Let $s = 0^{p-1}11$, then $|s| \ge p$ and $s \in 0^*1^*$. According to the pumping lemma, we can split $s$ into three parts $s = xyz$ such that $|y|>0$, $|xy| \le p$, and $xy^iz \in 0^*1^*$ for $i \ge 0$. Let $x = \varepsilon$, $y = 0^{p-1}1$, and $z = 1$. Clearly, $|xy| \le p$ and $|y|>0$. However, $xy^2z = 0^{p-1}10^{p-1}11$ is not a member of $0^*1^*$. This is a contradiction to the pumping lemma, therefore $0^*1^*$ is not regular.

We know $0^*1^*$ is regular, building a NFA for it is easy. What is wrong with this proof?

The idea is that there is some partition that fulfills the condition of the pumping lemma - you do not have the choice of the x, y, and z - you have to show that there exists no x, y, and z that satisfies the conditions.


Chomsky normal form: epsilon rule I have pretty simple question, but still can't find an answer just googling it.

I'm trying to understand Chomsky Normal Form (CNF). There are three production rules:

$A \to BC$
$A \to \alpha$
$S \to \epsilon$

First two I understand. But last one $\epsilon$ doesn't makes sense for me. Why do we need this rule? What is use of having this?

The last rule is necessary for languages containing $\epsilon$. A context-free grammar in which $S$ does not generate $\epsilon$ can be converted to Chomsky normal form without the rule $S \to \epsilon$. Conversely, simple induction shows that all other rules do not generate $\epsilon$, so this rule is needed for languages generating $\epsilon$.

The rule arises during the $\epsilon$-elimination step. For each non-terminal generating $\epsilon$, we "optionally" delete it from any production containing in in the right-hand side, and continue the process inductively (eliminating one non-terminal overtly generating $\epsilon$ may reveal that under generates $\epsilon$). Finally, it could happen that $\epsilon$ is pushed all the way to the starting symbol $S$; there is no way to eliminate it there.


Closure properties between two languages from different grammars We know that if we have two languages produced by one regular grammar, then any language produced from the union, intersection, and so on would be regular.

What if we have a regular grammar that produces language A and a different regular grammar that produces language B. Then could the closure properties still be used in order to produce another regular language C?

For example, is $A\cap B$ a regular language (intersection)? Is $A\|B$ a regular language (concatenation)?

A grammar produces exactly one language; it makes no sense to speak of two languages produced by the same grammar.

The closure properties of regular languages apply to any regular languages.


Problems Implementing Closures in Non-functional Settings In programming languages, closures are a popular and often desired feature. Wikipedia says (emphasis mine):

  In computer science, a closure (...) is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables outside its immediate lexical scope.

So a closure is essentially a (anonymous?) function value which can use variables outside of its own scope. In my experience, this means it can access variables that are in scope at its definition point.

In practice, the concept seems to be diverging, though, at least outside of functional programming. Different languages implement different semantics, there even seem to be wars of opinons on. Many programmers do not seem to know what closures are, viewing them as little more than anonymous functions.

Also, there seem to exist major hurdles when implementing closures. Most notable, Java 7 was supposed to include them but the feature was pushed back to a future release.

Why are closures so hard (to understand and) to realise? This is too broad and vague a question, so let me focus it more with these interconnected questions:

Are there problems with expressing closures in common semantic formalisms (small-step, big-step, ...)?
Are existing type systems not suited for closures and can not be extended easily?
Is it problematic to bring closures in line with a traditional, stack-based procedure translation?

Note that the question relates mostly to procedural, object-oriented and scripting languages in general. As far as I know, functional languages do not have any problems.

May I direct you to the Funarg problem wikipedia page? At least this is how the compiler people used to reference the closure implementing problem.

  So a closure is essentially a (anonymous?) function value which can use variables outside of its own scope. In my experience, this means it can access variables that are in scope at its definition point.

While this definition makes sense, it does not help describe the problem of implementing first-class functions in a traditional runtime-stack based language. When it comes to implementation issues, first class functions can be roughly divided into two classes:

Local variables in the functions are never used after the function returns.
Local variables can be used after the function returns.

The first case (downwards funargs) is not that hard to implement and can be found on even the older procedural languages, like Algol, C and Pascal. C kind of skirts the issue, since it does not allow nested functions but Algol and Pascal do the necessary bookkeeping to allow inner functions to reference the stack variables of the outer function.

The second case (upwards funargs), on the other hand, requires activation records to be saved outside the stack, in the heap. This means that it is very easy to leak memory resources unless the language runtime includes a garbage collector. While almost everything is garbage collected today, requiring one is still a significant design decision and was even more so some time ago.

As for the particular example of Java, if I remember correctly, the main issue was not actually being able to implement closures, but how to introduce them to the language in a way that was not redundant with existing features (like anonymous inner classes) and that did not clash with existing features (like checked exceptions - a problem that is not trivia l to solve and that most people don't think of at first).

I can also think of other things that make first class functions less trivial to implement, such as deciding what to do with "magical" variables such as this, self or super and how to interact with existing control flow operators, such as break and return (do we want to allow for non-local returns or not?). But in the end, the recent popularity of first-class functions seems to indicate that languages that don't have them mostly do so for historical reasons or due to some significant design decision early on.


Arguing that $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ is not $LL(k)$ for any $k$ Consider the language  $L= \{a^n \mid n\geq 0\} \cup \{a^nb^n\mid n\geq 0\}$ and the following statements.
$\quad\quad\text{I. }L$ is deterministic context-free.
$\quad\quad\text{II. }L$ is context-free but not deterministic context-free.
$\quad\quad\text{III. }L$ is not $LL(k)$ for any $k$.
Which of the above statements is/are TRUE?
$\quad\quad\quad$ A. $\text{I}$ only
$\quad\quad\quad$ B. $\text{II}$ only
$\quad\quad\quad$ C. $\text{I}$ and $\text{III}$ only
$\quad\quad\quad$ D. $\text{III }$ only
(GATE-CS-2020)

My doubt is only regarding a part of the above question, i.e. arguing about statement $\text{III}$.
Most of my mates are arguing as :

"Since $a^n$ for any arbitrary $n$, on just seeing $a^n$ on the input we cannot decide whether it is a part of $a^m$ or $a^mb^m$ for $m>n$ so the language is not $LL(k)$ for any $k$ since we cannot have an arbitrary or finite $k$ ".

But while reading the automata text by Peter Linz I came across an example as:

Example 7.11  The grammar $$S \rightarrow SS |aSb| ab$$
not an $LL (k)$ grammar for any $k$.

The above grammar in the Linz text is the grammar generating the positive closure of $\{a^nb^n|n\geq 1\}$ or simply it generates the set of strings having well formed parenthesis structure.
Now here the thing to be noted is that : Linz talks about the "grammar" not about the language as a whole. Talking about the language seems a bit difficult to me.
The author says that the "grammar" is not $LL(k)$ for any $k$ with the following argument:

To see why this is so, look at the derivation of strings of length greater than two. To start, we have available two possible productions $S \rightarrow SS$ and $S \rightarrow aSb$. The scanned symbol does not tell us which is the right one. Suppose we now use a look-ahead and consider the first two symbols, finding that they are $aa$. Does this allow us to make the right decision? The answer is still no, since what we have seen could be a prefix of $a$ number of strings, including both $aabb$ or $aabbab$. In the first case, we must start with $S \rightarrow aSb$, while in the second it is necessary to use $S \rightarrow SS$. The grammar is therefore not an $LL (2)$ grammar. In a similar fashion, we can see that no matter how many look-ahead symbols we have, there are always some situations that cannot be resolved.

The above explanation which my mates gives, quite matches with that of Linz, but the difference is that my mates are talking about the language and Linz talks about the grammar.
I came up with a grammar for the language in $\text{GATE-CS-2020}$ paper.

$$S\rightarrow S_1 | S_2$$
$$S_1 \rightarrow aS_1 b | \epsilon$$
$$S_2\rightarrow aS_2| \epsilon$$

which is not $LL(k)$ for any $k$ using similar logic as in Linz text. But proving that a grammar is not $LL(k)$ for any $k$ does not say anything about the language, as Linz says:

This observation about the grammar does not imply that the language is not deterministic or that no LL grammar for it exists.

then Linz removes the problem with the grammar and comes up with a "more not obvious form" (but does not explain how) which is $LL$ and equivalent to the original grammar in example 7.11

$$S_0 \rightarrow aSbS $$
$$S \rightarrow aSbS| \epsilon$$

So given such a question about the "language" as in the $\text{GATE-CS-2020}$ paper, how should one proceed? Or what should be the thinking approach?

Rosenkrantz and Stearns prove in their paper Properties of deterministic top-down grammars that the language
$$ \{ a^n b^n : n \ge 0 \} \cup \{ a^n c^n : n \ge 0 \} $$
is not $\mathrm{LL}(k)$ for any $k$ (see page 246). Presumably a similar proof will show that your language is not $\mathrm{LL}(k)$ for any $k$.

You mention a confusion between grammars and languages. By definition, a language is $\mathrm{LL}(k)$ if it has an $\mathrm{LL}(k)$ grammar. To show that a language is not $\mathrm{LL}(k)$, you have to show that it has no $\mathrm{LL}(k)$ grammar.


Inference rules for deriving invariants in Hoare logic The following algorithm is supposed to compare two strings $S_1$ and $S_2$ ("/\" for empty string):

X = S1
Y = S2

E = true
// (1) S1 = S2 <=> X = Y and E = true
while X != /\ and Y != /\ and E == true
  if head(X) == head(Y)
    X = tail(X)
    Y = tail(Y)
  else
    E = false
// (2) S1 = S2 <=> X = /\ and Y = /\ and E = true
if !(X == /\ and Y == /\)
  E = false
  // (3) S1 != S2 and E = false
else // an empty else; just for inserting an assertion (i.e., 3' below) here
  // (3') S1 = S2 <=> E = true
// (4) S1 = S2 <=> E = true
return E

There are five invariants:

(1). $S_1 = S_2 \iff X = Y \land E = true$

(2). $S_1 = S_2 \iff X = \Lambda \land Y = \Lambda \land E = true$

(3). $S_1 \neq S_2 \land E = false$

(3'). $S_1 = S_2 \iff E = true$

(4). $S_1 = S_2 \iff E = true$

I can understand these invariants and how they are derived from the previous ones in an intuitive and thus informal way. For example, we can derive (3') from (2) as follows:

  At point (2), we know that $S_1$ equals $S_2$ iff $X = \Lambda \land Y = \Lambda \land E = true$. At point (3'), we further know that $X = \Lambda \land Y = \Lambda$. Thus, at this point, we only need to check whether $E = true$ to decide whether $S_1 = S_2$ holds.

However, the reasoning above cannot be justified by the conventional inference rules of propositional logic by which we would have

$$S_1 = S_2 \iff (X = \Lambda \land Y = \Lambda \land E = true) \land (X = \Lambda \land Y = \Lambda),$$
which is $S_1 = S_2 \iff X = \Lambda \land Y = \Lambda \land E = true.$

Problem: What are the inference rules for the derivation from (2) to (3')?

Related Post: Developing invariants for comparing two strings

Edit:
As pointed out by @chi in the comment, it should be
$$\big(S_1 = S_2 \iff (X = \Lambda \land Y = \Lambda \land E = true)\big) \land (X = \Lambda \land Y = \Lambda),$$
which implies (3')
$S_1 = S_2 \iff E = true$ as the answer given by @kne shows.

There are two ways to answer the question.

The first is on the level of propositional logic. You have three statements, $S_1=S_2$, $(X=\Lambda\wedge Y=\Lambda)$, and $E=true$. Let's call them $A$, $B$, and $C$ for short. (2) is $A\Leftrightarrow(B\wedge C)$ and (3') is $A\Leftrightarrow C$. At point (3') we know $B$. Every assignment of the propositional variables that satisfies $B$ and (2) also satisfies (3'). In other words, at the position (3') we know

$(A\Leftrightarrow(B\wedge C))\wedge B$

from which

$(A\Leftrightarrow C)$

follows semantically. If the propositional proof system of your choice is complete, the above can also be derived using its rules.

The second answer addresses Hoare logic instead of propositional logic. Hoare logic has its own derivations. The neat thing is that most of them can be automated. And they work backwards. In the case at hand, (3') is derived from (4) by copy. After all, at the end of the else clause, the same invariant must hold as after the if-then-else. The then clause does not follow that rule, so let us fix the code

// (2) S1 = S2 <=> X = /\ and Y = /\ and E = true
// (2') (!(X == /\ and Y == /\) and (S1 = S2 <=> false = true)) or
//    ((X == /\ and Y == /\) and (S1 = S2 <=> E = true))
if !(X == /\ and Y == /\)
  // (3'') S1 = S2 <=> false = true
  E = false
  // (3) S1 = S2 <=> E = true
else // an empty else
  // (3') S1 = S2 <=> E = true
// (4) S1 = S2 <=> E = true

Now (3) is derived from (4) by copy, (3'') is derived from (3) by substitution (that is the Hoare logic rule for assignment) and (2') is derived from (3''), (3') and the if condition. It remains to see how (2') follows from (2). That is propositional logic plus $false\not=true$.


Create an Finite Deterministic Automata for a regular expression I want to create a finite state machine that accepts the following language:
$$
L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\}
$$
So I began by writing a regular expression from this and this is what I came up with:
$(a+b)(a+b)^*abb(a+b)^*$
And for the finite state machine I tried to do this:

But it doesn't work since I can go from qo->(a)q1->(b)->(b)q1 and have $abb$ at the begining. How should I approach this? How should I approach to create a finite state machine when for example I have the regular expression? How should I develop an intuition without using algorithms such as FollowPos?

I think your problem could be understood in two ways:

$abb$ is a subword of $w$ and the word $w$ doesn't start with $abb$
$abb$ is a subword of $w[1:]$, but the word $w$ can start with $abb$

I will assume the first one but correct me if I'm wrong.
One way to create an automaton for this language would be as follows:

From the start state $q_0$ go to $q_a$ on input $a$ and to $q_{abb?}$ on input $b$
From $q_a$ go to $q_{ab}$ on $b$ and to $q_{bb?}$ on $a$
From $q_{ab}$ go to $q_{reject}$ on $b$ and to $q_{bb?}$ on $a$
From $q_{abb?}$ loop on $b$ and go to $q_{bb?}$ on $a$
From $q_{bb?}$ go to $q_{b?}$ on $b$ and loop on $a$
From $q_{b?}$ go to $q_{accept}$ on $b$ and to $q_{bb?}$ on $a$
Loop on $q_{accept}$, which is the accepting state

The graphical representation would look as follows:

So what we are doing, in essence, is first checking if the word $w$ starts with $abb$ and if it does reject it and if it does not, then look for the subword $abb$.
Answering the other part of your question:

There is an algorithm that transforms regular expressions to Nondeterministic Finite Automata
Developing intuition is just a matter of practice. You have to write as many automata for regular languages as possible and see what are the common tricks and methods, and what are some traps that await you when constructing automata.


Writing a Context-Free-Grammar using Backus Naur Form for a for-loop? I'm pretty new to CFG, and I've tried out some samples as well. As of now I'm trying this for-loop to write it in CFG using BNF:

Start{
    int z = 20;
    for(int b = 0; b < 5; b++)
    {
        //some statement
    }
}

Attempted BNF:

<program> ::= Start <blockstatements>
<blockstatements> ::= <statement> | <statement>; | <statement_list> | <empty>
<statement> ::= <typespecification> <varDeclaration> <assignment-operator> <expression>
<typespecification> ::= char | short | int | long | float | double | string
<varDeclaration> ::= a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | x | y | z
<assignment-operator> ::= =
<expression> ::= <value>
<value> ::= <digit> | <letter> | <number> | <word>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" |
            "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" |
            "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"
<number> ::= <digit> + <digit> | <digit> - <digit> | <digit> * <digit> | <digit> / <digit>

The above CFG isn't complete and I wanted to make sure that I'm doing it correctly. Am I heading towards the right path? Should it be written as above or have I missed anything?

Any help could be appreciated.

I've usually seen it expressed as something like:

forExpression ::= for ( <declExpression> <expression>; <expression> ) <blockStatement>

blockStatement ::= <statement> |  { <statementlist> }

statement ::= <declExpression> | <forExpression> | <ifExpression> | ...

<declExpression> includes the semi colon

You want to be very careful of the details like where you define where things like the semi colon are required,

In your <number> you don't have any priorities set up, there is also no option for parenthesis, ...

Creating a good CFG is hard which is why so many languages start out as a dialect of C and just take that grammar and adapt it.


Bin packing when items can be broken In the bin packing problem, there are some $m$ items of size less than $1$, and they have to be packed into as few as possible bins of size $1$. The problem is NP-hard, but if we are allowed to break some items then it becomes easy, since each bin can be filled completely.
What if we are allowed to break (to as many pieces as we like) only $k$ items of our choice, where $k$ is a fixed constant - is the problem still NP-hard?

Here is a proof that the problem remains hard when $k=1$. For simplicity it uses an item of size equal to the bin capacity. If you require each item to be smaller than the bin capacity you can subtract a small enough constant from this item's size.
Consider an instance of $3$-partition in which $3n$ positive integers  $x_1, x_2, \dots, x_{3n}$ of total sum $S$ need to be partitioned into $n$ triples $t_1, \dots, t_n$, each with total sum at most $T=\frac{S}{n}$, where $T$ is also an integer.
Assume that $x_i \ge \frac{2T}{7}$ (it is known that the problem remains strongly NP-complete in this case).
Furthermore assume that $n > \max\{8,T+1\}$ (if this is not the case, multiply each integer in the instance by $10$, add many copies of the integers in $\{10T-2, 1, 1\}$ to the input, and then convert the resulting instance into an instance that satisfies $x_i \ge \frac{2T}{7}$. This conversion multiplies the new value of $T$ by $7$).
Consider the instance of your version of bin-packing in which $k=1$ and you need to pack the set of elements $Y = \{y_1, \dots, y_m\}$ into the fewest number of bins of capacity $n T$ (you can set the capacity of each bin to $1$ by a suitable scaling of all the involved quantities).
Let $m=3n+1$, $y_m = nT$ and $y_i = (n-1) x_i$ for $i=1,\dots,3n$.
If the $3$-partition instance is a yes-instance then $Y$ can be packed into $n$ bins.
Create a bin $b = (y_i, y_j, y_h)$ for each triple $t = (x_i, x_j, x_h)$ of a solution of $3$-partition. Notice that $y_i + y_j + y_h = (n-1) (x_i + x_j +x_h) = (n-1)T$, leaving $b$ with unused capacity of $T$.
The only element not assigned to a bin is $y_m$. Split $y_m = nT$ into $n$ pieces of size $T$ each, and add a piece to each of the $n$ bins.
If $Y$ can be packed into $n$ bins then the $3$-partition instance is a yes-instance.
Notice that $\sum_{i=1}^m y_i = (n-1) \sum_{i=1}^{3n}x_i + nT = (n-1)nT + nt = n \cdot nT$, showing that each each of the $n$ bins must be completely full.
We can assume w.l.o.g., that if some element is split into pieces, this element is $y_m$.
Indeed, if an element $y' \neq y_m$ is split, there must be one bin $b'$ that is used entirely for $y_m$. We can then swap each piece of $y'$ with a piece of $y_m$, so that $y'$ is now entirely contained in $b'$.
Notice now that each bin $b$ must contain exactly $3$ elements from $\{ y_1, \dots, y_{3n}\}$.
Indeed, if this was not true there would exist a bin that contains at least $4$ elements from $\{ y_1, \dots, y_{3n}\}$ and its used capacity would be at least
$$
4(n-1)\left(\frac{2T}{7}\right) = \left( \frac{8}{7}n - \frac{8}{7} \right)T > nT.
$$
We construct a solution for the $3$-partition instance by creating a triple $t = (x_i, x_j, x_h)$ for each bin $b$ containing $y_i, y_j, y_h$ with $i,j,h \le 3n$.
The total weight of $t$ is at most:
$$
x_i + x_j + x_h = \frac{y_i + y_j + y_h}{n-1} \le \frac{nT}{n-1}
= \frac{(n-1)T+T}{n-1} = T + \frac{T}{n-1} < T+1,
$$
i.e., $x_i + x_j + x_h \le T$.


What NP decision problems are not self-reducible? So we just learned about self-reducibility in class.  My professor and our textbook would not commit to saying that all problems in NP are self-reducible, but there didn't seem to be any examples of problems that are not.  I was wondering if there are any examples, or if it's just a situation where you can't prove a negative easily.  Wikipedia only says It is conjectured that the integer factorization problem is not self-reducible.

Googling found one result, which seems to state that planar graph 4 coloring is not self-reducible because LF-k coloring for a planar graph reduces to that reduction, but I couldn't quite follow the proof right now.

Is this an actual example of a self-reducibility disproof, and are there others?

The paper indeed shows that planar graph four coloring is not self-reducible in the sense of Schnorr. There are several other senses, under some of which every problem in P is self-reducible. See the follow-up paper of Große, Rothe and Wechsung. I am not aware of any other result of this kind. Going over all papers citing the paper you mention (this can be done using Google Scholar, for example), none give any such problems.


Max heap and array relation This question is about max heap and array

  Suppose there is max heap $h$, with $n$ data items already stored in $h$. An array that is formed by inserting a value larger than all the values in $h$ at the beginning/head of the heap $h$ is assumed to be new array $C$.
  The array $C$ is a heap  (or)  not?

My answer: is heap because it's bigger than any other element in array

  With $n$ data items already stored in heap $h$, a new array $D$ is created by adding a value $u$ to the heap $h$ that is smaller than any of the $n$ items already stored in heap. If $u$ is added to last element in heap $h$, is array $D$ heap or not?

My answer: it is heap because the smallest one has to be in the leaf

But what is the relation with array? Is there rule to insert node in heap?
I know that to insert node to array in heap we insert data as last element of heap and then put it in the root and heapify it.

Suppose an array $A$ is a maxheap.  Inserting a large element in the first position of $A$ does not necessarily preserve the maxheap property.  The maxheap property requires a node's value to be larger than both its children's values, for each node in the tree.  If the value inserted in the first position is larger than all values in the array, then the maxheap property is preserved at the root node, but might not be preserved at some of the other (lower level) nodes.

We can construct an initial array $A$ such that the nodes in the subtree rooted at the right child of the root have much larger values than the nodes in the subtree rooted at the left child of the root. When a new value is inserted in the first position of the array, the tree changes so that the smaller values in the left subtree become parents of the larger values in the right subtree, causing the maxheap property to be violated. For example, take $A=[6,3,5,2,1,4]$, which is a maxheap.  Inserting a $7$ in the beginning modifies $A$ to $A=[7,6,3,5,2,1,4]$, which is not a maxheap because the node with value $3$ is a parent of the node with value $4$.


How to create a regular expression for this language? I have a language:

$$ \{a^jb^k \mid j \neq k \text{ and } j \equiv k \pmod 3 \}$$

I want to prove that this language is regular. My first thought was to create a regular expression that accounts for all three of the cases of modulo 3 like such:

$$(aaa)^*(bbb)^* | a(aaa)^*b(bbb)^* | aa(aaa)^*bb(bbb)^*$$

However, this doesn't account for the fact that $j$ cannot equal $k$. Is there a way to exclude certain cases like this in a regular expression?

Your language $L$ is not regular.
Suppose that it was regular, then its complement $\overline{L}$ is also regular and the intersection $M = \{ a^j,b^k \mid j=k \vee j \not\equiv k \pmod{3} \}$ between $\overline{L}$ and $\{a^j,b^k \mid j,k \ge 0\}$ is regular.

Let $n$ a sufficiently large multiple of $3$ and consider the word $a^n b^n$. By the pumping lemma there is some $1 \le \ell \le n$ such that all words of the form $a^{n+i\ell} b^{n}$ belong to $M$, for all choices of an integer $i \ge -1$.

We pick $i=3$, so that the resulting word is $a^{n+3\ell} b^{n}$. Clearly $n+3\ell \equiv n \pmod{3}$ while $n+3\ell \neq n$. This shows that  $a^{n+3\ell} b^{n} \not\in M$, a contradiction.


Trying to find all possible combinations I am trying to find all the combination of options trades that make the highest profit. Each trade has a maximum profit and maximum loss. I have a list of maximum losses e.g. [5298, 1100, 500]. Each number corresponds to a trade. The combination of maximum losses must be under the money I have in my account, for example, 9000. I'm trying to subtract each number in the maximum loss array from the money in my account and repeatimg it until it gets to 0 or a negative number. It then advances to the next number. This will miss many combinations because it doesn't try the first AND second AND third at the same time. Does anyone know of an algorithm or know how to find and algorithm to find such combinations or have a better idea than mine? This is the pseudocode I have come up with:

for loop through max loss array
find difference between moneyInAccount and max loss[0]
if difference > maxLoss[0] then
difference = difference - maxLoss[0]
or else index to next maxLoss
if maxLoss[1] > difference
then difference - difference - maxLoss[1]
and so on

This might be a bit advanced for your level (I'm not sure where you're coming from), but this is technically a Knapsack problem. If you're unfamiliar, I suggest first reading a bit from Wiki: https://en.wikipedia.org/wiki/Knapsack_problem

Each of your options has a maximum loss, and some value to you. (I'm not quite sure what your value function here is -- is it the maximum profit? Or maybe $(max\,\,profit - max\,\,loss)/2$?) You have a cap on how much loss you'll assume as risk: your available money. Given that cap, you want to maximize your value.

If you think of the Knapsack as carrying options, then you have a "weight" on each option that is its maximum loss, and your max "weight" you bear is the money you have to risk. You want to maximize the value of your knapsack.

Now, the Knapsack problem is in general NP-hard: this means that no one has a solution to always find the true optimum quickly, and it's unlikely there ever will be. But, there are algorithms that do extremely well for most problems, or give approximate solutions. The Wikipedia article discusses a few.

From a practical perspective, one of the best options is running this as an "Integer Linear Programming" problem, or ILP. Writing your own ILP solver is hard, but there are good software libraries for it. There are also lots of tutorials online about tackling stock portfolio problems with ILP libraries. For instance, a minute of googling "Integer linear progrmaming stock option" took me to https://www.mathworks.com/help/optim/ug/maximize-long-term-investments-using-linear-programming.html, which talks about doing it in MATLAB. You can find many more, probably for Python and Java and R, to name a few likely candidates.


Why language is not regular Taken from site "Geeks For Geeks".
The lemma: "A concatenation of pattern(regular) and a non-pattern(not-regular) is also not regular language."

example: $\left \{L={a^{n}b^{2m}|n\geq 1,m\geq 1} \right \}$

I think I managed to build dfa (q2 is an accepting state) for language. perhaps I'm wrong...

Yes, you are absolutely right.  GeeksforGeeks is just wrong in this case.

Your analysis is correct.  The language $L=\{a^n b^{2m} \mid n \ge 1, m \ge 1\}$ certainly is regular.  Your DFA seems fine.  I don't know why the GeeksforGeeks article claims it is not; but in any case they are wrong.  It's a strange example; even by their own notions of what counts as a "regular pattern", $b^{2m}$ is a "regular pattern", so I don't know why they are giving that example.

Even if we try to look at better examples, the claim is still wrong.  For instance, consider the language

$$L = \{a^n a^p \mid n \ge 0, p \text{ is prime}\}.$$

This language is described by the concatenation of a "regular pattern" and a "non-regular pattern", so that article claims it should be not regular -- but they're wrong.  In fact, $L$ is regular, as $L  = \{a^m \mid m \ge 2\}$.

This whole notion of a "regular pattern" and "non-regular pattern" in that article is pretty much baloney.  I realize what they're trying to do -- they're trying to look for a shortcut to quickly tell whether a language is regular based on the syntax of the description of the language -- but those proposed rules are not a reliable way to tell whether a language is regular or not, and the notion of a "regular pattern" is not well-defined.  That's not a standard concept -- it's just something someone on the Internet made up.  At best, it is a way to form a quick guess at whether a language is regular or non-regular -- but I would recommend always following that up by proving your guess is correct, as their proposed rules are a bit dodgy.

Perhaps a lesson is to rely on primary sources, like well-regarded textbooks, and don't trust too much what you read on the Internet.


Solving recurrence relation where the $f(n)$ has some constant factor $k$ where $0 < k < 1$ I am trying to see if a recurrence relation where $f(n)$ has some constant factor $k$, e.g. $f(n)=kn$ where $0 < k < 1$, is $O(n)$. I am reaching a different result depending which route I take. Given the following recurrence relation:

$$T(n)=2T(\frac{n}{2})+f(n)$$
$$T(n)=2T(\frac{n}{2})+kn$$
Since $0 < k < 1$, we can represent $kn=n^c$, where $0 < c < 1$

This falls under the case 1 of the Master Theorem, because $a=2, b=2$, and therefore $log_b a = log_2 2 = 1 > c$.

It's $O(n)$.

But if I try to unfold the recurrence:
$$\begin{split}T(n) & = 2T(\frac{n}{2})+kn \\
& = 4T(\frac{n}{4})+2kn \\
& = 8T(\frac{n}{8})+3kn \\
& = ... \\
& = 2^cT(\frac{n}{2^c})+ckn \\
\end{split}$$

When $\frac{n}{2^c}=1$, $n=2^c$, then $log_2 n = c$.

So now it's $T(n) = nT(1) + kn log_2 n$, which is $O(n log_2 n)$. Now I am confused.

The error is where you claim that $kn=n^c$ where $0<c<1$.  This is not correct.    Even when $k<1$, it is still the case that $kn=\Theta(n)$; it is not $O(n^c)$ for any $c<1$.  (Check the definition of big-O notation.)


How does this unsigned subtraction work? Modern computers don't have circuits dedicated for subtraction. They do it by using the method of complements.

All is well when the 2 operands are signed 2's complement numbers. The result of addition will be another 2's complement which, when interpreted as a 2's complement number, will give the correct result provided that there's no overflow.

Now consider a 4 bit number. The unsigned range is 0 <-> 15. Signed range is -8 <-> 7.

What happens when I do 15u - 14u? The first thought which comes is "Do the 2's complement of 14 and do 15 + (-14)". But then, -14 is not in the range of a 4 bit number.

But if I do it anyway (Flip all bits and add 1):

   1111
 + 0010
------------
1  0001  =  0001 (4 bits)

It works. But 0010 is not even a negative 2's complement number. It is just 2. However, 0010 is the additive inverse of 14 for 4 bits. Is it a coincidence?

Question: Why does it work? And is this even the actual way it's happening?

In your example, what you are really doing is
$$
15 - 14 \equiv 15 + (16 - 14) \pmod{16}.
$$
To compute $16 - 14$, you first compute $15-14$ (flipping all bits), and then add $1$ to get $16 - 14$.


Why does the Turing Machine allow for multiple final states? Why does the Turing Machine allow for multiple final states when it would be simpler yet equivalent to work with just one? Why allow additional unnecessary states?

Is there some historical reason for this? Is the concept of multiple final states useful in any way? (Perhaps something akin to the ease of use of multi-track Turing machines, even though they're equivalent to standard ones?)

I've never seen a definition of Turing machines that allows multiple final states. All the definitions I've seen either have a single "halt" state or one "halt and accept" state and one "halt and reject" state.

There's no benefit to having multiple final states, though there's no real harm, either. In a finite automaton, it makes sense to have multiple final states because the automaton terminates when it runs out of input and whether or not the last state is final determines whether or not it accepts its input. (I prefer the term "accepting state", for this reason.)  But, for Turing machines, the machine halts precisely when it enters a final state, regardless of what's happening on the state.  So, if you have a Turing machine with multiple final states, you could just delete all but one of them and rewrite the transition function to jump to the one that remains, instead of the ones that were deleted.


How hard is it to decide if there exists a strict improvement of a given solution of an NP-complete problem? Take the Set Cover problem as an example. When we ask if there is a set of size k that covers all the elements, the problem is NP-complete. Now if we ask, for a given set $S$ of size $k$, if there exists another set that covers strictly more elements than $S$ does. Is this problem still NP-complete?

To be clearer, let's think about the Set Cover problem as an optimization problem: what is the maximum number of elements that can be covered by $k$ sets. The decision version is: are there $k$ sets that cover at least $m$ elements? (where $m$ is part of the input, and the version you were saying is simply the special case when $m=n$). Now the problem is, for $k$ given sets (as part of the input), does there exist $k$ other sets that cover strictly more elements than the $k$ given sets do.

Here is a reduction from Set Cover to your problem. Let $(\{S_1,\ldots,S_m\},k)$ be an instance of Set Cover, and let $U = S_1 \cup \cdots \cup S_m$. Let $x_1,\ldots,x_k$ be $k$ new elements, and consider the following instance of your problem:

The sets are $S_i \cup \{x_j\}$ for $i \in [m]$ and $j \in [k]$, together with the set $U$.
The given cover consists of $S_1 \cup \{x_j\}$ for $j \in [k-1]$ together with $U$.

The given cover covers all elements but $x_k$. There is a cover which covers more elements – that is, all elements – iff $U$ can be covered by at most $k$ sets from $S_1,\ldots,S_m$.


Maximimal Independent Set on Ring and Path Let's consider distributed version of algorithm for finding MIS of any graph $A$.

For details, MIS - Maximimal Independent Set.

Slow version of distributed algorithm for MIS, page 2 -  Distributed algorithms. Maximal Independent Set

In worst case, time complexity of the algorithm is $\text{O}(n)$ and a message complexity is $\text{O}(m)$. If nodes of the network are not unique than it's not possible to find MIS.

I am interested in few special cases, when the graph is a path and ring.

Exercise: Consider a path graph $G$ with vertex UIDs to be a random permutation of $\{1,…,n\}$, time complexity of MTS_Slow is $T \leq c\log n$ for a constant $c$ with probability $1-\frac{1}{n}$.
What is a time complexity and it's probability on a ring $G$ with vertex UIDs to be a random permutation of $\{1,…,n\}$.

Ideas: Time complexity has $\log n$ factor, therefore on each phase number of candidates for MIS nodes from a path graph $G$ should be divided by constant factor. Lets consider the worst case, when only one node is choicen to join MIS on each phase, it occurs when the nodes' UID's are located in increasing or decreasing order, it happes with probability $P(B)=\frac{1}{2^n}$, $P(A)=\frac{1}{2}$, where B - nodes' UID is placed in increasing order, A - the next node's UID is bigger the the current one. But how to show that the number of candidates is getting lower by any arbitrary constant factor. The problem is I have a difficulties in defining probability for taking arbitrary constant factor of nodes on each phase.

Case with ring should be similar to a path graph case.

I will appreciate any help in solving this exercise.

if a node terminates the algorithm after an iteration with probability $1/c$, then after $k$ iterations this probability is $c^{-k}$. and the number of iterations required is $\ln _c n$. This is done by arguing that the expected number of nodes after $k$ iterations is $n c ^{-k}$, and we want to make this value less or equal to 1. We achieve this by setting $k$ to $\ln _c n$.

Therefore, replacing $k = \ln _c n$ leads to $c^{- \ln _c n} = 1/n$, and whence the probability of correctness is $1 - 1/n$.

How to find $c$ ? As I said in my comment, I truly dont know the exact value. Here is a solution. Someone else may correct me.

We should calculate the probability that a node $v$ terminates the algorithm in any given iteration. This happens if $v$ is greater than its two neighbors OR if the left neighbor of $v$ is greater than all its neighbors OR if the right neighbor of $v$ is greater than all its neighbors. The probability of any of these events is 1/2*1/2 = 1/4. The probability of any of these events is 1/4 + 1/4 + 1/4 = 3/4. Therefore $c = 3/4$.


Enumerate all pairs, in order of increasing distance, efficiently Given $n$ points in 2D, e.g., $p_1,p_2,....,p_n$, there are $n^2$ possible pairs of points.  I want to output the list of $n^2$ pairs, but sorted according to their distance (e.g., the pair of two points that are closest is the first pair in the output, and so on).

Is there an algorithm to do this with running time better than $O(n^2 \log n)$?  If there was no metric property and the "distance" of each pair of points was unrelated to all other distances, the lower bound would be $\Omega(n^2 \log n^2)$ based on the lower bound for sorting $n^2$ values, but perhaps we can use the properties of the Euclidean distance to do better?

Consider all the point on the x-axis, then you are describing sorting $X-X$. A special case of $X+Y$ sorting(one can actually show they are equivalent in terms of running time). This is not known to be sortable in less than $O(n^2 log n)$ time. Interestingly $O(n^2)$ comparisons suffice.


Known bounds on space complexity of multiplication decision problem Given three numbers $m$, $n$ and $p$ in interleaved binary encoding1, it's obviously possible to check in $O(1)$ space whether $m+n=p$. It's less obvious2 that it isn't possible  to check in $O(1)$ space whether $m\cdot n=p$. I wonder whether one can prove that it isn't possible to check in $O(\log N)$ space3 whether $m\cdot n=p$. On the other hand, are there any known non-trivial upper bounds on the space complexity of this problem, like $O(N/\log N)$?

The problem described above is a simplified version of the "Multiplication decision problem: Is the $k$th bit of the product of $m$ and $n$ a one?" Since this problem is more "powerful" (and also better known), I wonder whether one can show that this problem can't be decided in $O((\log N)^2)$ space.

1. The interleaved binary encoding starts with the lowest significant bit, and allows "leading" zeros for the most significant bits.

2. The proof idea I have in mind would use such an algorithm as building block for a decision procedure of Robinson arithmetic. I call this less obvious, because the fact that Robinson arithmetic is undecidable may be well known, but still remains non-trivial.

3. Here $N$ is the length of the input $m$, $n$ and $p$ in binary encoding.

You can do it in $O(\lg N)$ space, if you're willing to accept a randomized algorithm with an exponentially small probability of error.  In practice, this algorithm is practical and every bit as good as a deterministic algorithm with no possibility of error.

The idea is to choose a random $\ell$-bit prime $\alpha$, reduce $m,n,p$ modulo $\alpha$, and then check whether the congruence $m\times n \equiv p \pmod{\alpha}$ holds modulo $\alpha$.  This test can be done with $O(\ell)$ bits of space (about $3\ell$ bits).  Moreover, it suffices to take $\ell = O(\lg N)$.  In particular, if you want the probability of error to be at most $1/2^t$, it suffices to take $\ell=O(t + \lg N)$.  The constants hidden by the big-O notation are small (something like 3 or so).

Now take $t=100$, and you get a practical algorithm.  The probability of error is $1/2^{100}$, which is so small as to be negligible.  It's more likely that you have a cosmic ray bit flip that causes your computation to give the wrong answer than that you get a wrong answer due to bad luck.  (And cosmic ray bit flips affect deterministic algorithms, too, so the notion of an algorithm with zero error is not something that can be implemented in the real world; the best we can hope for is for the probability of error to be negligible.)

The analysis of this relies upon the prime number theorem.  I don't have time to write out the full analysis right now, but the basic idea is that the algorithm gives the wrong answer only if $\alpha$ divides $mn-p$.  Since $|mn-p|$ is (at most) $2N$ bits long, there can be at most $2N/\ell$ distinct $\ell$-bit prime divisors of $mn-p$.  Also, by the Prime Number Theorem, there are about $2^{\ell}/\ell$ possible $\ell$-bit primes.  Therefore, the probability that the randomly chosen $\alpha$ happens to divide $mn-p$ is at most $(2N)/2^{\ell}$.  Now solve for $\ell$, and you get the result I claimed above.

Importantly, the probability of error is taken only over the internal coin flips of the algorithm, not over the possible values of $m,n,p$.  In other words, even if an adversary chooses the values of $m,n,p$, the probability of error will still be at most $1/2^t$.


Research work on computational models for a "specific" person's behaviors Is there active research work on creating computational models of a "specific" person's behaviors (general behaviors, emotions, actions...)? What are some references for such research? I tried google and scopus and did not have much luck.

I have worked on modeling movement behaviors of pedestrians in crowd (for my PhD work), but I am planning to work on the simulation of general behaviors of individuals (based on the historical data of their actions and behaviors).

I am more inclined to use machine learning methods than detailed mathematical models.

this is a broad area now overlapping with big data and (mass) surveillance technology. here are a few refs with scientific elements/ angles/ leads/ papers/ books etc. and reference to a new field of "social physics"

‘Social Physics’ Harnesses Big Data to Predict Human Behavior / Leopold
'Big data' reveals human interests, behavior / Kullman, physorg
What Can Big Data Ever Tell Us About Human Behavior? / Zwilling, Forbes


What is a "negative function" withing algorithms? I am currently studying the book 3rd edition CLRS Algorithms textbook, Chapter 3. I had the exact same question as this post but I have one more question now:
What is a negative function?
These functions are estimates that describe the time it takes to perform a function (an algorithmic sequence) onto a list. How can the function be negative if it describes the time it takes to do work? Can an algorithm sort a list 10 seconds before it starts?

The big-O notation (and also similar notations, such as big-Omega) are not inherently limited only to describe running time of algorithms. Indeed, when the context is the running time of some algorithm, there are no negative functions since algorithms cannot run "negative time".
That being said, the big-O notation is a general mathematical definition. It could be used for other things as well, as shown in this Wikipedia page.


Lower space bound on a turing machine accepting palindromes Let
$$
PAL = \lbrace x \in \lbrace 0, 1, \# \rbrace^* | x = rev(x) \rbrace
$$
How do I show that a turing machine deciding $PAL$ must use space $\Omega(\log n)$?

I have a feeling that I need to use crossing sequences when crossing the middle of the input tape, but I'm not sure how to relate that to space.

Hint: A Turing machine running in space $S$ runs in time at most $\exp S$.