Is Morse Code binary, ternary or quinary? I am reading the book: "Code: The Hidden Language of Computer Hardware and Software"  and in Chapter 2 author says:

  Morse code is said to be a binary (literally meaning two by two) code
  because the components of the code consists of only two things - a dot
  and a dash.

Wikipedia on the other hand says:

  Strictly speaking it is not binary, as there are five fundamental
  elements (see quinary). However, this does not mean Morse code cannot
  be represented as a binary code. In an abstract sense, this is the
  function that telegraph operators perform when transmitting messages (see quinary).

But then again, another Wikipedia page includes Morse Code in 'List of binary codes.'

I am very confused because I would think Morse Code actually is ternary. You have 3 different types of 'possibilities': a silence, a short beep or a long beep.

It is impossible to represent Morse Code in 'stirct binary' isn't it?

By 'strict binary' I mean, think of stream of binary: 1010111101010.. How am I supposed to represent a silence, a short beep and / or a long beep?

Only way I can think of is 'word size' a computer implements. If I (and the CPU / the interpreter of the code) know that it will be reading 8 bits every time, then I can represent Morse Code. I can simply represent a short beep with a 1 or a long beep with a 0 and the silences will be implicitly represented by the word length.(Let's say 8 bits..) So again, I have this 3rd variable/the 3rd asset in my hand: the word size.

My thinking is like this: I can reserve the first 3 bits for how many bits to be read, and last 5 bits for the Morse code in a 8bit word. Like 00110000 will mean 'A'. And I am still in 'binary' BUT I need the word size which makes it ternary isn't it? The first 3 bits say: Read only 1 bit from the following 5 bits.

Instead of binary, if we use trinary, we can show morse code like: 101021110102110222 etc.. where 1 is: dit 0 is: dah and 2 is silence. By using 222 we can code the long silence, so if  you have a signal like *- *---    *-  you can show it like: 102100022210, but it is not directly possible using only with 1's and 0's UNLESS you come up with something like a 'fixed' word size as I mentioned, but well this is interpreting, not saving the Morse Code as it is in binary. Imagine something like a piano, you have only the piano buttons. You want to leave a message in Morse Code for someone and you can paint buttons to black. There is no way you can leave a clear message, isn't it? You need at least one more color so you can put the silences (the ones between characters and words. This is what I mean by trenary.

I am not asking if you can represent Morse Code in 57-ary or anything else.

I have e-mailed the author (Charles Petzold) about this; he says that he demonstrates in Chapter 9 of "Code" that Morse Code can be interpreted as a binary code.

Where am I wrong with my thinking? Is what I am reading in the book, that the Morse Code being a Binary a fact or not? Is it somehow debatable? Why is Morse Code is told be quinary in one Wikipedia page, and it is also listed in List of Binary Codes page?

Edit: I have e-mailed the author and got a reply:

-----Original Message-----

From: Koray Tugay [mailto:koray@tugay.biz]

Sent: Tuesday, March 3, 2015 3:16 PM

To: cp@charlespetzold.com

Subject: Is Morse Code really binary?

Sir, could you take a look at my question here: Is Morse Code binary, ternary or quinary? quinary ?

Regards, Koray Tugay

From: "Charles Petzold"

To: "'Koray Tugay'"

Subject: RE: Is Morse Code really binary? Date: 3

Mar 2015 23:04:35 EET

Towards the end of Chapter 9 in "Code" I demonstrate that Morse Code can be interpreted as a binary code.

-----Original Message-----

From: Koray Tugay [mailto:koray@tugay.biz]

Sent: Tuesday, March 3, 2015 3:16 PM

To: cp@charlespetzold.com

Subject: Is Morse Code really binary?

Sir, could you take a look at my question here: Is Morse Code binary, ternary or quinary? quinary ?

Regards, Koray Tugay

I am not hiding his e-mail as it is really easy to find on the web anyway.

This answer isn't as long as it looks; this site just puts a lot of spacing between list items! Update: Actually it's getting pretty long...

Morse Code isn't "officially" binary, ternary, quaternary, quinary, or even 57-ary (if I count correctly). Arguing about which one it is without context is not productive. It is up to you to define which of those five it is based on your application and the encoding requirements for your specific situation. To that end, there are pros and cons to each symbol set size, which you should consider for your situation before making a decision.

For the basis, M.1677, the international Morse Code standard, section 2, defines timings as:

  2 Spacing and length of the signals
  2.1 A dash is equal to three dots.
  2.2 The space between the signals forming the same letter is equal to one dot.
  2.3 The space between two letters is equal to three dots.
  2.4 The space between two words is equal to seven dots.

Note that that defines timings only, e.g. a dash does not mean the same thing as three dots, it is simply the same length. The base unit of time is a dot.

Binary

We can choose binary if we'd like. It is possible to represent Morse Code with "strict binary", as you call it -- that author's approach was to assign the digits to "dot" and "dash". That approach does not work and I do not think the author has a firm grasp of Morse code. But there is a different approach that works. If we choose binary, we essentially represent whether the signal is high or low with each symbol occupying a single dot-lengthed time slice. Note that this is also the approach described on the List of Binary Codes page you cited.

Other binary codings can be chosen as well (e.g. Bob Jarvis' answer) at the expense of increases in difficulty decoding back to audible Morse Code (Bob's encoding cannot be decoded statelessly, for example, the tradeoff is it provides shorter encoded sequences).

Symbols:

Low, off, etc. (0)
High, on, etc. (1)

Encoding Examples:

Signal separator: 0
Letter separator: 000
Word separator: 0000000
Three dots: 10101
Three dashes: 11101110111
The word "son": 101010001110111011100011101
The phrase "is a": 10100010101000000010111

Pros:

Minimal symbol set size
Easily managed with typical digital logic
Easy to decode into audible Morse Code (presuming no validation is done); stateless decoding and does not require storing information about the timing of symbols (every symbol is the same length).

Cons:

Long encodings.
Many opportunities for invalid encodings.
Individual symbol meanings (0, 1) depend on context.

Ternary

With this choice, we define letter and word spacings as rests, and signal spacings are implicit (although you could choose to require dot length rest symbols between signals, if it suits you better).

Symbols:

Dot-length rest (0)
Dot (1)
Dash (2)

Encoding Examples:

Letter separator: 000
Word separator: 0000000
Three dots: 111
Three dashes: 222
The word "son": 11100022200021
The phrase "is a": 11000111000000012

Pros:

Small symbol set size.
Signal separator no longer needed.
Shorter encoding lengths than binary.
Removes some invalid encodings (e.g. 0110 with the binary choice no longer possible).

Cons:

Still lengthy encodings.
Still many possibilities for invalid encodings, in particular, the rests.
Cannot be decoded statelessly† unless you choose to place explicit dot length rests between signals.
Signal separators are implicit‡ unless you choose to place explicit dot length rests between signals.
Some individual symbol meanings (0) depend on context.

Quaternary

Symbols:

Letter separator (0)
Word separator (1)
Dot (2)
Dash (3)

Encoding Examples:

Three dots: 222
Three dashes: 333
The word "son": 2220333032
The phrase "is a": 220222123

Pros:

Very short encoded length.
Possibility of invalid encodings is reduced.
Symbols are semantically accurate.
Arguably, more human-readable.

Cons:

Large symbol set size.
Cannot be decoded statelessly.†
Signal separators are implicit.‡

Quinary

A direct interpretation of Wikipedia's list. Note this is very similar to the binary choice except the various valid combination of binary 0's or 1's are given their own symbols.

Symbols:

Signal separator (0)
Letter separator (1)
Word separator (2)
Dot (3)
Dash (4)

Encoding examples:

Three dots: 30303
Three dashes: 40404
The word "son": 303031404041403
The phrase "is a": 3031303032304

Pros (compared to quaternary):

Can be decoded statelessly.
The only symbol set size that unambiguously, directly and concisely represents the five objects mentioned in section 2 of the standard: "dot" (to which all timings are relative to), "dash", "space between the signals", "space between two letters", "space between two words".

Cons (compared to quaternary):

Higher possibility for invalid encodings.
Increased encoding lengths without adding extra information (tradeoff is decoding ease).
Not as easy to decode as the binary choice, in that each symbol is a different length in time and this association must be maintained somewhere.

57-ary:

Included for completeness.

Symbols:

26 letters
10 numbers
20 punctuation marks and miscellaneous signs
Word separator (space)

Encoding Examples:

The word "son": son
The phrase "is a": is a

Pros:

Shortest encoding
Human readable
Invalid encodings are impossible.

Cons:

Largest symbol set
Difficult to decode into Morse Code; necessary to maintain tables of Morse Code output sequences for each symbol and necessary to detect word boundaries and adjacent letters to determine where to insert various rests.
Impossible to expand beyond the Morse Code specification without adding new symbols (tradeoff for being immune to invalid encodings).
Signal and letter separators are implicit.‡

Termination

For storage as a symbol stream on a device, if you need to do that, it's worth noting that M.1677 defines message and transmission termination sequences. From Part II:

  5 Every telegram shall be terminated with a cross signal (. – . – .)
  6 The end of the transmission shall be indicated by the cross signal (. – . – .) followed by the invitation to transmit signal K (– . –)
  7 The end of work shall be indicated by the station that transmitted the last telegram. The correct indication is the end of work signal (. . . – . –)

Unfortunately, the standard is silent on the ability to distinguish e.g. the string "+K" from the sequence (end-of-telegram, invitation-to-transmit). However, end-of-work is unique. If you are storing morse code, then, you will have to make a choice as to how you want to indicate the end of a stored sequence.

If you are storing an entire conversation, for example, and are using the binary symbol set, you could reasonably consider end-of-work to be the end of sequence indicator, represented as the unique bit sequence 101010111010111. You need to consider the type of data you are storing (e.g. message fragments, entire messages, entire conversations) as well as the facilities offered to you by your storage medium (e.g. ability to prefix with message length) before deciding. I suppose you could go so far as to define your own end of sequence indicator. In any case these are all matters of underlying storage and have too many possibilities to list here. The choice is really up to you based on whatever is appropriate for your situation.

† Cannot be decoded statelessly: These encodings require some state to be maintained in order to decode into audible Morse Code. They all require "If preceding symbol was a dot/dash and current symbol is a dot/dash then insert signal separator". While you could try and "cheat" and automatically append a signal separator to all symbols while reducing word separator to 5 rests and letter separator to 1, M.1677 afaict does not explicitly prohibit consecutive word separators, which breaks this kludge.

‡ Signal separators are implicit: This is directly related to the above note but more semantically oriented. These encodings have implicit signal separators in their notation. That is "zzz" is intuitively three separate z's, the boundaries are "piggybacked" on whatever it is that separates symbols in the encoding itself. Consider the description "three dots in a row"; intuitively we take this to mean three separate dots, but if separators weren't implied this could be taken to be indistinguishable from a dash. Only the Wikipedia-style binary and quinary (or ternary with the explicit signal separator option) representations remove all ambiguity and "shortcuts" here, which can be of great value depending on the situation. It is for this reason that there is a strong argument for the quinary choice.

TL;DR:

As you can see, there are advantages and disadvantages to each, and it's up to you to decide how you want to treat it based on your requirements. There is no right answer. You could attempt to argue that one is more appropriate than the other in general, but these arguments would boil down to pedantic preferences, as without context, there is no correct answer.

Now, all that said, in my own opinion, the quinary choice is the representation that feels the most "right" to me for Morse Code itself (originally I had favored quaternary). It is the only choice that provides all of the following:

Context-free symbols (a symbol on its own contains all information about its meaning without examining adjacent symbols).
Representation of all primitives defined in M.1667.
Separators (signal, letter, word) are not implied by notation or underlying encoding (this is important, if I wrote { dot, dot, dash }, those ,'s are significant and easy to overlook).

However, there are strong arguments for all. The arguments related to encoding are also applicable to the treatment of Morse itself. There is no 100% concrete answer, but it can certainly make a good topic for debate with your friends at the bar.

. . . – . –

Originally Morse code was intended to be written marks on a strip of paper, but telegraph operators soon became able to "read" the clicks of the equipment. This version of Morse (American or "land" Morse) had three "mark" elements, the dot, the dash, and the long dash.

The use of International Morse during the last century, via radio transmission, was usually encoded by hand (on a telegraph key) and decoded by ear, by listening to the pattern of beeps produced by the receiver. Skilled operators could receive better than unskilled ones, and some people could produce code that was easier to understand than that of others. A good transmitting operator was said to have a "good fist." An inept operator was called a LID. (For the origin of "lid" -- which I believe comes from a common error in American Morse of sending LID for DD, daaahh, dit dit, dah dit dit instead of dah dit dit, dah dit dit -- see this reference: https://english.stackexchange.com/questions/31818/how-did-the-word-lid-come-to-mean-poor-operator-in-the-context-of-telegraph .)

Thus it follows that the "encoding" of Morse into a binary format depends upon purpose, and thus whether the quality of "good fist" versus "poor fist" is to be retained. Is a string of on-and-off switching to be matched to a clock and "corrected" for difficulties in phase or duration of each portion of the signal? Or is it instead to be sampled at a rate sufficient to retain random or confusing variations, presumably for later inspection or delight?


Computer architecture pipelining LOOP:LW    R1,0(R2)
     ADDI  R1,R1,#1
     SW    R1,0(R2)
     ADDI  R2,R2,#4
     SUB   R4,R3,R2
     BNEZ  R4, LOOP

If we want to move an instruction into a branch delay slot what will be that instruction and the schedule of the instructions?

In the solution they have brought SW R1,0(R2) into the branch delay slot like this:

LOOP:LW    R1,0(R2)
     ADDI  R2,R2,#4
     SUB   R4,R3,R2
     ADDI  R1,R1,#1
     BNEZ  R4, LOOP
     SW    R1,0(R2)

But according to me it will change the meaning of the program since R2 will be incremented by 4 before storing the word. Can anyone clear this?

There is an instruction already in the branch delay slot - it's just not displayed. So unless that instruction that isn't displayed is a NOP instruction, it will not be executed anymore if the branch is performed, so the meaning of the program has changed. Unless the question is "here is the code for a processor without branch delay slots, modify it for a processor with branch delay slots". In which case the obvious solution is to just move the last instruction before the conditional branch to the branch delay slot.

Independent of branch delay slot, you cannot just move the SW instruction which uses R2 past an instruction that modifies R2. In this case, you can move it if you modify it: R2 is increased by 4, so you can use the address -4(R2) instead of 0(R2).

In general, you initially don't care about branch delay slots and write code as if there were no branch delay slots, and add a NOP after each conditional branch, so you have correct code.

Then you move instructions into the branch delay slots, but carefully: You mustn't move an instruction if there is a branch to the conditional branch (because that instruction would be wrongly executed when branching to the conditional branch). You can't move certain instructions, like branches, returns, calls. And you can't move an instruction that was already moved. Say x = 0, branch if zero, not, branch if not zero, not. You can move the x = 0 into the first branch delay slot, but you mustn't move it into the second one.

Yes, moving an instruction must not change the meaning of the program.
However, as you correctly identified, the sw instruction uses R2 which is later being incremented by 4. Thus unless the instruction is changed to sw R1, -4(R2) (as suggested by Sai), the altered program may perform differently.


Guessing the smallest unique positive integer Let us consider the following game: there are some players and a computer. Each player inputs one positive integer and his name (player doesn't know another's numbers, just his own). When all the players made their moves, computer outputs a name of winner – who submitted the lowest unique number.

How do you think, what is the best strategy for this game?

There are a number of discussions of this game online, but you should be wary because some of them give incorrect solutions. This website gives an excellent exposition of how to solve this game. (Based in part on this paper.) You assume that all players use the same mixed strategy, and that when all players use this strategy, there is a Nash equilibrium. This gives equations which for three players have a closed form solution: you choose the integer $i$ with probability

$$ 0.839286 \cdot (0.543689)^{\textstyle i}$$

where 0.543689 is the solution of $x^3 + x^2 + x = 1$.

For $k$ players, if $k \geq 4$, the equations can still be derived, but they appear to have no closed form solution. However, in the optimal strategy the probability of playing a number larger than $k$ is very small, so an explicit nearly-optimal strategy can be found by solving the equations numerically.

Not enough reputation to comment, but, it is worth noting that if your opponents are playing by the Nash equilibrium strategy Peter Shor described for a 3 player game your chances of winning are around 29.6% irrespective of the number you choose. If you are only playing a single game (so no one can determine your strategy) and consider a draw between all players no better than a loss, a large number such as 89285829358008871 will give you the same chance of victory as a 1 or 2.

In this specific case, there's nothing to lose from trying a different strategy, just in case your opponents don't conform to your assumptions.


Calculate the average length of the linked lists in a hash table I am learning hash tables, and I would like to know how to determine the average length of the linked lists.

For example: A hash table holds about 10,000 employee records. Each record is indexed by the 2-character initials of the employee name, transformed into integers using the mapping: A=01, B=02, C=03, and Z=26. On average no more than 8 comparisons is made every time a search is requested.

How would you determine determine the actual average length of the linked lists, in the hash table, that is pointed to by the hash value slots?

since the hash is constructed such that the input element has an equal chance to be in any of the bins of the hash table, then the average number will be (number of imputed elements) / (size of the hash table)


Turing Completeness of System Which Randomly Fails to Complete Calculations If one were to create a variant of a turing complete language which upon completing a calculation randomly changes the answer by one, would it be Turing complete? For example, say I had a Python implementation which, upon every variable assignment, with probability $\frac13$ decreased the value by $1$, with probability $\frac13$ increased the value by $1$ and otherwise kept the value constant, would it be Turing complete? This seems to be able to perform all of the calculations which Python is able to perform, just not reliably.

I've gone around and around on this one.  It would seem that we've landed on "No, it would not be Turing Complete, although we might be able to approximate it with a bounded probability of error on either accuracy or returning in finite time."

In your post, you said "just not reliably"... that is, in fact, a crucial part of the definition.  To be Turing-complete, we have to be able to exactly simulate a single taped Turing machine -- getting it right "sometimes" isn't any better than flipping a coin to determine if it's raining outside with "50% accuracy".

In the given example, you seem to suggest that the random failures only occur on assignment, not for other operations in the computer.  Does this affect assignments performed by the programmer alone, or internal assignments performed as intermediate steps by the compiler?  If it only affects assignments performed by the programmer, many programs could be written (in horrendously terrifying complexity and near impossible to debug) without creating and assigning any variables at all.  In this case, I suppose it would be similar to a Turing tarpit.

If the programmer HAD to assign variables, they should be able to use something in the vein of the old Heinlein "Tell me 3 times", assigning the variable in an array repeatedly (say 100 times, or until 3 distinct values have been saved) and then use the median value (since all values are x, x-1, or x+1, the median value, not median result, must be the correct one).  This would cut into performance HORRIBLY, but should, typically, arrive at correct values.  (In fairness to @DavidRicherby, I concede that we cannot ensure both that we arrive at an answer and that it is correct with 100% certainty; for a look at how we could arrive at 3 distinct values without additional assignments, consider the following approach:

# function sum : x,y $\rightarrow$ z
var a = x + y;   // first assignment, may be x, x-1, or x+1
var b = x + y;
while (a == b)
  b = x + y;     // if this loop finishes, b is now distinct from a
var c = x + y;
while ((a == c) || (b == c))
  c = x + y;     // if this loop finishes, c is now distinct from a and b
if ((a < b) && (b < c))
  return b;
if ((b < a) && (a < c))
  return a;
// repeat for the other combinations; there should be 6 total if statements.

)

If the compiler can introduce intermediate assignment operations that the programmer did not that also suffer from this drawback (say, at the end of every elementary computation), or if there are other operations affected by this glitch (the killer one in my above example being the comparison operators), then we cannot simulate a Turing-complete language (or machine) at any speed -- we will only be right 1 out of every $3^n$ times on average, where $n$ is the number of operations we can't correct for.

The Short Version of My Answer:

I can try to check for errors internally myself in the midst of computation, which may or may not work depending on the details of your system.  If I can't have or emulate a verifying system, then I cannot be Turing complete -- I'm just guessing at solutions.

Given that popular consensus is that such a verifying system implemented could not guarantee both returning in finite time AND returning an accurate answer, it would appear no, although we might be able to approximate it a reasonable percentage of the time.


Construct two functions $f$ and $g$ satisfying $f \ne O(g), g \ne O(f)$ Construct two functions $  f,g:   R^+ → R^+ $ satisfying:

$f, g$ are continuous;
$f, g$ are monotonically increasing;
$f \ne O(g)$ and $g \ne O(f)$.

There are many examples for such functions. Perhaps the easiest way to understand how to get such an example, is by manually constructing it.

Let's start with function over the natural numbers, as they can be continuously completed to the reals.

A good way to ensure that $f\neq O(g)$ and $g\neq O(f)$ is to alternate between their orders of magnitude. For example, we could define

$f(n)=\begin{cases}
n & n \text{ is odd}\\
n^2 & n \text{ is even}\\
\end{cases}$

Then, we could have $g$ behave the opposite on the odds and evens. However, this doesn't work for you, because these functions are not monotonically increasing.

However, the choice of $n,n^2$ was somewhat arbitrary, and we could simply increase the magnitudes so as to have monotonicity. This way, we may come up with:

$f(n)=\begin{cases}
n^{2n} & n \text{ is odd}\\
n^{2n-1} & n \text{ is even}\\
\end{cases}$, and
$g(n)=\begin{cases}
n^{2n-1} & n \text{ is odd}\\
n^{2n} & n \text{ is even}\\
\end{cases}$

Clearly these are monotone functions. Also, $f(n)\neq O(g(n))$, since on the odd integers, $f$ behaves like $n^{2n}$ while $g$ behaves like $n^{2n-1}=n^{2n}/n=o(n^{2n})$, and vice-versa  on the evens.

Now all you need is to complete them to the reals (e.g. by adding linear parts between the integers, but this is really beside the point).

Also, now that you have this idea, you could use the trigonometric functions in order to construct ``closed formulas'' for such functions, since $\sin$ and $\cos$ are oscillating, and peak on alternating points.

Good illustration for me is:
http://www.wolframalpha.com/input/?i=sin%28x%29%2B2x%2C+cos%28x%29%2B2x

$$
f(n) =2x+sin(x)
$$
$$
g(n) =2x+cos(x)
$$
$$
f\neq O(g)
$$
$$
g\neq O(f)
$$


If inorder traversal of a tree is in ascending order will the tree definitely be a BST? For a binary search tree (BST) the inorder traversal is always in ascending order. Is the converse also true?

Yes.

The proof is straightforward. Assume you have a tree with a sorted in-order traversal, and assume the tree is not a BST. This means there must exist at least one node which breaks the BST assumption; let's call this node $v$.

Now, there are two ways $v$ could break the BST assumption. One way is if there's a node in $v$'s left subtree with label greater than $v$. The other way is if there's a node in $v$'s right subtree with label less than $v$.

But everything in $v$'s left subtree must come before it in the in-order traversal, and everything in its right subtree must come after it. And we assumed that the in-order traversal is sorted.

Thus, there's a contradiction, and such a tree cannot exist.

(EDIT: As RemcoGerlich points out, this is only true if your tree is known to be binary. But if it's not binary, an in-order traversal isn't defined, afaik.)

It is true only if there are no duplicates.


Find shortest path in undirected graph that goes through all vertices and returns to starting vertex I have an undirected weighted graph like this one

My task is to find the fastest path (with least weight) that goes from specified vertex goes through all vertices and returns to the starting vertex without repeating a vertex.

Graph
1 3 time 5
3 2 time 5
2 4 time 5
4 1 time 5
4 3 time 4
1 2 time 5

Starting vertex 3
Path 1: 3->1->4->2->3
Path 2: 3->2->1->4->3
Time 1 and 2: 5+5+5+5=20

Path 3: 3->1->2->4->3
Path 4: 3->4->2->1->3
Time 3 and 4: 5+5+5+4=19 -> fastest

Is there a fastest way than DFS to solve the problem?

Travelling salesman problem looks almost the same but I can't repeat a visited vertex.

Going from vertex 3 to vertex 5 I can't do that
3 -> 2 -> 3 -> 1 -> 3-> 4 -> 3

A solution is: 3->1->2->4->3

That's my function:

private static List<HashMap<Integer,Integer>> graph = new ArrayList<>();

public static void dfs(int currentVertex,Stack<Integer> visited,long currentTime) {
    if(visited.size() == graph.size()-1) {
        if(!graph.get(currentVertex).containsKey(targetVertex)) {
            return;
        }

        currentTime += graph.get(currentVertex).get(targetVertex);
        if(currentTime < fastestTime) {
            fastestTime = currentTime;
        }
        return;
    }

    for (Map.Entry<Integer,Integer> vertex: graph.get(currentVertex).entrySet()) {
        if(!visited.contains(vertex.getKey())) {
            visited.add(vertex.getKey());
            dfs(vertex.getKey(),visited,currentTime + vertex.getValue());
            visited.pop();
        }
    }
}


The difference between dense graph and sparse one How to decide whether the following statement is correct?

O(E log E) and O(E log V) are equivalent regardless whether graph is dense or
sparse

You have to be careful with your definitions. For any graph, the number of nodes and the number of edges is a constant, so $O(V) = O(E) = (1)$. This is clearly not helpful.

Sparse and dense only make sense for a family of graphs $\{G_n\}_{n=1}^\infty$.

The edge density of a graph $G$ is the proportion of possible edges that a graph actually has:

$$ D = \frac{|E(G)|}{{|V(G)|}\choose{2}}. $$

The edge density of a family of graphs is

$$ D = \lim_{n \to \infty} \frac{|E(G_n)|}{{|V(G_n)|}\choose{2}}. $$

The family is sparse if $D = 0$ and dense if $D > 0$. You must analyze the performance of your algorithm under either type of family as inputs.

This definition is from Diestel's Graph Theory.

In mathematics, a dense graph is a graph in which the number of edges
  is close to the maximal number of edges. The opposite, a graph with
  only a few edges, is a sparse graph.

A sparse graph is a graph $G=(V,E)$ in which $|E|=O(|V|)$.

For example, consider a graph $G=(V,E)$ with n nodes. Suppose that the out-degree of each vertex in $G$ is some fixed constant k. Graph $G$ is a sparse graph because $|E|=k|V|=O(|V|)$.

[UPDATE] If $N$ and $E$ are the number of nodes and edges in a network respectively. $N^2$ possible edges in a fully connected network.

Sparseness $P = \frac{E} {N^2} $

If $P << 1$, then the network is sparse.

Source: MIT OpenCourseWare

A dense graph is a graph $G=(V,E)$ in which $|E|=O(|V|^2)$.

For example, consider a graph $G=(V,E)$ with n nodes. $|E|=f|V|^2=O(|V|^2)$.

  How to decide whether the following statement is correct?

  O(E log E) and O(E log V) are equivalent regardless whether graph is
  dense or sparse

In the case of $O(E log E)$ and $O(E log V)$,

asymptotically $log E \approx log V$ and only $E$ contributes to the result regardless the graph is dense or sparse.

Thus,
$O(E log E) \approx O(E log V)$ for any dense or sparse graph.


Graph searching: Breadth-first vs. depth-first When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)).

Now, are there any advantages of one over another?

The ones I could think of:

If you expect your data to be pretty far down inside the graph, depth-first might find it earlier, as you are going down into the deeper parts of the graph very fast.
Conversely, if you expect your data to be pretty far up in the graph, breadth-first might give the result earlier.

Is there anything I have missed or does it mostly come down to personal preference?

I'd like to quote an answer from Stack Overflow by hstoerr which covers the problem nicely:

  That heavily depends on the structure of the search tree and the number and location of solutions.
   If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better. If the tree is very deep and solutions are rare, depth first search (DFS) might rootle around forever, but BFS could be faster. If the tree is very wide, a BFS might need too much more memory, so it might be completely impractical. If solutions are frequent but located deep in the tree, BFS could be impractical. If the search tree is very deep you will need to restrict the search depth for depth first search (DFS), anyway (for example with iterative deepening).

  But these are just rules of thumb; you'll probably need to experiment.

Rafał Dowgird also remarks:

  Some algorithms depend on particular properties of DFS (or BFS) to work. For example the Hopcroft and Tarjan algorithm for finding 2-connected components takes advantage of the fact that each already visited node encountered by DFS is on the path from root to the currently explored node.

I think it would be interesting to write both of them in a way that only by switching some lines of code would give you one algorithm or the other, so that you will see that your dillema is not so strong as it seems to be at first.

I personally like the interpretation of BFS as flooding a landscape: the low altitude areas will be flooded first, and only then the high altitude areas would follow. If you imagine the landscape altitudes as isolines as we see in geography books, its easy to see that BFS fills all area under the same isoline at the same time, just as this would be with physics. Thus, interpreting altitudes as distance or scaled cost gives a pretty intuitive idea of the algorithm.

With this in mind, you can easily adapt the idea behind breadth first search to find the minimum spanning tree easily, shortest path, and also many other minimization algorithms.

I didnt see any intuitive interpretation of DFS yet (only the standard one about the maze, but it isnt as powerful as the BFS one and flooding), so for me it seems that BFS seems to correlate better with physical phenomena as described above, while DFS correlates better with choices dillema on rational systems (ie people or computers deciding which move to make on a chess game or going out of a maze).

So, for me the difference between lies on which natural phenomenon best matches their propagation model (transversing) in real life.


Selection algorithm variant for an array Have a problem that's a variant of the linear time selection algorithm of a randomized array that I'm struggling with.

Let $A = A[1], ..., A[n]$ be an array of $n \ge 4$ distinct keys.
Describe an efficient algorithm to find the three smallest keys in $A$. Use words.
What is the worst case number of comparisons performed by your algorithm? Try to find an exact number. Ignore floors and ceilings. Explain your answer.

I would assume you use the randomized $k$-selection algorithm where $k=3$, but if you're recursively partitioning a group of integers around a pivot I'm not sure how you'd find $k=2$ and $k=1$ short of running the algorithm 3 times.
Ideas?

Well, here's what I came up with.

You could use Merge Sort, which has a worse-case time complexity of $O(n (log (n))$, then take the first 3 values of the array, but it felt like this question was seeking the use of the Randomized Select algorithm.

Best case for Randomized Select would be select $3$ (or $1$) as your random pivot and then make a comparison to the left or right of that for the other two spots, giving you a complexity of $n-1+1$ or $\Omega(n)$.

But this is asking for worst case. By my calculation if an adversary is always picking the furthest pivot from the target (say $k=3$), then the time complexity would be:
$$\frac{n(n-1)}{2} $$
For example. Let's say you have an unsorted array of $7,5,9,8$. The third smallest number is $8$ so the worst pivot is $5$. Compare $7,8,9$ (which is $n-1$ comparisons), you see there are 3 numbers greater.

The next worst pivot is either $7$ or $9$, so pick one of those, and $n-2$ comparisons, you see $8$ and $9$ are greater than 7. You know that $5$ is the smallest, $7$ is the second smallest, but you still need the third smallest. Repeat.

Pick $9$ as your pivot and make $n-3$ comparisons to see that $9$ is the 4th smallest, meaning $8$ is your 3rd smallest.

Add up those comparisons and simplify, you get the formula quoted above. Worst-case this seems less efficient than Merge Sort and selecting the first three numbers, but this seemed like the application of Randomized Select that the question was leaning toward (based on the book and classroom work).

Hope this helps someone else.


Will the future quantum computers use the binary, ternary or quaternary numeral system? Our current computers use bits, so they use the binary numeral system. But I heard that the future quantum computers will use qubits instead of simple bits.

Since in the word "qubit" there is the word "bi" I first thought that this meant that quantum computers would use binary (base 2).

But then I heard that qubits had three possible states: 0, 1, or a superposition of 0 and 1. So I then thought that this must mean that they will use ternary (base 3).

But then I saw that one qubit can hold as much information as two bits. So I thought that this maybe mean that they will use quaternary (base 4).

So which numeral system will the future quantum computers use: binary, ternary or quaternary?

The other answers are nice, but none address the question: what numeric base(s) might quantum computers use? I will answer in two parts: first, the question is a little subtle, and second, you may use any numeric base, and then you work with qutrits or in general with qudits, which lead to qualitatively new intuitions! Or at any rate, I will try to make the case that they do.

A quantum bit isn't just a $0$ or a $1$, it's a bit more complex than that. For example, a quantum bit may be in the state $\sqrt{\frac{1}{4}}|0\rangle+\sqrt{\frac{3}{4}}|1\rangle$. When measured, you will measure the outcome $0$ with probability $\frac{1}{4}$ and the outcome $1$ with probability $\frac{3}{4}$. The 'superposition' you talked about is $\sqrt{\frac{1}{2}}|0\rangle+\sqrt{\frac{1}{2}}|1\rangle$, but in general any pair of complex numbers $a$ and $b$ will do, as long as $a^2+b^2=1$. If you have three qubits, then you can entangle them, and the state will be

$$a_0|000\rangle + a_1|001\rangle+a_2|010\rangle+a_3|011\rangle+a_4|100\rangle +a_5|101\rangle+a_6|110\rangle +a_7|111\rangle$$

But when you measure this three-qubit system, your measurement outcome is one out of these 8 states, that is, three bits. This is this really weird dichotomy where on the one hand quantum systems seem to have this exponential state space, but on the other hand we only seem to be able to 'get at' a logarithmic part of the state space. In 'Quantum Computing Since Democritus', Scott Aaronson probes this question by matching off several complexity classes to try and understand how much of this exponential state space we can exploit for computation.

Having said that, there is an obvious complaint to the answer above: all the notation is in binary. Qubits are in a superposition of two base states, and entangling them doesn't change that much, because three qubits are in a superposition of $2^3$ base states. It's a legitimate complaint, because one usually thinks of $\texttt{unsigned int}$ as a number, and only remembers that it is implemented as a 32-bit string as an afterthought.

Enter the qutrit. It is a vector in $\mathbb{C}^3$, in other words, it consists of three base states rather than two. You operate on this vector with a $3\times 3$ matrix, and all the usual things done in quantum computing don't change much, because any operation expressed in terms of qutrits can be expressed in terms of qudits, so it's really just syntactic sugar. But some problems are much easier to write down and/or think about when expressed as qudits instead of entangled qubits. For example, a variation of the Deutsch-Josza problem might ask, given an oracle for a function $f\colon \{0,\ldots, kn-1\}\rightarrow \{0,\ldots, k-1\}$, is this function constant or balanced, given that one is promised to be the case? This function naturally takes one $k$-qudit register as input. To solve it, you must apply a Fourier transform to this $k$-qudit, like so: (if this goes over your head, don't worry, it's just for illustration)

$$|a\rangle \mapsto \sum_{u=0}^{k-1}e^{i2\pi\frac{au}{k}}|u\rangle$$

If you want to express this in binary, you end up with a gate that does this on numbers $0\ldots k-1$ and acts trivially (does nothing) on all numbers $\geq k$, which is slightly less contrived than doing it this way. Similarly, consider a Bernstein-Vazirani variation where the oracle computes an in-product in some radix $r$. If $r=2$, then we know how to do it. But if $r=5$, the problem is much easier to solve by hand using several $5$-qudit registers. Some problems are easier if you have several different qudit registers, e.g. one $5$-qudit register and one $2$-qudit register.

In summary, yes, you are free to consider other numeric bases, and in the right setting that will make your life easier, for the same reason that thinking about numbers in terms other than their binary expansion helps you with normal computers. I felt compelled to answer because while most answers explained that a qubit has something to do with two base states when measuring but infinite in principle, no answer mentioned that the OPs suggestion of using other bases is legitimate and in fact really happens (for example, in Quantum walks on graphs, Aharonov et al. use a subroutine that takes a qubit and an $n$-qudit as input)

Quantum particles can be in four states. They can spin up, down and be right or left-handed. If you are measuring particles that are entangled, when you measure them they will be in some combination of those four states. If we could some how predict or use a eraser of some kind, it would seem like a good idea to use quarternary rather than binary. As it stands right now, binary is being used but in the future something different will likely take the place of binary. Quantum computers are like classical computers were in the 50s, they are HUGE, expensive and not practical. In fact they are hardly useful at this time. We still struggle with decoherence. The hope it to identify a topological quantum particle that can maintain coherence (is robust) and if that day comes, look out! The revolution with take off like a rocket. To be honest no one can tell you with certainty what Q-computers will be like in the future became when singularity occurs (about 30 years from now) all bets are off. No one can tell you what will happen past that point. Computers could take off in directions we have not even dreamed about.


Why is the object destructor paradigm in garbage collected languages pervasively absent? Looking for insight into decisions around garbage collected language design. Perhaps a language expert could enlighten me? I come from a C++ background, so this area is baffling to me.

It seems nearly all modern garbage collected languages with OOPy object support like Ruby, Javascript/ES6/ES7, Actionscript, Lua, etc. completely omit the destructor/finalize paradigm. Python seems to be the only one with its class __del__() method. Why is this? Are there functional/theoretical limitations within languages with automatic garbage collection which prevent effective implementations of a destructor/finalize method on objects?

I find it extremely lacking that these languages consider memory as the only resource worth managing. What about sockets, file handles, application states? Without the ability to implement custom logic to clean up non-memory resources and states on object finalization, I'm required to litter my application with custom myObject.destroy() style calls, placing the cleanup logic outside my "class", breaking attempted encapsulation, and relegating my application to resource leaks due to human error rather than automatically being handled by the gc.

What are the language design decisions which lead to these languages not having any way to execute custom logic on object disposal? I have to imagine there is a good reason. I'd like to better understand the technical and theoretical decisions that resulted in these languages not having support for object destruction/finalization.

Update:

Perhaps a better way to phrase my question:

Why would a language have the built-in concept of object instances with class or class-like structures along with custom instantiation (constructors), yet completely omit the destruction/finalize functionality? Languages which offer automatic garbage collection seem to be prime candidates to support object destruction/finalization as they know with 100% certainty when an object is no longer in use. Yet most of those languages do not support it.

I don't think it's a case where the destructor may never get called, as that would be a core memory leak, which gcs are designed to avoid. I could see a possible argument being that the destructor/finalizer may not get called until some indeterminate time in the future, but that didn't stop Java or Python from supporting the functionality.

What are the core language design reasons to not support any form of object finalization?

The pattern you're talking about, where objects know how to clean their resources up, falls into three relevant categories.  Let's not conflate destructors with finalizers - only one is related to garbage collection:

The finalizer pattern: cleanup method declared automatically, defined by programmer, called automatically.
Finalizers are called automatically before deallocation by a garbage collector.  The term applies if the garbage collection algorithm employed can determine object life cycles.

The destructor pattern: cleanup method declared automatically, defined by programmer, called automatically only sometimes.
Destructors can be called automatically for stack-allocated objects (because object lifetime is deterministic), but must be explicitly called on all possible execution paths for heap-allocated objects (because object lifetime is nondeterministic).

The disposer pattern: cleanup method declared, defined, and called by programmer.
Programmers make a disposal method and call it themselves - this is where your custom myObject.destroy() method falls.  If disposal is absolutely required, then disposers must be called on all possible execution paths.

Finalizers are the droids you're looking for.
The finalizer pattern (the pattern your question is asking about) is the mechanism for associating objects with system resources (sockets, file descriptors, etc.) for mutual reclamation by a garbage collector. But, finalizers are fundamentally at the mercy of the garbage collection algorithm in use.
Consider this assumption of yours:

Languages which offer automatic garbage collection ... know with 100% certainty when an object is no longer in use.

Technically false (thank you, @babou).  Garbage collection is fundamentally about memory, not objects.  If or when a collection algorithm realizes an object's memory is no longer in use depends on the algorithm and (possibly) how your objects refer to each other.  Let's talk about two types of runtime garbage collectors.  There are lots of ways to alter and augment these to basic techniques:

Tracing GC.  These trace memory, not objects.  Unless augmented to do so, they don't maintain back references to objects from memory.  Unless augmented, these GCs won't know when an object can be finalized, even if they know when its memory is unreachable.  Hence, finalizer calls aren't guaranteed.

Reference Counting GC. These use objects to track memory.  They model object reachability with a directed graph of references.  If there is a cycle in your object reference graph, then all objects in the cycle will never have their finalizer called (until program termination, obviously).  Again, finalizer calls are not guaranteed.

TLDR
Garbage collection is difficult and diverse.  A finalizer call cannot be guaranteed before program termination.

found a ref on this in Dr Dobbs wrt c++ that has more general ideas that argues destructors are problematic in a language where they are implemented. a rough idea here seems to be that a main purpose of destructors is to handle memory deallocation, and that is hard to accomplish correctly. memory is allocated piecewise but different objects get connected and then the deallocation responsibility/ boundaries are not so clear.

so the solution to this of a garbage collector evolved years ago, but garbage collection is not based on objects disappearing from scope at method exits (that is a conceptual idea that is hard to implement), but on a collector running periodically, somewhat nondeterministically, when the app experiences "memory pressure" (ie running out of memory).

in other words the mere human concept of an "newly unused object" is actually in some ways a misleading abstraction in the sense that no object can "instantaneously" become unused. unused objects can only be "discovered" by running a garbage collection algorithm that traverses the object reference graph and the best performing algorithms run intermittently.

it is possible a better garbage collection algorithm lies waiting to be discovered that can near-instantaneously identify unused objects, which could then lead to consistent destructor calling code, but one has not been found after many years of research in the area.

the solution to resource management areas such as files or connections seems to be to have object "managers" that attempt to handle their use.

Destructors considered harmful / Koenig, Dr Dobbs


Exponential example for simplex used in SMT solvers The original simplex algorithm requires an exponential number of pivot operations in the worst case, e.g., if run on the Klee-Minty example [3,4].

What about the simplex algorithm used in SMT solvers [1,2]? Could you provide an example where it requires exponential time?

The algorithm I have in mind is by Bruno Dutertre and Leonardo de Moura in [1,2], and is presumably used in all modern SMT solvers. The algorithm introduces one slack variable per constraint, the slack variables have lower and upper bounds; and the problem is that of feasibility instead of optimization.

I tried to modify the Klee-Minty example [3,4], but failed so far.
Kroening & Strichman contains this question as an exercise, so you can also hint instead of answering.

Integrating Simplex with DPLL(T) by Bruno Dutertre and Leonardo de Moura:
Decision Procedures: an Algorithmic Point of View by Daniel Kroening and Ofer Strichman
Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method
Picture of the Klee-Minty cube:

Here, you can find hard examples for DPLL.
http://www.ioc.ee/~tarmo/tday-torve/itsykson-slides.pdf

For instance, it can be very slow for Tseitin formulas and for some unsatisfaisable formulas (it will try many solutions).

I hope it will give you some hints :)


Substring in a infinite sequence of numbers I have an infinite sequence of numbers, starting from 1 and need to find position of begin of some given substring of numbers.

Example:

1234567891011121314151617181920 ...

S = 141

Result: 18

All i think about is convert sequence to string and find substring using Rabin-Karp or KMP. But i feel that i can use it as numbers and there is some O(1) solution using math.

Another thought is split S on pieces:

141 = [(1, 4, 1), (1, 41), (14, 1), (141)]

And i have (1-9)(10-99)(100-999)(1000-9999)... which represents infinite sequence.

Than i can use this algo:

For (1, 41): try to find 1 from (1-9) and what goes next, if 41 is not next number, than try next tuple.

For (14, 1): try to find 14 from (10-99) and and what goes next, if 1 than find position of '14'.

But i'm not sure that this is correct solution.
Maybe some advices?

Your algorithm is not correct. Consider 21:

21 = [(2, 1), (21)]

First we find 2 in (1-9): 123456789. However, a 3 follows, so it's not a solution.

Then we try to find 21 in (10-99). This finds a solution, but it's 21. However there is an earlier solution:

123456789101112131415161718192021

So the solution is not correct.

The sequence you're after is A229186, but no simple formula is posted there.

Consider the number you want to search

eg 141 , see the digit in number lesser than or equal to the first digit

[ Intuition: If less maybe , we can bring it to the front, If equal maybe the rest is the next number in the series]

Following this:

See 141 , 1 in the third place is equal to the first digit.

So here we go position of 14 (with a check that 15 comes after 14, Maybe its like (191, where 19+1 = 20 in which case we are wrong )

Another example

21 , 1 is lesser than 2 , so 12 13  and we are done.

Another one 1254

Since no number is greater than or equal to 1 , answer is 1254

Another one 5421

1 is the least so 1542 1543

Another one 191

1 is least so, 19+1 = 20 (No!!) So answer is 191.

1911

Here we see we can solve by , 19 11 , take to front 11 19 11 20.

Or let the last one stay (tie as 1), so 191 192. So the answer is 191

In this case your algorithm will be max O(size of pattern) , instead of O(size of text) as in kmp, assuming you can calculate index in O(1) by a formula.

Code this up and you are done :)


Problem with Understanding a Recursion Tree Consider the recursion tree:

$T(p) = 3T(\frac{2p}{8}) + 2T(\frac{p}{8}) + O(p)$.

I determined that there are at most $1 + log_{4}\ p$ levels, because the longest simple path from root to leaf is $p \rightarrow \frac{2p}{8} \rightarrow \frac{4p}{16} \rightarrow \frac{8p}{32} \rightarrow\ ...$.

This means that the time complexity is $O(p\ log\ p)$.

Now, I stopped all my leaves in the above recursion tree have $T(1)$, but say I have the condition $T(0) + O(1)$. Does this change my solution somehow?

Think of it this way, you have a mathematically formal description of a recursive function. Which every function maps an element (or more than one element) To 1 element in the codomain.

What would T(0) be in terms of this functions as an input? It wouldn't change the time complexity.


3-SAT problem with number of clauses equal to number of variables Consider the 3-SAT problem where the formula is in conjunctive normal form and we restrict the Boolean formulas such that the number of clauses in the formula is equal to the number of variables. Is this problem still NP-hard?

For example, this formula has $3$ variables and has $3$ clauses $(\lnot x_1 \vee \lnot x_2 \vee \lnot x_3 ) \wedge (\lnot x_1 \vee \lnot x_3) \wedge (\lnot x_2 \vee \lnot x_3)$,

and the following formula has three variables but has only two clauses $(\lnot x_1 \vee \lnot x_2 \vee \lnot x_3  ) \wedge (\lnot x_2 \vee \lnot x_3)$.

Let the variant of the 3-SAT problem you describe be called EQUAL-3-SAT, where (following your definition) each clause has at most 3 literals. We prove EQUAL-3-SAT is NP-complete by a reduction from 3-SAT as follows.

Let $\phi$ be an instance of 3-SAT with $n$ variables and $m$ clauses. If $\phi$ is balanced already in the beginning (the case $n=m$), we do nothing. If $n > m$, we introduce a fresh variable $x$ that does not appear anywhere in $\phi$ and add to $\phi$ exactly $n-m+1$ clauses of the form $(x)$, so we have $n=m$, and we are done.

Then, if $n < m$, we can do similar balancing: each addition of a 3-literal clause $(a \vee b \vee c)$, where $a$, $b$ and $c$ are fresh variables, increases $n$ by $3$, and $m$ by $1$. Keep adding this clause to $\phi$ until $n=m$, or the difference between $n$ and $m$ is exactly one or three (if the difference was two, repeating the process once more would balance $\phi$). If the difference is one, adding one more 3-literal clause causes $n=m+1$ thus we use the balancing process of the first step (case $n > m$). If the difference is three, we simply add an 2-clause of the form $(a \vee b)$, increasing $n$ by two and $m$ by one, again giving us $n=m$.

Finally, we observe the new formula is satisfiable if and only if $\phi$ was.

If number of clauses is equal to number of variables this problem is in P.


Decidability of empty intersection of two languages accepted by Turing machines I am really struggling with determining the decidability of languages and cant figure out whether this problem is decidable or not.

I have a language

$\qquad\displaystyle
  L = \{ (R(M_1), R(M_2)) \mid L(M_1) \cap L(M_2) = \emptyset \}$,

where $R(M_1)$ and $R(M_2)$ are representations of Turing machines $M_1$, resp $M_2$ and $L(M_1)$, $L(M_2)$ are the languages accepted by these machines.

Is language $L$ a decidable language?

I have found this theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection. (but I dont know whether $L(M_1)$ and $L(M_2)$ are context-free, I only know that they are accepted by some machines, so I dont know if I can use this theorem).

I think that this problem is undecidable and my attempt to prove this would go like this:

In order for this language to be decidable. I would have to build a Turing machine that tests whether an arbitrary word is accepted by $M_1$ and not $M_2$ (and vice versa) but I cannot guarantee that it will halt for all inputs (since language acceptence does not guarantee that the language is decidable) so it proves the undecidability.

Is this correct approach?

Is $L$ at least recursively enumarable?

It is undecidable whether a Turing machine accepts any input at all (reduction from the halting problem). So, take a machine $M_1$ that accepts all inputs. $L(M_1)\cap L(M_2) = L(M_2)$ so non-emptiness is undecidable.

The intersection of two RE sets is RE. This is a standard fact: simulate the accepting machines in parallel and accept iff they both accept.

We can reduce this problem to the decision of an empty language by a turing machine (Etm), as previous posted. In this case I think that the problem can be more easily solved if we use the Etm Decider as a post-processing.

First, we know that L(M1) $\cap$ L(M2) = L(M1) if L(M1) $\subseteq$ L(M2). So we construct a decider that tests if L(M1) $\cap$ L(M2) = L(M1). If the answer is no, we reject. If it is yes, we test if L(M1) $\neq$ $\emptyset$. If yes, we accept. If no, we reject.

It is a contradicition, since Etm is undecidable.

Is this approach correct to this problem?


Proof Complexity of a Proof or Disproof of P = NP Has there been any research on the proof complexity of a resolution to the P=NP problem?  If not, given the lack of progress on the problem, would it be unreasonable to conjecture that any proof that resolves the P=NP problem will require a super-polynomial number of steps?

Proof complexity only makes sense when there is a sequence of statements depending on a parameter $n$. For example, the proposition $\mathsf{PHP}_n$ states (informally) that there is no bijection $[n+1] \to [n]$. This sequence of propositions is hard for certain propositional proof systems.

The statement $\mathsf{P} \neq \mathsf{NP}$ is a single statement, so you can't apply proof complexity to it directly. However, the following sequence of statements does make sense, for particular functions $s(n)$: "there is no circuit of size $s(n)$ correctly solving SAT for instances of length $n$". This has been considered in the literature, for example by Razborov (who considered the setting of uniform proof complexity, i.e., bounded arithmetic).

If P = NP then all you need to do is to create a polynomial time algorithm for solving some NP-complete problem, and prove that it is indeed polynomial (which might be hard, for example the Simplex algorithm usually runs very fast but proving that it runs fast seems incredibly difficult).

Ok, this might be very difficult. Assume we find an algorithm that supposedly solves the Traveling Salesman problem in O ($n^{100}$). Tough. We can't even measure the execution time for a problem with two cities.


Constant folding vs. Constant propogation What is the difference between constant folding and constant propogation? They both seem to do the same thing, instead of saving constants into stack or evaluating a full arithmetic expression, they simply replace it with the result which can be obtained at compile time. What is the difference between two?

Based on these two websites: http://www.compileroptimizations.com/category/constant_folding.htm and
http://www.compileroptimizations.com/category/constant_propagation.htm

The difference is that constant propogation is not saving a variable to the stack, because we know its a constant (like x = 10;) and can simply plug it in everywhere (say if you had an expression y = x + x + x => y = 10 + 10 + 10) it is used in machine code. Whereas, constant folding is simply evaluating expressions that use constants and substituting the result into the machine code (like y = 10 + 10 + 10; => y = 30;)

In constant folding you only submit the result.
For example, in constant folding you turn y=3+4 into y=7.

In contrast, in constant propagation, the constant replaces a variable.
For example, given

int x=6;
for(i=0;i<x;i++)

you simple replace the value of x by the constant:

for(i=0;i<6;i++)


Using the Chomsky-Schutzenberger theorem to prove a language is not context-free? The Chomsky-Schutzenberger representation theorem states that a language $L$ is context-free iff there is a homomorphism $h$, a regular language $R$, and a paired alphabet $\Sigma = T \cup \overline{T}$ such that $L = h(D_\Sigma \cap R)$, where $D_\Sigma$ is the Dyck language over $\Sigma$. This is a necessary and sufficient condition for a language to be context-free, so in principle it seems like it should be possible to show that a language is not context-free by showing that there are no valid choices for $h$, $\Sigma$, and $R$ satisfying the theorem.

This earlier question talks about approaches for showing that a language is not context-free, but doesn't mention this approach. Additionally, I can't seem to find any constructive examples of proofs of non-context-freeness along these lines.

Are there any known examples of languages that have been shown not to be context-free by means of the Chomsky-Schutzenberger theorem?

here is a construction not exactly as requested but related/ somewhat similar. the contrapositive of the Chomsky-Schutzenberger theorem can be used to prove a language is not unambiguously CFL. it describes the close connection of the construction to generating functions that yields key insight into the problem.

see ORDINARY GENERATING FUNCTIONS OF CONTEXT-FREE
GRAMMARS / TANNER SWETT, EDWARD ABOUFADEL, sec 2.6 p 6


Compute a max-flow from a min-cut We know that computing a maximum flow resp. a minimum cut of a network with capacities
is equivalent; cf. the max-flow min-cut theorem.

We have (more or less efficient) algorithms for computing maximum flows, and computing a minimum cut given a maximum flow is neither hard nor expensive, either.

But what about the reverse? Given a minimum cut, how can we determine a maximum flow?
Without solving Max-Flow from scratch, of course, and preferably faster than that, too.

Some thoughts:

From the minimum cut, we know the maximum flow value. I don't see how this information helps the standard approaches augmenting-path and push-relabel, although adapting the latter seems slightly more plausible.
We can not use the minimum cut to split the network in two parts and recurse since that won't shrink the problem in the worst case (if one partition is a singleton); also we would not have a minimum cut of the smaller instances.
Does knowing the value of the maximum flow speed up solving the Max-Flow LP, maybe via the complementary slackness conditions?

In the worst case, the minimum cut itself doesn't convey much information about the maximum flow. Consider a graph $G=(V,E)$ in which the minimum $s,t$-cut has value $w$. If I extend $G$ by adding a new vertex $s'$ and an edge $(s',s)$ with weight $w$, a minimum $s',t$-cut in the new graph consists of just the edge $(s', s)$ but that doesn't give any information about how to get $w$ units of flow from $s$ to $t$.

Effectively, the minimum cut tells you the value of the flow, but not how to achieve that flow. This means that knowing the minimum cut can speed up finding the flow by at most a logarithmic factor, since we could do binary search to find the value of the cut.

There certainly exist algorithms that let you compute the min cut before computing the maxflow. Two such algorithms are the push relabel and the pseudoflow algorithms which are closely related. The latter is more efficient. Both of these algorithms use special properties of the residual graph they iteratively improve to derive the maxflow from the min cut. For details I highly recommend reading the code and papers.

To elaborate on the push relabel case, when the algorithm can push no more flow to the sink it is guaranteed to have computed a min cut. This part of the algorithm is called phase 1 for lack of a better name. Phase 2 is the more efficient stage where it transforms the min cut into a maxflow by iteratively cancelling cycles in the residual graph using a single depth first search and pushing excess back to the source. I believe phase 2 can be proven to be asymptomatically more efficient than phase 1.


Can there be a perfect chess algorithm? Current chess algorithms go about 1 or maybe 2 levels down a tree of possible paths depending on the player's move's and the opponent's moves. Let's say that we have the computing power to develop an algorithm that predicts all possible movements of the opponent in a chess game. An algorithm that has all the possible paths that opponent can take at any given moment depending on the players moves. Can there ever be a perfect chess algorithm that will never lose? Or maybe an algorithm that will always win?
I mean in theory someone who can predict all the possible moves must be able to find a way to defeat each and every one of them or simply choose a different path if a certain one will effeminately lead him to defeat.....

edit--
What my question really is. Let's say we have the computing power for a perfect algorithm that can play optimally. What happens when the opponent plays with the same optimal algorithm? That also will apply in all 2 player games with finite number (very large or not) of moves. Can there ever be an optimal algorithm that always wins?

Personal definition: An optimal algorithm is a perfect algorithm that always wins... (not one that never loses, but one that always wins

First of all, I believe that chess algorithms look more than 2 plies down, although they don't consider all different possibilities; pruning the search tree is very important to avoid the combinatorial explosion in the number of possible moves.

For a game like chess, there are three possibilities as to the identity of the winner: either player 1 has a winning strategy, or player 2 has a winning strategy, or both players draw under optimal play. It is not known which is the case for the game of chess. However, since chess is a finite game, there is a computer algorithm, consisting of a very large table, which plays chess optimally.

Of course, such an algorithm wouldn't be practical. But for some simpler games, the "value" of the game (which player wins, if any) has been determined, and an optimal algorithm has been devised. Such a game is known as a solved game.

The mathematical subject that deals with (what are known as) combinatorial games is combinatorial game theory. Mathematicians have developed a recursive method to determine the value of a game given the graph of the game, which includes all the allowed positions and moves. You should be able to find a description of this algorithm in the Wikipedia entry or any lecture notes on the subject.

will add another answer that emphasizes the massive state space, not really conceptualized in the question or pointed out in other answers. must disagree with your premise:

  Let's say that we have the computing power to develop an algorithm that predicts all possible movements of the opponent in a chess game.

see info on shannons 1950 paper, "Programming a Computer for Playing Chess" which introduced the field of computer based chess playing/algorithms and which its analysis is basically unchanged & still sound (even by the subsequent computer revolution and Moores law). it estimates the number of moves. its absolutely astronomical. in the range of "never within conceivable hardware even with revolutionary unforeseen advances".

its a documented psychological fact [3], probably one of the many psychological biases [2], that humans have trouble understanding numbers of this magnitude. see also counterfactual thinking.[4] while supercomputers compute massive problems, its uncontroversially not within the range of any supercomputer that is currently built or could ever be built. (and many chess aficionados would argue this "combinatorial explosion" in move/position possibilities is an intrinsic aspect of the games "flavor" that seems to be intentionally designed into the millenia-old game).

therefore chess is fundamentally different than some games which have smaller "solvable" state spaces [of which there is some study in computer science & game theory etc] and in some key ways cannot be evaluated within that framework.

  Allis also estimated the game-tree complexity to be at least $10^{123}$, "based on an average branching factor of 35 and an average game length of 80". As a comparison, the number of atoms in the observable universe, to which it is often compared, is estimated to be between $4×10^{79}$ and $10^{81}$.

now, that said, it is conceivable (but unlikely) that there may be theoretical insights into the game that could be used to prune the search space substantially. that has happened since 1950 but not really in any fundamentally breakthrough ways.

see also

[1] what is the computational complexity of solving chess, tcs.se

[2] human biases in judgement and decision making

[3] Psychology students publish research on conceptualizing numbers

[4] counterfactual thinking


How to develop an $O(N)$ algorithm solve the 2-sum problem? Given an sorted array of integers, I want to find the number of pairs that sum to $0$. For example, given $\{-3,-2,0,2,3,4\}$, the number of pairs sum to zero is $2$.

Let $N$ be the number of elements in the input array. If I use binary search to find the additive inverse for an element in the array, the order is $O(\log N)$. If I traverse all the elements in the set, then the order is $O(N\log N)$.

  How to find an algorithm which is of order $O(N)$?

Let $A$ be the sorted input array. Keep two pointers $l$ and $r$ that go through the elements in $A$. The pointer $l$ will go through the "left part" of $A$, that is the negative integers. The pointer $r$ does the same for the "right part", the positive integers. Below, I will outline a pseudocode solution and assume that $0 \notin A$ for minor simplicity. Omitted are also the checks for the cases where there are only positive or only negative integers in $A$.

COUNT-PAIRS(A[1..N]):
 l = index of the last negative integer in A
 r = index of the first positive integer in A
 count = 0;

 while(l >= 0 and r <= N)
   if(A[l] + A[r] == 0)
     ++count; ++right; --left; continue;

   if(A[r] > -1 * A[l])
     --left;
   else
     ++right;

It is obvious the algorithm takes $O(N)$ time.

The simplest approach, by my understanding, seems to be to use a Hash-Table, H = {a[0] = true, .. , a[n-1] = true}. This Hash-Table can be built in O(n) time. Once the Hash-Table is built, iterate through A[0,..,n-1] and check if H[-1*a[i]] exists. If it does, increment a counter by 1, and return the final result. This is clearly O(n).


How solve this recurrence: T(n) = 2t(n-1) - t(n-2) +5n +7 I am trying to solve the recurrence: T(n) = 2t(n-1) - t(n-2) +5n +7 but without success.

And from here I don't know how to continue?

According to your recurrence equation  2t(n-1) futher breakdown like 2[2t((n-1)-1)+t((n-1)-2)+5(n-1)+7] and for solution of this equation explore
recurrence equation solution


Why is it O(1) (and not, say, O(2))? If the running time of an algorithm scales linearly with the size of its input, we say it has $O(N)$ complexity, where we understand N to represent input size.

If the running time does not vary with input size, we say it's $O(1)$, which is essentially saying it varies proportionally to 1; i.e., doesn't vary at all (because 1 is constant).

Of course, 1 is not the only constant. Any number could have been used there, right? (Incidentally, I think this is related to the common mistake many CS students make, thinking "$O(2N)$" is any different from $O(N)$.)

It seems to me that 1 was a sensible choice. Still, I'm curious if there is more to the etymology there—why not $O(0)$, for example, or $O(C)$ where $C$ stands for "constant"? Is there a story there, or was it just an arbitrary choice that has never really been questioned?

"$O(1)$" is used because it is simple, clear and unambiguous. "$O(C)$" would be a poor choice of notation because in any given context, $C$ might have a specific meaning, such as the number of clauses in a CNF formula, the number of components in a graph.

You can write $O(k)$ as well, what it conveys is the fact that the asymptotic runtime is independent of the size of the input $n$, and is bound by some constant times $k$.

The Landau notation puts great emphasis on the ease of analysis. Suppose you have to compute $O(1) + O(13) + O(123)$. That can become quite messy, so instead you say $O(1)+O(1)+O(1) \in O(1)$. Again, the intuition here is there is a constant that put a bound on their sum, and is independent of the size of the input.


How to prove every context-free language over a unary alphabet is regular? How can I show that every context-free language over a unary alphabet is regular?

The following proof follows Pighizzini, Shallit and Wang, Unary Context-Free Grammars and Pushdown
Automata, Descriptional Complexity and Auxiliary
Space Lower Bounds.

Let $L$ be a unary context-free language. Assume for simplicity that $\epsilon \notin L$, and consider a grammar $G = \langle V,\{a\},P,S \rangle$ for $L$ in Chomsky normal form. Denote $h = |V|$.

In the sequel, whenever we say parse tree, we mean parse tree in $G$.

Let $\Pi$ be the collection of all triples $(U,i,j)$ such that $U$ is a parse tree rooted at some nonterminal $A$ which represents a derivation of the sentential form $a^i A a^j$, where $0 < i+j < 2^h$.

Let $(U,i,j) \in \Pi$, and let $A$ be the label of the root of $U$. Given a parse tree $S$ containing a node $v$ labeled $A$, we can "pump" $S$ by $U$ by replacing $v$ with a copy of $U$, attaching the children of $v$ to the leaf of $U$ labeled $A$.

Lemma. If $\ell > 2^{h-1}$ and $a^\ell \in L$ and $T$ is a parse tree for $a^\ell$, then there exists a triple $(U,i,j) \in \Pi$ and a parse tree $S$ for $a^{\ell-i-j}$ such that $T$ is obtained from $S$ by pumping by $U$.

Proof. Since $\ell > 2^{h-1}$, $T$ must have depth at least $h+1$ (recall that the last level corresponds to productions of the form $A \to a$), and so a path of length $h+1$ edges. This path contains $h+1$ nonterminals, one of which must repeat. Consider such a repetition within the last $h+1$ nonterminals of the path. The repetition corresponds to a triple $(U,i,j) \in \Pi$ (note $i+j < 2^h$ since we chose a repetition within the last $h+1$ nonterminals, and $i+j > 0$ since the grammar is in Chomsky normal form). By "pumping out" this derivation, we obtain the parse tree $S$ for $a^{\ell-i-j}$. $\quad\square$

Corollary. Every parse tree in $L$ can be obtained in the following way:

Start with a parse tree for some $a^\ell$, where $\ell \leq 2^{h-1}$.
Repeatedly pump by $U$ for some $(U,i,j) \in \Pi$.

Using this, we can construct an NFA for $L$:

Guess a parse tree for some $a^\ell$, where $\ell \leq 2^{h-1}$, and read the word $a^\ell$.
Set $X$ to be the set of nonterminals appearing in the parse tree.
Perform the following operation an arbitrary number of times:

Guess $(U,i,j) \in \Pi$ such that the label of the root of $U$ appears in $X$.
Read $a^{i+j}$.
Add all nonterminals in $U$ to $X$.

This shows that $L$ is regular.

Parikh's theorem can be proved in the same way.

This was my first attempt at it:

First let $L$ be our context free language. Using the pumping lemma for context free grammars: the pumping constant is $p$ and $m \ge p$.

We have a string $s = 1^m = uvwxy$, and we say $a_m = |uwy|$ and $b_m = |vx|$ such that $s = 1^{a_m}1^{b_m}$ where $1 \le b_m \le p$

Because our language was context free, we can say this about a string. Now let us define two more languages:

$$Mod = \{m \in \mathbb{N} | 1^m \in L\}$$

$$ L' = \{x \in L| |x| < p\}$$

Now we can construct out language $L$ from of finite union of regular languages, meaning it is regular:

$$ L = L' \cup \bigcup_{m \in Mod} 1^{a_m}1^{b_m} = L' \cup \bigcup_{m \in Mod} 1^{a_m}(1^{b_m})^* $$


Longest subsequence such that A[i].x < A[i+1].y I have an issue for which I am looking for an algorithm (if it exists)

What I have:
An array of items which have certain properties, e.g. item $A$ has properties $x$ and $y$.

Example: $[ A(x,y), B(x,y), C(x,y), D(x,y), E(x,y) ]$

What I want:
A result list consisting of elements of the original list, such as $[ A(x,y), C(x,y), E(x,y) ]$, for which the following properties are true:

No reordering of elements, they are in the same order as the original list
The result has the maximum number of elements, i.e. the longest 'path' possible
For each pair of consecutive items $(A(x,y), B(x,y))$ in the result, $A.x \lt B.y$. In other words, an item's $x$ must be less than the next item's $y$.

Complexity: The list in the case I have is about 35 items long, so an algorithm which is $O(n!)$ might not work.

Does such an algorithm exist?

It's easier to change notation.  Suppose the array is $A$, with the $i$-th element denoted $A[i]$ for $i=1,2,\dots,n$, and that element $i$ has attributes $A[i].x$ and $A[i].y$.  Associate a directed graph $G$ with the array as follows.  The vertices of $G$ are the indices $1\dots n$ of the array.  Vertex $i$ is connected to vertex $j\ $ if both conditions $i<j$ and $A[i].x < A[j].y\ $ hold.

You are then asking for a longest directed path in $G$.

Note that $G$ is actually acyclic, since the arcs form a subset of the usual order on the set $\{1,\dots,n\}$.
Any standard linear algorithm can then be used to compute the longest path, such as a topological sort.

So, your comparison is based on numerical properties x and y? If this is the case, then do some kind of sorting algorithm first, and adjust the order after sorting so that your condition of no reordering holds (that is delete those elements that are not at the correct location).


"NP-complete" optimization problems I am slightly confused by some terminology I have encountered regarding the complexity of optimization problems.  In an algorithms class, I had the large parsimony problem described as NP-complete.  However, I am not exactly sure what the term NP-complete means in the context of an optimization problem.  Does this just mean that the corresponding decision problem is NP-complete?  And does that mean that the optimization problem may in fact be harder (perhaps outside of NP)?

In particular, I am concerned about the fact that while an NP-complete decision problem is polynomial time verifiable, a solution to a corresponding optimization problem does not appear to be polynomial time verifiable.  Does that mean that the problem is not really in NP, or is polynomial time verifiability only a characteristic of NP decision problems?

An attempt on a partial answer:

Decision problems were already investigated for some time before optimization problems came into view, in the sense as they are treated from the approximation algorithms perspective.

You have to be careful when carrying over the concepts from decision problems. It can be done and a precise notion of NP-completeness for optimization problems can be given. Look at this answer. It is of course different from the NP-completeness for decision problems, but it is based on the sames ideas (reductions).

If you are faced with an optimization problem that doesn’t allow a verification with a feasible solution, then there is not much you can do. That is why one usually assumes that:

We can verify efficiently if the input is actually a valid instance of our optimization problem.
The size of the feasible solutions is bounded polynomially by the size of the inputs.
We can verify efficiently if a solution is a feasible solution of the input.
The value of a solution can be determined efficiently.

Otherwise, there is not much we can hope to achieve.

The complexity class $\mathrm{NP}$ only contains decisions problems per definition. So there aren’t any optimizations problems in it. And the Verifier-based definition of  $\mathrm{NP}$ you mention is specific to $\mathrm{NP}$. I haven’t encountered it with optimization problems.

If you want to verify that a solution is not just feasible, but also optimal, I would say that this is as hard as solving the original optimization problem because, in order to refute a given feasible and possibly optimal solution as non-optimal, you have to give a better solution, which might require you to find the true optimal solution.

But that doesn’t mean that the optimization problem is harder. See this answer, which depends of course on the precise definitions.

The reason most optimization problems can be classed as P, NP, NP-complete, etc., is the Kuhn-Tucker conditions.  I'll talk in terms of linear-programming problems, but the KTC apply in many other optimization problems.  For each optimization problem there is a dual.  If the goal in the original problem is to maximize some function, then the dual (usually) has a function to be minimized.*  Feasible, but non-optimal solutions to the original problem will be infeasible/invalid for the dual problem, and vice-versa.  If, and only if, a solution is feasible for the primary and dual, it is an optimal solution for both.  (Technically, may be one of a large number of optimal solutions which give the same result.)

So finding an optimal solution of an optimization problem is equivalent to finding a valid solution for the primary and dual.  You may use optimization algorithms to find that solution, but the overall process is an existence proof.

If you want to flip from minimization to maximization, multiply the objective function by -1.


Algorithm to find out the number of times a number occurs consecutively in an array in a range specified I have an array say

8 3 5 4 4 4 4 4 3 2 7 11 12 7 7 7 7 1 2

total =17 elements
now you are given a range say [2,11] both included ,now you have o find out the element that has occurred the max number of times and the number of times it has occurred

A simple traversing through the array in the range  and keeping the track of the each element is one solution but time complexity is O(N) and if we are given N queries time complexity = O(N^2). Any faster algo than this ?

Define a sub problem solution as the range of longest sub series.
If there are more than one we solution is 2 at most. The once at the tips of the range.
and there are exactly (n^2-n)/2 sub problems here.
You can solve each sub problem in o(n).

If you were to remember the results of problems you solved.
You can remember all in o(n*(n^2-n)/2) and it's fine.

But, If you consider Dynamic programming.
There is a bottom up series to solve each sub problem in o(1) time.

when trying to solve(i,j) two cases are to consider:

the range is at the tip. so consider increasing the result.
the range is at the tip. just return the longest. again up to 2 ranges.


What are GPUs bad at? I understand that GPUs are generally used to do LOTS of calculations in parallel. I understand why we would want to parallelize processes in order to speed things up. However, GPUs aren't always better than CPUs, as far as  I know.

What kinds of tasks are GPUs bad at? When would we prefer CPU over GPU for processing?

GPUs are bad at doing one thing at a time.  A modern high-end GPU may have several thousand cores, but these are organized into SIMD blocks of 16 or 32.  If you want to compute 2+2, you might have 32 cores each compute an addition operation, and then discard 31 of the results.

GPUs are bad at doing individual things fast.  GPUs only recently topped the one-gigahertz mark, something that CPUs did more than twenty years ago.  If your task involves doing many things to one piece of data, rather than one thing to many pieces of data, a CPU is far better.

GPUs are bad at dealing with data non-locality.  The hardware is optimized for working on contiguous blocks of data.  If your task involves picking up individual pieces of data scattered around your data set, the GPU's incredible memory bandwidth is mostly wasted.

GPU are 1) highly parallel architectures, with additional limitation that 2) are organized in blocks which must perform same operation on different data at the same time.

Therefore, the performance of GPUs is due to extensive and quite constrained paralelism, but their clock rates are not particularly high. So, whenever you have an algorithm where the next step depends on the current step then very little actual(!) parallelism is possible.

Examples of such algorithms: iterative algorithms, many optimization methods.

Side note: you may do speculative calculation in iterative algorithms as well if you have discrete solution space (e.g. if previous step has 16 possible outcomes, you can precalculate the next step in parallel). But this are mostly special cases.

Side note 2: Same limitations apply to FPGAs. Just that clock rates are even lower (e.g. hundreds of Mhz, not Ghz), and penalty for not having parallelism even higher.


How to get a base-3 representation of an integer using a stack? Assuming that a stack data structure is available, how can this data structure be used to compute a representation of an integer in base three? For example, the algorithm for printBase3 would return 12020 on input 141.

ok I think I found the solution to my question

So if n = 141, 12020 would be printed to the screen.

Solution:

          public static void printBase3(int n){
           if (n/3 == 0)
           System.out.print(n);
          else{
          printBase3(n/3);
          System.out.print(n%3);
          }
        }


Theory of computation introductory curriculum I want to study theory of computation on my own, so I am looking for books.

What set of books would you recommend for the equivalent of a one-semester course that introduces theory of computation?

Please post answers that describe a complete curriculum, explaining which chapters of each book are relevant at which stage of the course or self-study.

Introduction to the Theory of Computation by Michael Sipser is a relatively recent entry into this field. It was the required book for a class my friend was taking, and I asked him for the PDF so I could browse through at my leisure. I ended up reading almost the whole book, even the chapters on topics I was already very familiar with, just because the book is such a joy to read. It's written at an introductory level, which means less notation, more exposition, and more intuition. The motivation behind every idea and theorem is crystal clear. He precedes every proof with a "proof idea" section that lays out the path the proof is going to take without getting into the gory details. The book covers Automata Theory, Computability Theory, and Complexity Theory to a satisfactory depth for an undergraduate level. I've read many textbooks in computer science and math, and this is probably my favorite.

There are probably no worthy books.  Danny Hillis`s book comes to mind, but much theory can be introduced with very little text.  Binary arthimetic (with a little philosophy of number) and minimal Turing Machines, what?

It's understanding that takes time to grok how simple it is -- that's the job of the teacher, not a textbook (at least if you want to accomplish it in one semester).  Only real-time, in the classroom, can you get a read on how to proceed with such a task.


Master theorem with $T(n) = 6T(n/10) + \lg^2 n$ So I think this falls under case 1...but I am not sure how to formally prove that $n^{lg_{10} 6}$ is asymptotically greater than $\lg^2 n$. I tried using L'hopitals but kinda reached a dead end. Here's what i have so far

$$\lim_{n \rightarrow \infty} \frac{d(\lg^2 n)}{d(n^{\lg_{10}6})} = \frac{2 \lg n (\frac{1}{n})}{(\lg_{10}6) n ^{(\lg_{10}6) - 1}}$$

Is there some better way I can think about proving case 1?

Yuval Filmus pretty much showed the way in the comment above. I will just elaborate on his approach.

First, we raise both to the power lg610.

(nlg106)lg610 = n(lg106 x lg610) = n

and,

(lg2n)lg610 = (lg n)2 x lg610 = (lg n)2.57

Now, taking log of both of these, we get
lg(n) and 2.57xlg(lg(n)) respectively.

lg(n) is asymptotically greater than lg(lg(n)), and thus, our case is proved.


Does there exist a priority queue with $O(1)$ extracts? There are a great many data structures that implement the priority-queue interface:

Insert: insert an element into the structure
Get-Min: return the smallest element in the structure
Extract-Min: remove the smallest element in the structure

Common data structures implementing this interface are (min)heaps.

Usually, the (amortized) running times of these operations are:

Insert: $\mathcal{O}(1)$ (sometimes $\mathcal{O}(\log n)$)
Get-Min: $\mathcal{O}(1)$
Extract-Min: $\mathcal{O}(\log n)$

The Fibonacci heap achieves these running times for example. Now, my question is the following:

  Is there a data structure with the following (amortized) running times?

Insert: $\mathcal{O}(\log n)$
Get-Min: $\mathcal{O}(1)$
Extract-Min: $\mathcal{O}(1)$

If we can construct such a structure in $\mathcal{O}(n)$ time given sorted input, then we can for instance find line intersections on pre-sorted inputs with $o\left(\frac{n}{\log n}\right)$ intersections strictly faster than if we use the 'usual' priority queues.

Our idea is to use threaded splay trees. Other than the Wikipedia article we will thread the trees so that every node has a pointer next to its successor in the in-order traversal; we also hold a pointer start to the smallest element in the tree.

It is easy to see that extracting the smallest element is possible in (worst case) time $\mathcal{O}(1)$: just follow the start pointer, remove the minimum and change the pointer to the minimum's next. The minimum can never have a left child; if it has a right child, we put it in the minimum's place in the tree. We do not perform the splay operation splay trees usually would do.
The result is a search tree that is still reasonably balanced: because we only remove nodes on the left flank, we know that when the number of nodes (in an affected subtree) drops to about half the original number because of deletions, the (sub)tree's height is reduced by one.

Insertions are possible in $\mathcal{O}(\log n)$ amortised time; the zig-zag (and what not) operations will here also rebalance the tree nicely.

This is a rough sketch at best. Credits go to F. Weinberg who puzzled over the question with me and our advisor M. Nebel who mentioned splay trees, about the only tree variant we had not tried.

Find-min in $O(1)$ with expected update time of $O(\sqrt{log\text{ }log\text{ }n})$

See the 2007 paper: Equivalence between priority queues and sorting by Mikkel Thorup.

Note: He refers to the 2002 article by Han & Thorup: Integer Sorting in $O(n\text{ }\sqrt{log\text{ }log\text{ }n})$ Expected Time and Linear Space.


Alternative algorithms for calculating x^2? I'm emulating 128-bit arithmetic. At the moment I'm calculating $x^2$ by computing $x\cdot x$. What might be some alternative methods that aren't simply dressing up multiplication?

Base on the fact that:

If n is an even number $(n = 2m) \implies n^2 = 4m^2$

If n is an odd number $(n = 2m + 1) \implies n^2 = 4m^2 + 4m + 1$

And you can calculate $m$ by bitwise shifting right of $n$, calculate $4m$ (or $4m^2$) by bitwise shifting left.

So you can apply the recursion method to this process to establish the result with $O(\log n)$ time complexity.

You can simply use pow(x,2) this comes under the library #include<math.h>


How is the complexity/size of a problem (for instance SAT) determined? We say an algorithm runs in polynomial time if it is of the form $O(n^k)$ where $n$ is the size of the input, right?

So how do we judge how many inputs there are in: $(x_1 \vee x_2 \vee \overline{x_3}) \wedge (\overline{x_1} \vee \overline{x_2} \vee x_4) \wedge (x_2\vee x_3\vee x_5)$

...actually, in looking for an actual definition of an algorithm running in polynomial time, wolframAlpha says:
"An algorithm is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is $O(n^k)$ for some non-negative integer $k$, where $n$ is the complexity of the input. "

So, then my question is, for my example, what is the complexity of the input? Is the complexity based on how many variables, or how many clauses?

The complexity of SAT relates to the number of arguments to the Boolean function (i.e. the "distinct literals" in the expression), not the number of terms in a particular normal form.

The complexity of an algorithm which solves SAT is related to the size of the input that you give it. So if the input is the Unicode string (x1∨x2∨¬x3)∧(x1¬∨x2¬∨x4)∧(x2∨x3∨x5), then the size of that is the number of Unicode codepoints (or bytes or bits used to encode those codepoints).

The subject of SAT is the function, not the representation of the function. The complexity class (i.e. the complexity of any solver which is optimal for its computer) is the same whether functions are written as product-of-sums or a sum-of-products. This complexity varies with the number of arguments to the function.

The input to a SAT solver is the representation of the function. Your example is in the product-of-sums normal form, which is a common way to express SAT problems. This is not a coincidence — SAT is solved mindlessly if you instead give it a sum-of-products expression! The brute-force method of solving SAT is to enumerate the sum-of-products, where each term either contradicts itself (b ¬b) or represents a satisfied piece of the function's domain. This simple approach doesn't trivialize SAT because going from one normal form to the other causes a combinatorial explosion. The size of the domain of a function of $n$ Boolean arguments is $2^n$.

Thus, feeding a gigantic problem description into a simple algorithm may have the same computational (and space) complexity as feeding a simple but equivalent description into a sophisticated algorithm. For brevity, we tend to prefer to imagine the description to be simple and the algorithm to be complicated.


Does a proof using the well-ordering principle need a base case? For proofs by well-ordering principle the general template is to consider the negation of some predicate $P(n)$. Then assume the set of all elements that fulfill $\lnot P(n)$, i.e.

$\qquad N = \{ n \mid \lnot P(n) \}$

has a smallest element according to WOP, say $m = \min N$, and if we manage to prove that there is another element $m' \in N$ that is less than $m$ that also negates  then we contradict our assumption that $m$ is the smallest element.

My question is that should we be proving some sort of a base case as well for the above mentioned template. As in proving that for some base case, $P(\mathrm{base})$ is true?

In the Wiki page,

  In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element.

Pay attention to the word non-empty.

Consider the negation of P(n). Before you assume the set that satisfying P(n) is false has a smallest element m, you already assume that the set is non-empty. You prove that there is another element that is less than m. This contradicts the assumption that the set is non-empty. Thus, the set is empty which means P(n) is true.

A typical example is show gcd(a,b) = min { ma+nb > 0: integers m,n  }.

By Well-Ordering-Principle this set has a least element x.  One check's it's the GCD.

The GCD certainly divides x.  If it did not divide a or b we could run division algorithm and the remainder would be a smaller number in this set.

We've basically shown the Euclidean algorithm terminates at some point (using WOP), which is the GCD.

Invoking WOP is like the "base case" and checking that x satisfies your properties of interest can be compared to "induction".

The outline for using WOP is

Let's prove P(n) for all n by consider the set where P(n) is false
As a subset of natural numbers there is a least positive number m where P(m) is false
Prove there's a smaller number m' < m where P(m') is still false

Well Ordering Principle and Induction are equivalent even though they feel different.