Is C actually Turing-complete? I was trying to explain to someone that C is Turing-complete, and realized that I don't actually know if it is, indeed, technically Turing-complete. (C as in the abstract semantics, not as in an actual implementation.)

The "obvious" answer (roughly: it can address an arbitrary amount of memory, so it can emulate a RAM machine, so it's Turing-complete) isn't actually correct, as far as I can tell, as although the C standard allows for size_t to be arbitrarily large, it must be fixed at some length, and no matter what length it is fixed at it is still finite. (In other words, although you could, given an arbitrary halting Turing machine, pick a length of size_t such that it will run "properly", there is no way to pick a length of size_t such that all halting Turing machines will run properly)

So: is C99 Turing-complete?

I'm not sure but I think the answer is no, for rather subtle reasons. I asked on Theoretical Computer Science a few years ago and didn't get an answer that goes beyond what I'll present here.

In most programming languages, you can simulate a Turing machine by:

simulating the finite automaton with a program that uses a finite amount of memory;
simulating the tape with a pair of linked lists of integers, representing the content of the tape before and after the current position. Moving the pointer means transferring the head of one of the lists onto the other list.

A concrete implementation running on a computer would run out of memory if the tape got too long, but an ideal implementation could execute the Turing machine program faithfully. This can be done with pen and paper, or by buying a computer with more memory, and a compiler targeting an architecture with more bits per word and so on if the program ever runs out of memory.

This doesn't work in C because it's impossible to have a linked list that can grow forever: there's always some limit on the number of nodes.

To explain why, I first need to explain what a C implementation is. C is actually a family of programming languages. The ISO C standard (more precisely, a specific version of this standard) defines (with the level of formality that English allows) the syntax and semantics a family of programming languages. C has a lot of undefined behavior and implementation-defined behavior. An “implementation” of C codifies all the implementation-defined behavior (the list of things to codify is in appendix J for C99). Each implementation of C is a separate programming language. Note that the meaning of the word “implementation” is a bit peculiar: what it really means is a language variant, there can be multiple different compiler programs that implement the same language variant.

In a given implementation of C, a byte has $2^{\texttt{CHAR_BIT}}$ possible values. All data can represented as an array of bytes: a type t has at most
$2^{\texttt{CHAR_BIT} \times \texttt{sizeof(t)}}$ possible values. This number varies in different implementations of C, but for a given implementation of C, it's a constant.

In particular, pointers can only take at most $2^{\texttt{CHAR_BIT} \times \texttt{sizeof(void*)}}$ values. This means that there is a finite maximum number of addressable objects.

The values of CHAR_BIT and sizeof(void*) are observable, so if you run out of memory, you can't just resume running your program with larger values for those parameters. You would be running the program under a different programming language — a different C implementation.

If programs in a language can only have a bounded number of states, then the programming language is no more expressive than finite automata. The fragment of C that's restricted to addressable storage only allows at most $n \times 2^{\texttt{CHAR_BIT} \times \texttt{sizeof(void*)}}$ program states where $n$ is the size of the abstract syntax tree of the program (representing the state of the control flow), therefore this program can be simulated by a finite automaton with that many states. If C is more expressive, it has to be through the use of other features.

C does not directly impose a maximum recursion depth. An implementation is allowed to have a maximum, but it's also allowed not to have one. But how do we communicate between a function call and its parent? Arguments are no good if they're addressable, because that would indirectly limit the depth of recursion: if you have a function int f(int x) { … f(…) …} then all the occurrences of x on active frames of f have their own address and so the number of nested calls is bounded by the number of possible addresses for x.

A C program can use non-addressable storage in the form of register variables. “Normal” implementations can only have a small, finite number of variables that don't have an address, but in theory an implementation could allow an unbounded amount of register storage. In such an implementation, you can make an unbounded amount of recursive calls to a function, as long as its argument are register. But since the arguments are register, you can't make a pointer to them, and so you need to copy their data around explicitly: you can only pass around a finite amount of data, not an arbitrary-sized data structure that's made of pointers.

With unbounded recursion depth, and the restriction that a function can only get data from its direct caller (register arguments) and return data to its direct caller (the function return value), you get the power of deterministic pushdown automata.

I can't find a way to go further.

(Of course you could make the program store the tape content externally, through file input/output functions. But then you wouldn't be asking whether C is Turing-complete, but whether C plus an infinite storage system is Turing-complete, to which the answer is a boring “yes”. You might as well define the storage to be a Turing oracle — call fopen("oracle", "r+"), fwrite the initial tape content to it and fread back the final tape content.)

Yes it is.

1. Quoted answer

As a reaction on the high amount of downvotes on my (and other) correct answers – in comparison to the alarmingly high approval of false answers – I searched for a less theoretically profound alternative explanation. I found this one. I hope it covers some of the here common fallacies, so that a little more insight is shown. Essential part of the argument:

  [...] His argument is as follows: suppose one has written a given terminating program which may require, during its execution, up to some arbitrary amount of storage. Without changing that program, it is possible a posteriori to implement a piece of computer hardware and its C compiler that provide enough storage to accommodate this computation. This may require widening the widths of char (via CHAR_BITS) and/or pointers (via size_t), but the program would not need to be modified. Because this is possible, C is indeed Turing-Complete for terminating programs.

  The tricky part of this argument is that it only works when considering terminating programs. Terminating programs have this nice property that they have a static upper bound to their storage requirement, which one can determine experimentally by running the program over the desired input with increasing storage sizes, until it “fits.”

  The reason why I was mislead in my train of thoughts it that I was considering the wider class of “useful” non-terminating programs [...]

In short, because for every computable function there is a solution in the C language (due to unlimited upper bounds), every computable problem has a C program, thus C is Turing-complete.

2. My original answer

There are widespread confusions between mathematical concepts in theoretical computer science (such as Turing-completeness) and their real-world application, i.e. techniques in practical computer science. Turing-completeness is not a property of physically existing machines or any in spacetime limited model. It is just an abstract object describing properties of mathematical theories.

C99 is Turing-complete regardless of implementation-based restrictions, just like virtually any other common programming language, since it is able to express a functionally complete set of logical connectives and has in principle access to an unlimited amount of memory. People have pointed out that C restricts the random-memory access explicitly to be limited, but this is nothing one could not circumvent, since these are additionally stated restrictions in the C standard, while Turing-completeness is entailed without them already:

Here is a very basic thing about logical systems that should suffice for a non-constructive proof. Consider a calculus with some axiom schemata and rules, such that the set of logical conseqences is X. Now if you add some rules or axioms, the set of logical consequences grows, i.e. must be a superset of X. This is why, for example, the modal logic S4 is properly contained in S5.
Similarly, when you have a subspecification which is Turing-complete, but you add some restrictions on top, these do not prevent any of the consequences in X, i.e. there must be a way to circumvent all of the restrictions.
If you want a non-Turing-complete language, the calculus must be reduced, not extended. Extensions which claim that something would not be possible, but actually is, only add inconsistency.
These inconsistencies in the C standard may bear no practical consequences though, just like Turing-completeness is unrelated to practical application.

Simulating arbitrary numbers based on recursion depth (i.e. this; with the possibility to support multiple numbers via scheduling / pseudo-threads; there is no theoretical limit to recursion depth in C), or using file storage to simulate unlimited program memory (idea) are probably only two out of infinite possibilities to constructively prove Turing-completeness of C99. One should recall that for computability, time and space complexity are irrelevant. In particular, assuming a limited environment in order to falsify Turing-completeness is merely circular reasoning since that limitation excludes all problems which exceed the presupposed complexity bound.

(NOTE: I only wrote this answer to prevent people from being stopped to gain mathematical intuition due to some kind of application-oriented limited thinking. It is quite a pity that most learners will read the false accepted answer due to it being upvoted based on fundamental flaws of reasoning, so that more people will spread such false beliefs. If you downvote this answer, you are just part of the problem.)


Finding constants C and k for big-O of fraction of polynomials I am a teaching assistant on a course for computer science students where we recently talked about big-O notation. For this course I would like to teach the students a general method for  finding the constants $C$ and $k$ in the definition of big-O
$$
|f(x)| \leq C|g(x)|, x > k,
$$
when the function $f(x)$ is a fraction of polynomials.

I have tried to concoct my own method, but I am unsure of its correctness. I was inspired by the easy method of finding $C$ and $k$ for a polynomial where for example we can show that $x^3+2x+3$ is $O(x^3)$ by
$$
x^3+2x+3 \leq x^3+2x^3+3x^3 = 6x^3
$$
to find $C = 6$ and $k = 1$.

Now, for a fraction of polynomials I am unsure what to do with the denominator. My attempt at a general method is as follows. I would like to show that $\frac{x^4+x^2x1}{x^3+1}$ is $O(x)$. First I divide by the highest term in the denominator to get a $1$ in the denominator:
$$
\frac{(x^4+x^2+1)/x^3}{(x^3+1)/x^3} = \frac{x+\frac{1}{x}+\frac{1}{x^2}}{1+\frac{1}{x^3}}
$$
Now I argue, somewhat analogously to the previous example, that the fractions in the numerator must be less than (when x > 0) x, and since a smaller denominator makes the expression smaller, setting all the terms in denominator except the $1$ to $0$, I obtain the inequality
$$
\frac{x+\frac{1}{x}+\frac{1}{x^2}}{1+\frac{1}{x^3}} \leq \frac{x+x+x}{1+0} = 3x
$$
and I find $C = 3$ and $k = 1$.

Now my question is, does this homebrewed method actually work or is it complete nonsense? And if it is nonsense, does anybody know of another general method for finding $C$ and $k$ in instances like this?

Note that I need to find the constants $C$ and $k$, not just show that a given function is big-O of some other function, and the students have had no course in calculus, so I can use no concepts from there, such as limits.

It works if the denominator doesn't have negative coefficients. Consider, however,
$$ \frac{x}{x-1}. $$
As $x$ tends to infinity, this is $O(1)$. However, your method would give
$$ \frac{x}{x-1} = \frac{1}{1-\tfrac{1}{x}} \leq \frac{1}{1-1} = \infty, $$
which is not very helpful. The problem is that when $x = 1$, the denominator is not positive. In this case it is zero, but for an example like
$$ \frac{x}{x-2} = \frac{1}{1-\tfrac{2}{x}} \leq \frac{1}{-1} = -1, $$
the inequality is in fact wrong.

Often when considering $O(f(x))$, we assume that $f(x)$ is always positive. But sometimes it isn't, and then the assumption that we're making is that $f(x)$ is eventually positive. This is not usually explained when big O notation is defined, but it's the reason behind the extra quantifier "for large enough $x$" which appears in the full definition of big O; this quantifier is only needed when $f(x)$ is not always positive but only eventually positive.

The way to fix the argument is now clear. If $f(x)$ is eventually positive, then take some $y$ such that $f(x) > 0$ for all $y \geq x$, and now apply the method. For example, if $f(x) = x/(x-1)$ then any $y > 1$ would do, say $y = 2$. In that case we have
$$ f(x) = \frac{1}{1-\tfrac{1}{x}} \leq \frac{1}{1-\frac{1}{2}} = 2 $$
for $x \geq 2$.

More generally, suppose that $f(x) = C p(x)/q(x)$, where $p,q$ are monic polynomials (leading coefficient is $1$) and are eventually positive, and $C > 0$. Then for all $\epsilon > 0$ there is $y$ such that for all $x \geq y$,
$$ (C-\epsilon) x^{\deg p - \deg q} < f(x) < (C+\epsilon) x^{\deg p - \deg q}. $$
(Exercise.)

Compare the definition of the Bachman-Landau notations to the definition of a limit when $n \to \infty$, the relation between them is enough for cars like this.


What is the min # of moves to sort an array from 1 to n? Problem: You are required to sort an array with numbers from 1 to n. You can do a "move", which means choosing one element and moving it to
any place you want (insert to any place, not swap). Prove the minimum number of "moves" to sort the array is n - k, where k = the length of the longest increasing subsequence.

Ex: array is [1, 2, 5, 3, 4, 7, 6]

Longest increasing subsequence is [1, 2, 3, 4, 6], which is of length 5. Hence, the answer is 7 - 5 = 2 moves. You move numbers 5 and 7 to the correct spots.

I'd like a proof / intuition on why this has to be the minimum # of moves.

There is an invariant that each move can only increase the number in your longest increasing subsequence by at most 1.

If your initial array has $k$ values in its longest increasing subsequence, you need $n-k$ moves at least to get it sorted.
This shows $n-k$ moves is necessary.

Given answer is wrong because for example -
let the given array is

    3 5 7 1 9 8

In the first step, 1 is removed and placed at first position, as a consequence the array becomes

    1 3 5 7 9 8

In the second step, 9 is removed and placed at the last position in the array, as a consequence the array becomes

    1 3 5 7 8 9

The array is now sorted. It took 2 steps to sort the array. You have to find out the minimum number of steps required to make the array sorted.


Construct SLR Parse table problems Consider the augmented grammar G is:

S` -> S
S -> a
S -> (T)
T -> T,S
T -> S

I have tried to construct parse table. But, when I read '(' nonterminal Symbol (item 3), there is no action table elements either 'shift' or 'reduce'.

I3:
S -> (.T)
T -> .T,S
T -> .S

so I can't construe '(a,(a,a))' in this Parse table.
then is it ambiguous grammar? or I wrong the answer?

I3 productions are:
S->(.T)
T->.T,S
T->.S
here you need to add closure of S
S->.a
S->.(T)


An efficient data structure supporting Insert, Delete, and MostFrequent Assume that we have a set $D$ and each member of $D$ is a data and key pair. We want a data structure that would support the following operations:

Insert $(d,k)$ into $D$,
Delete member $e$, (no need to search to find $e$, e.g. $e$ points to a member in $D$),
MostFrequent, which returns a member $e \in D$ such that $e.key$ is one of the most frequent keys in $D$ (note that the most frequent key doesn't need to be unique).

What would be an efficient implementation of this data structure?

My solution is a heap for the keys and their frequencies prioritized by the frequencies plus a hash table where the hash function maps members with the same key to the same slot in the hash table (with pointers from each part to the other).

This can give $\Theta(\lg n)$ for the first two operations and $\Theta(1)$ for the third (worst case running time).

I am wondering if there is more efficient solution? (or a simpler solution with the same efficiency?)

In the comparison-based model of computation, you may implement the priority queue using a Fibonacci heap instead of an ordinary heap. This will give you the following bounds: $\mathcal{O}(1)$  amortized time for insert and $\mathcal{O}(\log n)$ amortized time for deletion operations.

If you depart from the comparison-based model and adopt the RAM model where keys are regarded as binary strings, each one contained in one or more machine words, you may implement your priority queue in $o(\log n)$. Indeed, you can achieve for both insert and delete operations $\mathcal{O}(\sqrt{\log \log n}) $ and $\mathcal{O}(1) $ time for the findMin operation. Thorup proved that

If we can sort $n$ keys in time $S(n)$ per key, then we can implement a priority queue supporting find-min in constant time and updates (insert and delete) in $S(n)$ time.

See M. Thorup. Equivalence between priority queues and sorting, 2002. in Proc. FOCS 2002

Since we can sort in $\mathcal{O}(n \sqrt{\log \log n}) $ expected time and linear
space, as shown by

Y. Han and M. Thorup. Integer sorting in $\mathcal{O}(n \sqrt{\log \log n}) $ expected time and linear
space. in Proc. FOCS 2002

the bound is proved.

Worst-case complexity
Insert: $\mathcal{O}(1)$
Find-min: $\mathcal{O}(1)$
Decrease-key: $\mathcal{O}(1)$
Delete: $\mathcal{O}(\log \log n)$
Space: $\mathcal{O}(n)$
Proof

THEOREM 1. We can implement a priority queue that with n integer keys in the range $[0 , N )$ in linear space supporting ﬁnd-min, insert, and dec-key in constant time, and delete in $\mathrm{\mathcal{O}(log\ log\ min \{n, N\})}$ time.

Which is established with a combination of:

LEMMA 3. Let $\tau(n, N)$ be the delete time for a priority queue for up to $n$ integers in the range $[0 , N)$ supporting insert and dec-key in constant time. Then $\tau ( n, N ) \le τ ( N, N)$. This holds whether $\tau$ is amortized or worst-case.

and:

THEOREM 6. Theorem 6. We can implement a priority queue that with $n$ integer keys in the range $[0 , N)$ in linear space supporting ﬁnd-min, insert, and dec-key in constant time, and delete in $\mathrm{\mathcal{O}(1 + log\ log\ n − log\ log\ q)}$ time for a key of rank $q$.

Reference
Thorup, Mikkel. “Integer Priority Queues with Decrease Key in Constant Time and the Single Source Shortest Paths Problem.” In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, 149–158. STOC  ’03. New York, NY, USA: ACM, 2003.


Is randomly building a BST different from random sampling whole trees? What is the difference between a randomly built binary search tree (using n keys )and choosing a binary search tree (of n key) from a random distribution

You want to distinguish

  randomly built binary search tree

from

  choosing a binary search tree from a random distribution.

Let me first tell you why this is not a well-posed query. Neither version is
completely specified; the first misses the process by which the tree is built
as well as the used random source, the second lacks a specification of the
distribution to be used. In particular, the "randomly built" trees are
"chosen from a random distribution"!

Now I'll assume that you (or your teacher) made the "usual" assumptions and reformulate
the models.

Starting with the empty tree, we insert keys $s_1, \dots, s_n \in [1..n]$
successively (with BST insertion). The sequence is chosen uniformly at random
from all permutations of $[1..n]$.

This is the famous random permutation model.
Pick a tree uniformly at random from all BSTs with keys $[1..n]$.

There are several ways to see that the two models define different random distributions.

There are $n!$ different permutations but only
$C_n = \frac{1}{n+1} \cdot \binom{2n}{n}$
BSTs. Show that it is not possible to distribute the permutations evenly,
i.e. $C_n$ does not (always) divide $n!$.

In particular, for $n=3$ we have six permutations but five BSTs.
For $n=3$, enumerate all trees and notice that four trees result from one
permutation each while the fifth results from two. Ergo, the random
permutation model is not uniform.
Know (from earlier studies) that BSTs have average height $\Theta(\log n)$
in the random permutation model but $\Theta(\sqrt{n})$ in the uniform model.

The first is a standard result found in most textbooks on the matter. The latter, admittedly, a less known result by Flajolet and Odlyzko [1]; the method of analysis has broader relevance and the result generalises to many families of trees.

The average height of binary trees and other simple trees by P. Flajolet and A. Odlyzko (1982)

Randomly built binary search tree : When binary tree is built by picking n keys one by one randomly from a set of keys.

While binary search tree from a random distribution mean there are all possible ways of binary tree with n keys from a set of keys . and you are picking directly one of the tree.

Only way of making a random binary tree is different.

Randomly built binary search tree will be more efficient to make than the later one.

but both will result in estimated search time of O(log n)


Look Ahead buffer vs Translation Look aside buffer I know that Translation look aside buffer is used for address translation in  paging to achieve better performance.

I came across term called Look Ahead buffer in a document which said it implements Temporal locality.

I tried searching for Look Ahead buffer's but could not get any significant data.

Please help

I do not know the exact definitions of TLBs and look-ahead buffers, but here is what I understand about them.

TLBs help make translations from virtual to physical addresses quicker via caching. So, you can see how the TLB is implementing temporal locality (any kind of caching is implementing temporal locality) in some sense.

Look ahead buffers on the other hand come into play when while bringing data from disk to memory. Pages that are explicitly requested may be brought into the disk buffer along with other pages (often selected based on spatial locality to the requested page -- but there are other heuristics that the disk can use). The idea is to not have to go to disk too often. Instead the disk will try to predict what pages will be required in the RAM in the future (hence the term "look-ahead").

Note: I have heard people call the TLB the look-aside buffer and the look-ahead buffer. To me it seems like "translation look-aside buffer" is the correct expansion (because I dont see where any "looking ahead" is happening).

yes look-ahead buffer can be implemented by working set algorithm to take care of spatial locality.


If O(log n) vs O(n) is exponential what is O(1) vs O(n)? If one refers to using an O(log n) instead of an O(n) algorithm as an exponential speedup,
how would one refer the speedup gained by using an O(1) algorithm vs an O(n)?

There's no name for that, but the closest would be "infinite" speedup. $O(\log n)$ is considered an exponential speedup over $O(n)$, because $n$ is exponential in $\log n$: if we take the exponential function $f(n)=2^n$, we get $f(\log n)=2^{\log n}=n$.

However, $n$ isn't anything in $1$: there's no way to recover $n$ from $1$, no matter how quickly the function $f$ that we take grows, $f(1)$ will always be a constant (and never equal $n$). As $n\to \infty$, $1$ becomes infinitely smaller than $n$.

Your confusion seems to be related to the technical meaning of the word "exponential".
As the definition is given in http://www.learnersdictionary.com, it is defined as:

  Exponential growth is literally growth that becomes faster and faster as it continues. In ordinary use, however, exponential is understood to mean simply “very fast” when it is used with words like growth and increase.

Now, let's consider an example, where n = 256 (a power of 2 for the sake of simplicity).
If n = 256, then \log_2 n = 8. This is an "exponential" speedup, because of the log function.
As far as O(1) is concerned, you need to realize that \log_n n = 1 in general. With that being said, O(1) will also be an ideal "exponential" speedup.
Hope this makes things clear.


Why do we still use a Von Neumann Architecture in modern computers? The Von Neumann architecture was first created in the mid 40s for use in a computing system known as ENIAC for research into the feasibility of thermonuclear weapons.

To this day the Von Neumann architeture is still primary foundation in the majority of modern computers. I have listened to a few historians and scientists mention that there is likely more efficient architectures and that Von Neumann himself didn't believe in its universal capability(unfortunately cannot remember enough to find a link).

So why do we still use this architecture in the majority of modern computing?

So why do we still use this architecture in the majority of modern
  computing?

The assumption itself, first clause: Modern Computer <= Von Neumann

Firstly, do note that the Von Neumann architecture is not used exclusively: almost any current "Von Neumann" machine except for very small microcontrollers (which are occasionally Harvard machines) features several important extensions to the original architecture, from DMA to MMUs.

Specialized coprocessors are very popular - most notably, GPUs.

Those work very well in conjunction to a Von Neumann machine.

The assumption itself, second clause:  Von Neumann <= Modern Computers

The limitations of the Von Neumann architecture and the need for non-Von Neumann architectures for certain applications is well recognized in the scientific community, most importantly whenever "[general] artificial intelligence" of interest, see for example this very recent paper, which continues the line of work started by Carver Mead, who envisioned one of the most radical departures from "classical" architectures in 1989, in the form of analog, time-continuous, highly parallel "neuromorphic" chips.

Your premise is thus, in a way, flawed, unless it is implied that you're referring purely to industrial applications (read on for that part).

On the notion of efficiency

Note that Mead himself had envisioned his architecture as complementary to a traditional Von Neumann machine.

Why?

This brings us to another important point: you mention "more efficient architectures", but efficient for which sort of workload?

Sontag and Siegelmann have famously proved that a feed forward neural network is Turing-complete, as is, of course, the Von Neumann architecture, and if we accept Church's thesis (which has never been seriously challenged in quite a while) that this amounts to the ability to compute all computable functions, they're theoretically interchangeable and unsurpassed in their abilities.

However, leaving aside for a moment the issue of practicality, they are not as efficient for the same applications.

I'm guessing that a neuromorphic chip such as Carver Mead's would make for a terrible Excel machine.

So why mostly Von Neumann in industrial applications?

But yes: even if research has branched in other directions and has gotten to the status of prototypes and early industrial devices Von Neumann architectures are still the bread and butter of industrial applications (and a good foundation to extend with coprocessors and specialized optimizations).

It's safe to assume that the reason is practical:

They're universal -- i.e. "good enough" in the broadest possible sense: they are Turing complete and sufficiently close to some theoretical models such as the TM itself or the URM; it is safe to assume that the ubiquity of the Von Neumann machine has influenced developement of theory as well.
They're tolerably easy to reason about and very well understood by engineers and developers
They work very well for existing industrial workloads that drive the demand for hardware R&D; there is 60 years' worth of algorithms and software for Von Neumann machines.

Von Neumann closed under copper cable?

Finally - and only partly tongue-in-cheek: do note that it is very easy to obtain a decidedly non-Von Neumann machine from off-the-shelf parts: just buy two laptops and connect them with an UTP cable and you have a very strange machine where you don't have uniform, synchronized access to a single mutable storage or a single clock.

Just an example - Volta GPU has 5120 so-called cores. Most modern CPUs has an out-of-order execution. Any modern processor has a lot of built-in caches. Do you still consider that as von-Neumann architectures?


How can I multiply a binary representation by ten using logic gates? So I’m currently working on something and I have converted all decimal digits 0-9 into binary.
But now I want to take say 6 in binary and increase its order of magnitude by base 10 (turning 6 into 60) without converting back to base 10.
Is this possible and if so is there a way to do it with any number, X --> X0 ?

EDIT 1: sorry the first part of the question was super vague and I forgot to mention I’m trying to do this with logic gates.

I assume that the task is to compute $mul(10, a)= 10a$. You don't need to do multiplication. A single binary adder is enough since $$10a = 2^3a + 2a$$
meaning you add one-time left-shifted $a$ to 3-time left-shifted $a$.
For general multiplication $mul(x,y)$ please see this article.

Multiply by 8 (left shift 3) then add to it a multiply by two (left shift 1).


Applying Master Theorem to: T(n) = T(n - 2) + n^2 I've been learning master theorem in school now and have learnt how to apply it to a number of recurrence relations. However one of my assignments has the following recurrence relation:

T(n) = T(n-2) + n^2

Am I wrong in thinking that I cannot apply Master Theorem to this equation? If it can be applied, I am unsure how, as the variable T(n-2) gives no value for "b" which would usually be used to solve with master theorem.

If it can be solved with Master Theorem, how would it be solved? If it cannot be, how would one go about solving this specific recurrence relation?

Thank you in advance for any help and clarification!

Think about what the derivative of T is. If the difference between T (n) and T (n-2) is $n^2$ then the derivative T' (n) is about $n^2 / 2$ and T (n) is about $2/3 · n^3$.

This: Solving Recurrence Relations 'Chip & Conquer'  helped me solve the relation.


Fibonacci Series with Dynamic Programming We can compute Fibonacci numbers by means of dynamic programming approach. If we do not store intermediate solutions, we cannot use them for future necessities. In this case, asymptotic complexity reaches exponential time.

             f(5)    -> 2^0
            /    \
           /      \
          f(4)    f(3)   -> 2^1
         /   \    /   \
       f(3) f(2) f(2) f(1) ->2^2
      /   \
     f(2)f(1)............

Each recursive call consumes only O(1) time.

T(n) = 2^0 + 2^1 + 2^2.... (geometri series)

T(n) = (2^n - 1) / 2 - 1

T(n) = O(2^n)

In some places, it is written that n is size of the problem, but I think n is number of levels in recursion tree. Is n equal to size of the problem or number of recursion levels ?

$n$ is the index of the Fibonacci number you're computing. For example, the sixth Fibonacci number, $f(6)$, is equal to 8.

If we assume that function calls take constant time and we are using your model, then it's clear that the number of calls, $C(n)$, to compute the $n$-th Fib will be given by
$$C(n)=C(n-1)+C(n-2)$$
with $C(0)$ and $C(1)$ both being 1.

Hmm. That recurrence is almost exactly the recurrence for the Fibs, just shifted by a place, so we have $C(n)=f(n+1)$. In other words, the asymptotic growth of $C(n)$ is the same as the Fibs themselves.

n-th number of Fibonacci series is :
f(n) = f(n-1) + f(n-2)
with f(0)=1 & f(1)=1
if we don't use Dynamic programming time complexity will be O(2^n)
but if we use space of O(n) we can do it in O(n) !
We allocate an array A of size n; then we set A[0]=A[1]=1;
now we calculates eazh A[i] i>2 by having A[i-1] and A[i-2] as below :
A[i] = A[i-1] + A[i-2]
so a for loop in O(n) computes f(n) !!


Maximum set packing and minimum set cover duality I read that the maximum set packing and the minimum set cover problems are dual of each other when formulated as linear programming problems. By the strong duality theorem, the optimal solution to the primal and dual LP problems should have the same value.

However, consider a universe $U = \{1, 2, 3, 4, 5\}$ and a collection of sets: $S = \{ \{1, 2, 3\}, \{3, 4, 5\}, \{1\}, \{2\}, \{3\}\}$. From what I understand, a minimum set cover would consist of the first 2 sets in set $S$, while the maximum set packing consists of the last 3 sets. These solutions aren't in accordance with the statement of the strong duality theorem.

Given that, I don't understand how the 2 problems can be dual of each other. What am I missing?

Thank you very much.

There is no contradiction. The strong duality theorem applies to the fractional linear programming formulations of the problems, where one is allowed to set fractional values for the variables, but these formulations are only relaxations of the two original problems. Strong duality does not apply to the integer linear programming formulations (as your example indeed shows).

The actual formulation of the dual of the set-packing problem is:

$$\min \sum_{e \in U} y_e$$
$$ s.t. $$
$$ \sum_{e: e \in s} y_e \ge w_s \quad\quad (s \in S)$$
$$ y_e \ge 0 \quad\quad (e \in U)$$

(Zideon's formulation is wrong, not enough reputation to reply him...)

I got the same confusion with that wiki statement some weeks ago. I will correct that article once I get the time to do it.


Big O Unsure (single problem) int a = 0;
    for (int i = 0; i < n*n; ++i) {
        for (int j = 0; j <= i; ++j) {
            a += j;
        }
    }

Could someone help prove to me that this is function is $O(N^4)$.

I remember doing this problem a while back, but now I do not see it.

I understand that the outer loop is $O(N^2)$ but I am unsure of how this would cause the inner loop to be $O(N^2)$ as well

Consider the range of j in the inner loop:

What is its maximum?
What is its average?
What is its average average?

What does the big-Oh notation mean ? It always gives me an upper bound(worst case scenario) on the running time of an algorithm.

What is the worst-case running time of this algorithm ? It will happen when the outer loop (where i is defined) reaches its maximum value, and so j is subsequently forced to follow till i.

This should give you your answer.


Randomly partition an rectangle into N smaller rectangles I'm looking for an algorithm that can partition a rectangle into N smaller rectangles, at random. N will be small (on the order of 5-10 in most cases). It need not be uniformly at random, but at the very least, I'd like to avoid algorithms which completely exclude interesting classes of partitions.

One algorithm I've come across a few times (including a question on Math.SE about the number of ways to do n partitions), is to randomly divide the rectangle in two by drawing an horizontal or vertical line across it, then do the same thing recursively to the resulting smaller rectangles until you get what you want.

The trick here is that although you can get a number of different partitions using this scheme:

There are some ways of dividing a rectangle into smaller rectangles that this method will never produce:

You can easily see that the divide-and-conquer partitioning will never generate the above, because there's no line that could possibly be the first cut, since no single straight line divides the entire square into two smaller rectangles.

So basically I'm looking for an algorithm to randomly divide a rectangle up into N smaller rectangles, where the results meet the following criteria:

Partitioned into exactly N smaller rectangles
Everything must actually be a rectangle (no L shapes, etc)
No empty space left over

The algorithm as a whole should meet the following criteria:

There is no valid partitioning that the algorithm is incapable of producing
Can be biased towards certain types of  configurations, though the less bias the better.
Preferably works with integer indices.
Does not operate by generating all possible partitions and then picking one at random.

I don't care about asymptotic complexity much, because I'll be working with small numbers.

Here's a simple idea that I believe can generate all partitions.  There are two types of subdivisions:

Given a rectangle, randomly generate a horizontal or vertical line to partition it into two subrectangles.  (The usual "split in two" rule.)
Given a rectangle, randomly generate a rectangle that fits inside it.  Consider the 4 corners of this inner contained rectangle: for each of them, flip a coin and draw a line from this corner outwards towards the outer containing rectangle, with the direction of the line (horizontal or vertical) being determined by what the coin says.  Regardless of the directions of the 4 lines, the result will always be 5 rectangles.  (Some partitions that can be generated by rule 1 can also be generated this way -- in fact, only 2 of the 16 possible configurations of lines will produce partitions that could not be produced by rule 1.)

At any point in time you will have a set of rectangles (initially, just the original one).  Randomly choose one to subdivide (or you could, e.g., choose the biggest, etc.), flip a coin to decide which of the two rules to apply to it, and then apply that rule; keep doing this until you have $n$ rectangles.

Disclaimer: I have no idea how to even think about the set of all partitions, let alone whether the above procedure generates them all with equal probability...  Probably not.

(Disclaimer : I have not thought about throughly nor tested this idea ) ... Why not keep track of the largest available area amongst all of the sections, pick the one with the maximum area and draw a random line segment (either vertical or horizontal) within that selected bounding area. This would create two new section and recurse.


Data structure for getting the k'th largest element I'm given a set of $n$ numbers. Is there a data structure that builds in $O(n)$ (linear time) and gets the $k$'th largest element in $O(k)$ time? Also, is there anything better than $O(k)$?

Here is a solution that uses only comparisons. For simplicity, assume that $n$ is a power of 2.

Find the median of the original array in $O(n)$, and extract the largest $n/2$ elements. Then find the median of the new array in $O(n/2)$, and extract the largest $n/4$ elements. Continue in this way, extracting the $n/8,n/16,\ldots,1$ largest elements. In total, preprocessing takes time
$$ O(n+n/2+n/4+\cdots) = O(2n) = O(n). $$

Given $k$, find $\ell$ such that $n/2^{\ell+1} < k \leq n/2^{\ell}$. By construction, $n/2^\ell < 2k$. The $k$th largest element is thus one of the $n/2^{\ell}$ largest elements. Using the linear time selection algorithm, locate the $k$th element among them in $O(n/2^\ell) = O(k)$.

We can improve the running time for $k \leq Cn/\log n$ (for arbitrary $C$) to $O(1)$ as follows.

During preprocessing, use a linear time selection algorithm to locate the $Cn/\log n$-th largest element in $O(n)$, and extract all larger elements. Sort them in $O(n)$.

During query time, locate the $k$th largest element for $k \leq Cn/\log n$ in $O(1)$ using the new array.

Conversely, we can show that this $O(1)$ behavior cannot extend beyond $O(n/\log n)$ for comparison-based algorithms. Indeed, suppose that there is an algorithm which preprocesses an array in $O(n)$, and is able to locate the $k$th element in $O(1)$ for $k \leq f(n)$, where $f(n) = \omega(n/\log n)$. This allows us to sort an array of size $f(n)$ in time $O(n) + O(f(n)) = o(f(n) \log f(n))$ by adding $n - f(n)$ dummy elements, contradicting the well-known lower bound for sorting.

I don't think there is such algorithm. If there was, you would be able to find median in O(n) which is AFAIK unknown or even it is proven it doesn't exist.


Extending the implementation of a Queue using a circular array I'm doing some exam (Java-based algorithmics) revision and have been given the question:

  Describe how you might extend your implementation [of a queue using a circular array] to support the expansion of the Queue to allow it to store more data items.

The Queue started off implemented as an array with a fixed maximum size. I've got two current answers to this, but I'm not sure either are correct:

Implement the Queue using the Java Vector class as the underlying array structure. The Vector class is similar to arrays, but a Vector can be resized at any time whereas an array's size is fixed when the array is created.
Copy all entries into a larger array.

Is there anything obvious I'm missing?

Using the Vector class is certainly a possibility, as a practical matter. Other solutions will amount to implementing functionality that is similar to what the Vector class provides (possibly in a way that is more efficient given that the data structure stores a queue).

Some languages offer inherently resizable arrays. For example, in C, to allocate an array, you allocate a block of memory of the required size with the malloc function, and you can later resize this block without affecting the data in the remaining part (when shrinking) or the initial part (when extending). Under the hood, realloc may allocate a new region (at a different address in memory) then copy the data, but it'll try to extend or shrink the region in place for efficiency, in which case no copying is necessary.

Most high-level languages do not support resizing existing memory regions. This is because resizing might change the address of the object, which requires modifying all references to that object — C gets away with it by shifting the burden of updating references to the programmer. If you want a resizable array, you can achieve that manually: access the array through an indirect reference, and when you want to resize the array, allocate a new array, copy the data and assign the indirect reference to the new array.

As a simple optimization, if the array size shrinks by a small amount (say, because you take an element from the queue), do not shrink the array: you'll waste a bit of space, but avoid incessantly reallocating the array and moving the data around if successive elements are removed. And if the array size increases by a small amount (say, because you push an element onto the queue), increase the array size by a margin over the requested amount, so that the array will still be good for the next few increases. The Vector class in Java does this: it maintains an elementCount for the array that contains the data; array elements beyond this position are not used.

Asymptotically, you get good behavior by varying the array size exponentially, for example sticking to powers of 2: if you add an element to a 128-element queue, resize the array to 256; if you remove an element from a 65-element queue (in a 128-element array), resize the array down to 64. With array sizes of the form $a^n$, the wasted space is at most $(a-1)$ times the array size. The cost of reallocations, dominated by moving elements when crossing a size boundary is $\Theta(a^n)$. Amortized over a sequence of additions from an empty array or a sequence of removals until the array is empty, the cost of reallocations is $\Theta(a^n/a^n) = \Theta(1)$. In general the amortized cost of reallocations is $O(1)$.

There are other implementations of resizable arrays that avoid reallocation altogether, at the cost of having slower access time to elements. Avoiding reallocations is especially good to avoid long pauses when a reallocation happens and a lot of data needs to be moved around. A simple one is to maintain a list or array of arrays of exponentially increasing size. The element number $2^i + j$ with $j < 2^i$ is stored at position $j$ in array number $i$. No data ever needs to be copied when the array grows or shrinks (except for the bookkeeping data to maintain the collection of array, which grows logarithmically over the total size).

Ummmm... isn't the point of a circular array to wrap around and store some of the data at the beginning? Isn't it just to simply overlap data to fill in bits not already filled, but can be filtered out by using the % operator? Or am I completely wrong?


Should O(1) necessarily stand for a non-zero constant? I had a debate with my friend. He argued that $o(1)\subseteq O(1)$, so if a function converges to 0, then it belongs to both $o(1)$ and $O(1)$. However I imagine that $O(1)$ represents a constant time, in essence, a non-zero constant time. Is there a broad acceptance that a function converging to zero belongs to $o(1)$ and not to $O(1)$?

$O(1)$ does not represent time. It represents a class of functions, which could be used to measure time, space or literally anything else.

$f(x)\in O(1)$ if, and only if, there is a constant $c$ such that $f(x)<c$ for all large enough $x$. There's no requirement that $f$ must be eventually non-zero. $f(x)\in o(1)$ if, and only if, $\lim_{x\to\infty} f(x) = 0$ so, in particular, for all large enough $x$, $f(x)<1$. Therefore, $f(x)\in O(1)$.

I'm going to try to answer a slightly different question than you asked, namely, what the difference is between big-oh and little-oh, and how can you build some good intuition about both of them. If you know that, then the answer to your question is obvious.

I'm also going to ignore absolute values here for the sake of simplicity.

Here's a good way to visualise the difference between big-oh and little-oh. This was never explained to me in this way; I came up with this myself. I hope this helps you, too.

A function $f(x)$ is $O(g(x))$ if there exists a constant $c>0$ such
that there exists a number $x_0$ such that $\forall x>x_0, f(x) \le
   cg(x)$.
A function $f(x)$ is $o(g(x))$ if for all constants $c>0$ there exists
a number $x_0$ such that $\forall x>x_0, f(x) \le cg(x)$.

So the difference between big-oh and little-oh is that big-oh is "there exists a constant $c$", and little-oh is "for all constants $c$".

It should be clear from this alone that if $f(x)$ is $o(g(x))$ then it is also $O(g(x))$. However, there's a wider point here which it's helpful to emphasise.

Informally, $f(x) = O(g(x))$ means that $f(x)$ is eventually within a constant factor of $g(x)$, and the constant is chosen for you. If this measures time, then the constant may be a complex interplay between the CPU designers, the laws of physics, how loaded your machine is, and so on. The point is, it's within a constant factor, and the constant factor is not under your control.

However, $f(x) = o(g(x))$ means that $f(x)$ is eventually within a constant factor of $g(x)$, but you get to pick the constant yourself, and it can be as small as you like. To rub the point in, we often name the constant $\varepsilon$ instead of $c$, because epsilon carries the connotation of "arbitrarily small".

Please let that point sink in before you read on.

Little-oh notation is far more commonly used in space analysis than time analysis, because in time analysis, we typically care about "wall time" (i.e. the time according to a clock on the wall), which invariably changes when you run the same algorithm on a new computer. However, in space analysis, we care about bits, or gigabytes, or something like that. A bit may be physically smaller when a new RAM chip or hard disk gets released, but it's not logically smaller. A bit always can only store one bit of information at the most.

So suppose that you are designing a data structure which information theory states must use at least $f(n)$ bits (say, if you're storing $n$ things in it).

A data structure which uses $f(n) + O(1)$ bits is called implicit.
A data structure which uses $f(n) + O(f(n)) = \left( 1 + O(1) \right) f(n)$ bits is called compact.
A data structure which uses $f(n) + o(f(n)) = \left( 1 + o(1) \right) f(n)$ bits is called succinct.

Informally, a compact data structure has constant relative overhead. This might mean 1%, 5%, or 10 times. That last one might not be as useful as 1% overhead, but still. The point is that the relative overhead (compared to a theoretically perfect solution) is a constant.

A succinct data structure, on the other hand, has a relative overhead which is eventually insignificant.

It should be clear from the above definitions that a data structure that is implicit is automatically succinct, and a data structure that is succinct is automatically compact.


Sort deck of cards with least no of moves We have n cards with each card numbered from 1 to n.

All cards are randomly shuffled but all cards are visible

We are allowed only operation MoveCard(n) which moves the card with value n to the top of the pile.

We need to sort the pile of cards with minimum number of MoveCard operations.

The brute force approach which i can think of is start with MoveCard(n), MoveCard(n-1), MoveCard(n-2).... MoveCard(1).

This approach will solve the problem in n MoveCard operations.

But can we optimize it.

For instance, If the input is like: 3 1 4 2

As per my approach:

4 3 1 2
3 4 1 2
2 3 4 1
1 2 3 4

MoveCard operations is 4.

But we can solve this problem with minimum number of moves:

Optimized solution is:

2 3 1 4
1 2 3 4

MoveCard operations is 2.

The aim is to find the first card which has to be moved. In this case its 2

Given a permutation $\pi:[n]\to[n]$ of cards from $1$ to $n$ you can find the first card to move to the front the following way:

$c \leftarrow n$
for each $k$ from $n$ down to $1$ do
$\space\space\space$ if $c = \pi(k)$ then
$\space\space\space\space\space\space$ $c \leftarrow c - 1$
$\space\space\space$ end if
end for
return $c$

In other words, choose the highest card, for which there is another card of higher value in front of it. More formally, choose a maximum $c\in[n]$ such that there exists a $c' > c$ with $\pi(k') = c'$, $\pi(k) = c$ and $k' < k$. Clearly, this card is not in order yet and since it is the one with the highest value it must be moved first if we want to keep the number of moves minimal. For the permutation $3,1,4,2$ this card is clearly card number $2$.

use Count sort

for x in input:
    count[key(x)] += 1

# calculate the starting index for each key:
total = 0
for i in range(k):   # i = 0, 1, ... k-1
    oldCount = count[i]
    count[i] = total
    total += oldCount

# copy to output array, preserving order of inputs with equal keys:
for x in input:
    output[count[key(x)]] = x
    count[key(x)] += 1

return output

sorry about that. in that case you can pick the first greatest card which is smaller than the top card and move it to top. with this the above example i.e. 4 3 1 2 can be done in three steps and this one 2 3 1 4 in ONE step..


Finding the sum of four squares There is Lagrange's four-square theorem, which statea that

  Given an integer $N$, we can write $N$ as a sum of four squares
  $A^2+B^2+C^2+D^2=N$.

How can I find a valid solution with time complexity of $O(1)$ or $O(\sqrt N)$? I only have to find one solution.

Here is my $O(1)$ algorithm:

while(count!=4){
     solution = sqrt(N)
     print solution
     N-= solution*solution
     count++
}

But it does not works for all $N$, for example it fails for $N=23$. Is there any other solution?

Try this: Legendre's_three-square_theorem

Assume $4\not\mid N$. If not, divide $N$ by $4^k$ and multiply $2^k$ back in the end. Find an $A$ satisfying $N-A^2\not\equiv0,4,7 \mod 8$. It's always valid to choose $A=\lfloor\sqrt{N}\rfloor$ or $\lfloor\sqrt{N}\rfloor-1$. (Choose the even one if $N\equiv 1,5 \mod 8$ and the odd one otherwise.) Now $N-A^2$ is an integer in $O(\sqrt{N})$ and you can find $B,C,D$ in $O(\sqrt{N})$ easily.

Edit: Since $B,C,D\le cN^{\frac{1}{4}}$ for some small constant $c$, we can enumerate two of them (suppose $B$ and $C$) and check whether the corresponding $D$ is an integer. This works in $O(\sqrt{N})$. There might be some faster solutions.

I am going to provide you with 4 links and I hope it will help you.

this one is an online calculator based on an algorithm from math overflow.

http://www.mathcelebrity.com/foursquare.php?num=+178&pl=Show+Lagrange+Four-Square+Notation

the math overflow algorithm can be found here.

https://stackoverflow.com/questions/11732555/how-to-find-all-possible-values-of-four-variables-when-squared-sum-to-n

and then there is also this algorithm from cs stackexchange

How fast can we find all Four-Square combinations that sum to N?

and if you want to do a bit of work, then there is this algorithm that can find the sum of 2 squares for a given integer. So you would have to divide your number in two ( not necessarily equal part ) and then add up the results to get a 4 square representation.

https://math.stackexchange.com/questions/1972771/is-this-the-general-solution-of-finding-the-two-original-squares-that-add-up-to/1977767?noredirect=1#comment4062390_1977767


How to find min or max in constant time using infinite # processors? Given $ n $ numbers and an infinite number of processors can the min or max be found in constant time? Assume a shared memory architecture (all processors can write to a common shared memory) and the ability to perform concurrent writes

I have tried dividing up the numbers into groups of 2 each and then using $n/2$ processors at the first step and then $n/4$ processors on the output of the first step etc. I can't see how to make use of more than $n/2$ processors given that I have $\infty$ of them

I managed to solve this so hoping it's alright to answer your own question.
Initialize to all elements off, an $n$ bit vector $A$ having a 1:1 mapping with the $n $ numbers. Compare each number against every other number on $n \choose 2$ processors. Each processor switches the bit corresponding to the smaller of its two elements to 1. Assumption is that the processors can do concurrent writes to $A$. The bit in $A$ remaining off denotes the maximum element.

This is $\Theta(1)$ (constant time) as the depth of the computational graph is independent of the number of elements. The work required is however $\mathcal {O(n^{2})}$.

If you find max and min using recursion, then the best case complexity is O(log n). So, I think you can get constant time, by dividing the work into n parts and assigning each of that partition to a processor. Infinite processors can be used only when n is too large.


Meaning of the constants that appear in the Master Theorem The general formula for time complexity is $T(n) = aT(n/c) + bn^k$.

If $a> c^k$, the complexity is $O(n^{\log_c a})$.
If $a = c^k$, it is $O(n^k \log n)$.
If $a < c^k$, it is $O(n^k)$.

$a$ is the amount of times the recursive function is called, but what do $b$, $c$, and $k$ represent?

That is not the general formula for time complexity. There is no "general formula  for time complexity", any more than there is a "general formula for the answer."

Rather, the formula you give is a recurrence relation that can be used to compute the running time of certain divide-and-conquer–style recursive algorithms.  Specifically, it corresponds to a recursive function which, when given an input of size $n$, makes $a$ recursive calls, each on inputs of size $n/c$. If you pretended that the recursive calls were "free" (i.e., that they returned their answer in one computation step), then the algorithm would take $bn^k$ steps.

I think you must mean solving recurrences of the form T(n) = aT(n/b) + f(n).

From the relations that you have written I understand that you must be trying to learn the Master Method for solving recurrences. This is used where a divide and conquer strategy is used by the algorithm to solve problems. The D&C strategy divides a given problem into specific parts in order to solve it effectively.

Here a implies the number of parts a single problem is divided into.

(n/b) is  the size of each sub-problem and

f(n) is the cost of solving(combining and splitting) each sub problem.

More details of the master method can be understood from here as suggested earlier by Raphael


Modifying Dijkstra's algorithm for edge weights drawn from range $[1,…,K]$ Suppose I have a directed graph with edge weights drawn from range $[1,\dots, K]$ where $K$ is constant. If I'm trying to find the shortest path using Dijkstra's algorithm, how can I modify the algorithm / data structure and improve the time complexity to $O(|V|+|E|)$?

If edge weights are integers in $\{0,1,\ldots,K\}$, you can implement Dijkstra's to run in $O(K|V|+|E|)$ time, following @rrenaud's suggestion. Here is a more explicit explanation.

At any time, the (finite) keys in the priority queue are in some range $\{D,D+1,\ldots,D+K\}$, where $D$ is the value of the last key removed from the priority queue. (Every key is at least $D$, because the sequence of keys removed by Dijkstra's algorithm is non-decreasing, and every key is at most $D+K$, because every key has value $d[u] + wt(u,w)$ for some edge $(u,w)$ where $d[u]$ is the distance from the source to some vertex $u$ that has already been removed, so $d[u]\le D$.)

Because of this, you can implement the priority queue with a circular array $A[0..K]$ of size $K+1$, with each cell containing a bucket.  Store each vertex with key $k$ in the bucket in cell $A[h(k)]$ where $h(k)=k \bmod (K+1)$. Keep track of $D$.  Do operations as follows:

delete-min: While $A[h(D)]$ is empty, increment $D$.  Then delete and return a vertex from $A[h(D)]$.
insert with key $k$: Add the vertex to the bucket of $A[h(k)]$.
decrease-key $k$ to $k'$: Move the vertex from $A[h(k)]$ to $A[h(k')]$.

Insert and decrease-key are constant-time operations, so the total time spent in those operations will be $O(|V|+|E|)$.  The total time spent in delete-min will be $O(|V|)$ plus the final value of $D$.  The final value of $D$ is the maximum (finite) distance from the source to any vertex (because a delete-min that takes $i$ iterations increases $D$ by $i$). The maximum distance is at most $K(|V|-1)$ because each path has at most $|V|-1$ edges.  Thus, the total time spent by the algorithm is $O(K|V|+|E|)$.

you can use topological sort to find the solution, let the source to have degree 0 then, go from each edge from the source, if another vertex has 0 degree then put it into the queue and keep doing that. in this case(without cycle inside the graph) it can achieve V + E as it would go through every vertex and edges once and only once.


How to solve the optimization of bin packing using the decision version Let us say the optimization version of the bin packing problem asks you to give a packing using the fewest bins possible and the decision version asks if it is possible to pack the bins into $k$ bins.

  How can you reduce the optimization version to the decision version?

If you only have to answer what the fewest bins possible is then it is clear you can use binary search. But if you actually have to give the packing, I can't see how to do it.

If you could solve the decision problem (do these items fit in k bins) you can obviously solve the optimisation problem (what is the minimum number of bins) using binary search. But you actually want to know what to put into each box. That’s easily done doing the decision problem at most n^2 times.

Let’s say you know k boxes are required and sufficient. Sort the item by descending size. Replace the biggest and second biggest item with one item of their combined size and check if the new items fit into k bins. If not, try the largest and third largest item, and so on. After n attempts, you either know two items that are in the same bin in an optimal solution, or you know the largest item is on its own. And you repeat that, each time you find that you can put two items in the same bin by solving at most n decision problems.

There is some inconsistency about whether, in the context of complexity analysis, an optimization problem is defined as asking for the optimal solution or the optimal objective function value. For example, Wikipedia's entry on decision problems says:

  There are standard techniques for transforming function and optimization problems into decision problems. For example, in the traveling salesman problem, the optimization problem is to produce a tour with minimal weight. The associated decision problem is: for each $N$, to decide whether the graph has any tour with weight less than $N$. By repeatedly answering the decision problem, it is possible to find the minimal weight of a tour.

The second sentence defines the optimization problem as producing the optimal tour, whereas the last sentence implicitly defines it as producing the weight of the optimal tour.

Similarly, the entry on optimization problems says:

  For example, if there is a graph $G$ which contains vertices $u$ and $v$, an optimization problem might be "find a path from $u$ to $v$ that uses the fewest edges". This problem might have an answer of, say, 4.

But 4 is not an "answer" to the problem of "find[ing] a path". So, this quote, too, is inconsistent about whether the optimization problem means finding the optimal solution or finding the optimal objective function value.

I am not trying to wade into a debate here about the quality of Wikipedia entries; I'm just trying to make the point that in common usage, there is an inconsistency about the way "optimization problem" is used, and that inconsistency can lead to confusion about the relationship between decision and optimization problems.

Now, back to your original question. If what you are asking is:

  How can you reduce the "find the optimal solution" version of the optimization problem to the decision problem?

then I don't know of a way to do this, though @David Richerby gives one in his answer.

If what you are asking is:

  How can you reduce the "find the optimal objective function" version of the optimization problem to the decision problem?

then the answer is, using binary search, as you have pointed out.

And if what you are really asking is:

  Why does everyone say you can reduce the optimization problem to the decision problem, when it seems impossible?

then my answer is, when people say you can reduce the optimization problem to the decision problem, they mean the "find the optimal objective function" version of the optimization problem, but they are not always sufficiently clear in articulating that.

Now, from a practical perspective, if you are actually going to solve the decision problem, you usually run some algorithm that determines whether the items can be packed into $k$ bins. That algorithm is most likely going to do the packing, so in the course of your binary search, you will find the actual packings.


Do we need recursion in programming language to solve any problem? My question is simple: If we want to be able to solve every problem, that we can solve using recursions, do we need programming language to allow us use recursions?

Assuming we are allowed to use: conditional evaluation of blocks (if/else), cycles(for,while), dynamic allocation of memory.

I know, that we won't be able to implement everything the way we want. However, I'm asking whether we are able to solve everything, just by using different implementation - or by modification of algorithm to be non-recursive.

In short, to answer your questions:

(1) You can convert any recursive algorithm into its non-recursive form.

(2) As stated by the others, you have all the features you need.

Computational Power (Turing-completeness)

You probably know that you cannot solve any problem, for instance, the halting problem is undecidable. And so are many other problems, such as deciding whether an arbitrary formula in first order logic is provable. Thus, with today's knowledge on computability, even the most advanced computer/programming system imaginable won't be able to process every query even if all the data is available.

When assessing the computational power of languages, computer scientists often use the notion of Turing-completeness:
If you can describe (and run) any Turing machine in your programming language, then it is Turing complete and can solve any problem which can be solved by a Turing machine.

To get a feel for Turing machines, I strongly encourage you to use a Simulator and try to solve some simple problems.

In particular, have a look at the syntax of the sample program in the Simulator, which should give you an idea of your minimal language.

Expressive Power and Minimality

When it comes to language design, expressive power is more important to me than the ability to solve any computable problem. Many useful domain-specific languages are not Turing-complete, but address specific problems very well.

However, equally powerful computational models such as the Lambda Calculus (functional programming) or the Pi Calculus (concurrent programming) show that you can have a very small set of elegant, composable language elements to construct larger systems, to be able to reason about their composition while having the computational power of Turing machines at the same time. Beautiful.

So if it is minimality you are looking for, take a closer look at the Lambda Calculus.
Other noteworthy well designed minimal languages are:

LISP
Prolog
Smalltalk and in particular Self

Feel free to add more languages to your personal list (and please let me know ;)

To complete others' answers, I think you might want to check the difference between a recursive process, and a recursive procedure. A recursive procedure doesn't necessarily execute a recursive process. When Babou writes that you can do everything without loops, he is probably secretly thinking about recursive procedures yielding iterative processes.


A Case Distinction on Dynamic Programming: Example Needed! I have been working on dynamic programming for some time. The canonical way to evaluate a dynamic programming recursion is by creating a table of all necessary values and filling it row by row. See for example Cormen, Leiserson et al: "Introduction to Algorithms" for an introduction.

I focus on the table-based computation scheme in two dimensions (row-by-row filling) and investigate the structure of cell dependencies, i.e. which cells need to be done before another can be computed. We denote with $\Gamma(\mathbf{i})$ the set of indices of cells the cell $\mathbf{i}$ depends on. Note that $\Gamma$ needs to be cycle-free.

I abstract from the actual function that is computed and concentrate on its recursive structure. Formally, I consider a recurrrence $d$ to be dynamic programming if it has the form

$\qquad d(\mathbf{i}) = f(\mathbf{i}, \widetilde{\Gamma}_d(\mathbf{i}))$

with $\mathbf{i} \in [0\dots m] \times [0\dots n]$, $\widetilde{\Gamma}_d(\mathbf{i}) = \{(\mathbf{j},d(\mathbf{j})) \mid \mathbf{j} \in \Gamma_d(\mathbf{i}) \}$ and $f$ some (computable) function that does not use $d$ other than via $\widetilde{\Gamma}_d$.

When restricting the granularity of $\Gamma_d$ to rough areas (to the left, top-left, top, top-right, ... of the current cell) one observes that there are essentially three cases (up to symmetries and rotation) of valid dynamic programming recursions that inform how the table can be filled:

The red areas denote (overapproximations of) $\Gamma$. Cases one and two admit subsets, case three is the worst case (up to index transformation). Note that it is not strictly required that the whole red areas are covered by $\Gamma$; some cells in every red part of the table are sufficient to paint it red. White areas are explictly required to not contain any required cells.

Examples for case one are edit distance and longest common subsequence, case two applies to Bellman & Ford and CYK. Less obvious examples include such that work on the diagonals rather than rows (or columns) as they can be rotated to fit the proposed cases; see Joe's answer for an example.

I have no (natural) example for case three, though! So my question is: What are examples for case three dynamic programming recursions/problems?

There are plenty of other examples of dynamic programming algorithms that don't fit your pattern at all.

The longest increasing subsequence problem requires only a one-dimensional table.
There are several natural dynamic programming algorithms whose tables require three or even more dimensions.  For example: Find the maximum-area white rectangle in a bitmap.  The natural dynamic programming algorithm uses a three-dimensional table.
But most importantly, dynamic programming isn't about tables; it's about unwinding recursion.  There are lots of natural dynamic programming algorithms where the data structure used to store intermediate results is not an array, because the recurrence being unwound isn't over a range of integers.  Two easy examples are finding the largest independent set of vertices in a tree, and finding the largest common subtree of two trees.  A more complex example is the $(1+\epsilon)$-approximation algorithm for the Euclidean traveling salesman problem by Arora and Mitchell.

This is exactly not the search space you are looking for but i've an idea of the top of my head which might be of help.

Problem :

Given a $n × n$ matrix say, $M$ with distinct integers in which the entries of each row (from left to right) and each column (from top to bottom) are both sorted in increasing order and the entries in each column are in increasing order . Give an eﬃcient algorithm to ﬁnd the position of an integer $x$ in $M$ (or say the integer is not present in the matrix).

Answer

This can be solved in the following recursive way :

We have an n×n matrix. Let $k = \lceil{\frac{1+n}{2}}\rceil$. Now compare $x$ with
$m_{k,k}$. If $x<m_{k,k}$ we can discard any element $m_{i,j}$ for $k\leq i\leq n$ and $k\leq j\leq n$ i.e., the search space is reduced by $1/4$. Similarly, when $x>m_{k,k}$, the search space is reduced by $1/4$. So after the first iteration, the size of the search space becomes $\frac{3}{4} n^2$. You can do this recursively further as follows: we make 3 comparisons: $x$ with the middle element in each of the remaining three quadrants, and the size of the remaining search space then becomes $\left(\frac{3}{4}\right)^3 n^2$ and so on.


Time Complexity proof for Segment Tree implementation of the ranged sum problem I understand that segment trees can be used to find the sum of sub array of $A$. And that this can done in $\mathcal{O}(\log n)$ time according to the tutorial here.

However I'm not able to prove that the querying time is indeed $\mathcal{O}(\log n)$. This link (and many others) say that we can prove that at each level, the maximum number of nodes processed is $4$ and so $\mathcal{O}(4 \log n) = \mathcal{O}(\log n)$.

But how do we prove this, perhaps by contradiction?

And if so, if we were to use segment trees for ranged sum of higher dimensional arrays, how would the proof be extended?

For example,
I can think of finding a sub matrix sum by dividing the original matrix into 4 quadrants (similar to halving intervals in linear arrays) building a quadrant segment tree but the proof eludes me.

The claim is that there are at most $2$ nodes which are expanded at each level. We will prove this by contradiction.

Consider the segment tree given below.

Let's say that there are $3$ nodes that are expanded in this tree. This means that the range is from the left most colored node to the right most colored node. But notice that if the range extends to the right most node, then the full range of the middle node is covered. Thus, this node will immediately return the value and won't be expanded. Thus, we prove that at each level, we expand at most $ 2 $ nodes and since there are $ \log{n} $ levels, the nodes that are expanded are $ \boxed{2 \cdot \log{n} = \Theta\left( {\log{n}} \right)} $

At each level (L) of tree there would be at max 2 nodes which could have partial overlap. (If unable to prove - why ?, please mention)
So, at level (L+1) we have to explore at max 4 nodes. and total height/levels in the tree is O(log(N)) (where N is number of nodes). Hence time complexity is O(4*Log(N)) ~ O(Log(N)).
PS: Please refer my answer on - Segment tree time complexity analysis


How to determine if a state is a fixed point in a Hopfield network? I have been reading a lot and I am still unsure of how to determine this. Let's say I have an initial binary state vector (1, 1, 1). How would I go about determining whether (1, 1, 1) is a fixed point in the network?

My initial understanding was to put the state through the network and if it converged to (1, 1, 1) then it is a fixed point. However I have a feeling it is not as simple as that.

Thanks.

It's as simple as that.  Write out the state equation.  Substitute the state vector.  Verify that equality holds.   If it does, then you have a fixed point.

Note that what you're calling a state vector probably isn't one in the typical definition of that term.  The vector of neuron inputs is usually called the state vector. It would be unusual (though of course not impossible) for this to be all 1's.

If what you actually have is the output vector, then you can solve for the state vector using the feedback function.  Then verify the resulting state vector is consistent with the outputs.  If so, then you have a fixed point.


Search in a partial ordering defined by tuples of numbers This is a graph theory and partial ordering problem. Consider a set of triples {(di,ai,ci)}i=1...N, which specify edges between two nodes A and B, d denotes a departure time, a an arrival time and c a cost. Technically there can be multiple incomparable costs, for example in $ and % chance that your goods arrive safely.

An example of such a situation could be these 5 edges:

(I did not draw the time axis on scale)

There are five edges, I, II, III, IV and V. The costs are denoted at the edges, they are either 100, 10 or 1. Edge V is drawn red to easily discriminate it from the other edges, since it crosses through them. However, aside from that it is not different.

Given such edges, a few things are important:

An edge is only interesting if it departs after we arrive at A, for example in the image we can arrive at (a), then edge I is not an option anymore. The same goes for edges II and V if we arrive at (b), etc.
Given an arrival and its set of interesting edges, and edge ei is dominated if there exists an edge ej with ej< ei. This is the case iff aj ≤ ai ^ cj ≤ ci ^ (aj < ai v cj < ci). In layman terms, cost and arrival need to be at least as small, but one must be strictly smaller. This is a partial ordering, some edges are incomparable.
Given a arrival in A, I want to find all relevant, undominated (or Pareto) edges.

We can enumerate all the edges:

I:   (0  , 1, 100)
II:  (0.5, 2, 10)
III: (2  , 3, 100)
IV:  (2.5, 4, 10)
V:   (1.5, 5, 1)

Putting them in a partial ordering, using a directed acyclic graph (dag), we get this:

An arrow denotes the <-relation between edges. Note that an edge in this case is a node in the dag: confusing, I know. When I say edge, I mean a node in the dag above.

I added an edge (-∞, -∞), which is always irrelevant, but creates a nice 'root' of the dag. This way we sort of have a tree, where leaves sometimes merge without creating cycles. I also only denote the arrival at B and cost, needed to create the dag, but technically there is also a departure are A for each of the edges.

If we were to arrive at A at -1, we can simply return all the children of (-∞, -∞) as relevant and undominated, but for another arrival we may need to traverse the tree differently (in a more complicated fashion). I was thinking of this:

marker := map from edge to bool # marks whether edge has been traversed
for all edges: marker(edge) := false # none have been traversed

traverse(root, arrival):
    if(marker(root)) return []  #already been at this node
    marker(root) := true;
    if(departure(root) > arrival) return [root]; # return singleton list, all children will be dominated by this edge.

    # this node is irrelevant, but possible some children are relevant.
    l = [];
    for each child of root:
        append traverse(child, arrival) to l
    return l

Traverse returns a list of undominated, relevant edges. However, Is this an efficient way to tackle this problem? Is there a better solution to this problem? Is this problem known under a known name?

I solved my OP as my intuition was. First I created a graph as described by the second picture of the OP. Then I traverse it like this:

global: visited, front

function proceed(arrival)
    visited := array of bool for each node initialized to false
    for each x &isin; front
        proceed(arrival, x)
    return front

function proceed(arrival, node):
    if(visited[node]): return
    visited[node] := true
    if(node.departure > arrival):
       remove node from front
       for each node x:
           append x to the end of front

function calculate_outgoing:
    outgoing := array of lists for each arrival at A, each list contains feasible and relevant A->B connections for that arrival.
    front   := [(-&infin;, -&infin;)]
    for each arrival at A in increasing order:
        outgoing[arrival] := proceed(arrival)
    return outgoing

Initially only the root of the dag is in the is in the front. Then the front is moved towards the 'leaves' of the dag as the arrival times increase, that is, certain options 'fade away' and hence are replaced by other options.

Notice that I have a tree-view on the dag. The key difference is that a node can have more parents, hence I mark which nodes are already visited, preventing one from visiting them twice via different parents.

I find this solution more satisfying then @d-w's, since he did not address the problem of multiple costs, like stated in the OP: "Technically there can be multiple incomparable costs, for example in $ and % chance that your goods arrive safely.", nor did he comment on it. If you have only one cost, his solution is adequate.

This is the problem of enumerating all minimal elements of a partial order.  Your edge dominance relation defines the partial order.

A warmup

In the simple case where you arrive at time $-1$, the partial order consists of all of the "edges", and you're just looking to enumerate all minimal elements in this partial order.

If you don't care about running time, this can be done by computing the dag that corresponds to this partial order and then pulling out all sources (all nodes in the dag with in-degree 0).  Note that every partial order corresponds to a dag (the relation $x<y$ in the partial order corresponds to an edge from $x$ to $y$ in the dag), and so you can construct the dag using your partial order.  The downside is that the running time to construct a dag in a naive fashion will be $O(n^2)$, if you test all pairs of edges for dominance.

In your case, there is a much more efficient algorithm.  Each edge corresponds to a pair $(a,c)$, with the arrival time and the cost.  Imagine plotting these on (the upper-right quadrant of) the 2-D plane.  Now we want the subset of points that don't have any point below-and-to-the-left of them.

This subset can be computed in $O(n \lg n)$ time.  First sort the points by arrival time, i.e., by $a$-value.  Now iterate through the points, in increasing order of arrival time.  As you iterate, keep track of the smallest cost (smallest $c$-value) you've seen so far.  When you see a point that has a smaller cost than any previously seen, add it to the subset: it is a minimal point (it is not dominated by any other point).

In this way, you can find all of the minimal elements of your partial order in $O(n \lg n)$ time, where $n$ denotes the number of edges in your original problem.

The general case

We can adopt the above methods to the more general case where you arrive at time $t$.  Now the partial order consists of all edges that apart after time $t$.

It's easy to construct this partial order with an initial filtering pass: simply throw away all of the edges that depart before time $t$.  This can be done in a simple $O(n)$ time linear scan of all of the edges.

Next, you want to final all the minimal elements in this partial order.   This can be done in $O(n \lg n)$ time, using the method described above.  So, this solves your problem of finding all of the Pareto-minimal (undominated) edges, efficiently.

References

You might like to read the following articles about lattices and partial orders and their role in  computer science:

http://matt.might.net/articles/partial-orders/
http://www.elegantcoding.com/2012/09/lattice-theory-for-programmers-and-non.html


Is there a way to calculate exactly how many binary trees are possible if only one of the preorder, inorder and postorder traversals is given? I am studying tree traversals and I've got to know that we can uniquely determine the binary tree if their:

Case 1. Preorder & inorder traversals are given or

Case 2. postorder & inorder traversals are given

We can not determine the tree if only one of the traversals are given because there will be finitely many trees possible.

My question is that, is there a way to calculate the number of trees possible?

Your question probably assumes that the nodes of the tree all contain different values. If we have a tree with $n$ nodes all of whose have the same label $x$, then we can't tell what tree we're looking at by observing the traversals, as we always get just a series of $x$'s, independent of what the tree shape is or what traversal we use. So I assume the labels are all different.

Use the traversal to generate a list of all the elements of the tree $[x_1, \ldots, x_n]$. Now, which trees are possible with this particular traversal? Pick any tree with $n$ elements and place the labels $x_i$ into the nodes so that for that tree you'll get them back in the order $[x_1, \ldots, x_n]$. This shows that, if we only have one of the traversals available, any tree shape is possible, as long as it has the correct number of nodes $n$. So the answer is that there are $C_n$ such trees, where
$$C_n = \frac{1}{n+ 1}{2 n \choose n}$$
is the $n$-th Catalan number.

Total number of possible Binary Search Trees with n different keys = Catalan number Cn = (2n)!/(n+1)!*n!

For n = 0, 1, 2, 3, … values of Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …. So are numbers of Binary Search Trees.


If all edges are of equal weight, can one use BFS to obtain a minimal spanning tree? If given that all edges in a graph $G$ are of equal weight $c$, can one use breadth-first search (BFS) in order to produce a minimal spanning tree in linear time?

Intuitively this sounds correct, as BFS does not visit a node twice, and it only traverses from vertex $v$ to vertex $u$ iff it hasn't visited $u$ before, such that there aren't going to be any cycles, and if $G$ is connected it will eventually visit all nodes. Since the weight of all edges is equal, it doesn't matter which edges the BFS chose.

Does my reasoning make any sense?

If your graph is unweighted, or equivalently, all edges have the same weight, then any spanning tree is a minimum spanning tree. As you observed, you can use a BFS (or even DFS) to find such a tree in time linear in the number of edges.

If all the edges are of equal weight we can use:

-BFS
-DFS
-Dijkstra's algorithm
-Prim's algorithm

But you cannot use

-kruskal's algorithm


Halting problem vs. automated theorem proving? In the Theory of Computation tutorial offered by Complexity Tree (I just began the 2nd video), it talks about how the Halting problem was developed to show that mathematics could not be automated.  Lately, I've heard quite a bit about automated/automatic theorem proving--some people are even positing that some day mathematicians will be replaced by machines.  My question is: Do we need to find a flaw in the reasoning of the Halting problem to prove that mathematics can be automated?  (Or is the Halting problem, in the age of Machine Learning, reduced to a nice historical account of the past...)

The notion of automating mathematics is a vague one, and that's accounting for the discrepancy here.

One interpretation would be: to automate mathematics would be to produce a machine $M$ which could tell whether or not a given sentence is true (or, more weakly, provable from some agreed-upon set of axioms like $\mathsf{ZFC}$). Even the weaker version is ruled out by the incomputability of the halting problem.

Another interpretation is: to automate mathematics is to produce a machine $M$ which will find proofs of all provable (again, from that agreed-upon set of axioms) sentences. Note that $M$ is not required to determine whether a sentence is provable in the first place, merely to find a proof if such a proof exists at all. This is possible via brute force search.

Of course that second type of automation is highly infeasible - in general, it will take ridiculously long to find proofs of theorems. But that doesn't impact its in-principle-possibility. This is really the starting point of automated theorem proving: trivially brute-force-proof-search is possible, and trivially it's horrible in general - can we find clever proof search strategies in some cases of interest? (And this is where complexity theory enters the picture.)

I think this question should give you the
answer.

https://cstheory.stackexchange.com/questions/2800/if-p-np-could-we-obtain-proofs-of-goldbachs-conjecture-etc

In short, if P=NP then any conjecture with a reasonable length proof can be proved by a computer.


“In object-oriented programming, the program is organized around its data” In a description of OOP in my textbook, it is written that “in procedure oriented program the program is organized around its code while in object oriented programming, the program is organized around its data”. What is the meaning of this statement? An explanation with an example would be of great help.

procedure oriented programming means you can group some operations to finish a task when you know how to do it，step 1，step 2……
object oriented programming means you can inspect a object from two parts，its features (states or data) and its behavior in different states.


How can I reduce Subset Sum to Partition? Maybe this is quite simple but I have some trouble to get this reduction. I want to reduce Subset Sum to  Partition but at this time I don't see the relation!

Is it possible to reduce this problem using a Levin Reduction ?

If you don't understand write for clarification!

Let $(L,B)$ be an instance of subset sum, where $L$ is a list (multiset) of numbers, and $B$ is the target sum. Let $S = \sum L$. Let $L'$ be the list formed by adding $S+B,2S-B$ to $L$.

(1) If there is a sublist $M \subseteq L$ summing to $B$, then $L'$ can be partitioned into two equal parts: $M \cup \{ 2S-B \}$ and $L\setminus M \cup \{ S+B \}$. Indeed, the first part sums to $B+(2S-B) = 2S$, and the second to $(S-B)+(S+B) = 2S$.

(2) If $L'$ can be partitioned into two equal parts $P_1,P_2$, then there is a sublist of $L$ summing to $B$. Indeed, since $(S+B)+(2S-B) = 3S$ and each part sums to $2S$, the two elements belong to different parts. Without loss of generality, $2S-B \in P_1$. The rest of the elements in $P_1$ belong to $L$ and sum to $B$.

this link has a good description of  both reductions, partition to subset-sum and subset-sum to partition.
I think it is more obvious than YUVAL's answer.
useful link


Using Queues for a Stack and Stacks for a Queue I was asked a question on how to use a pair of Queues to create a Stack and how to use a pair of Stacks to create a Queue. Any thoughts on how I would do this? Right now I don't even know where to start.

To answer the question in the comment above-

Two queues to implement a stack(Assume Queue A is filled with elements in LIFO order and Queue B is empty):

PUSH: Empty Queue A into Queue B. LIFO order will be persisted in Queue B. Now insert the new element into Queue A. Now empty Queue B into Queue A.

POP: Dequeue from Queue A

Two stacks to implements a queue -- always fill the stack A in stack B: the last element in stack A is popped (now you got FIFO) -- return elements from stack B to stack A.

Same idea is applied to queues.


Proving that if $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$ I'd really like your help with proving the following.

If $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$.

Here, $\mathrm{NTime}(n^{100})$ is the class of all languages which can be decided by nondeterministic Turing machine in polynomial time of $O(n^{100})$ and $\mathrm{DTime}(n^{1000})$  is the class of all languages which can be decided by a deterministic Turing machine in polynomial time of $O(n^{1000})$.

Any help/suggestions?

Here is the solution using padding. Suppose $L \in \mathrm{NTime}(n^{1000})$. Define a new language $L' = \{x0^{|x|^{10}-|x|} : x \in L\}$. Each $x \in L$ corresponds to some $y \in L'$ of length $|y| = |x| + (|x|^{10}-|x|) = |x|^{10}$. Therefore we can decide whether $y \in L'$ in non-deterministic time $|x|^{1000} = |y|^{100}$, i.e. $L' \in \mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$. In order to decide whether $x \in L$, form $y = x0^{x^{10}-|x|}$ and run the $|y|^{1000} = |x|^{10000}$-time deterministic algorithm for $L'$. We conclude that $L \in \mathrm{DTime}(n^{10000})$.

This is a near trivial consequence of the definition of NP-completeness. If any language in NP is solvable in polynomial time (which is asserted by the premise), then they all are. Another way to look at this is to look at Cook's theorem for NP-completeness that reduces all NP-complete languages to the recognition of a language involving SAT and the conversion of the nondeterministic Turing machine into SAT.


Rearrange an array using swap with 0 This is a Google interview question. I got it from a website.

You have two arrays source and target, containing two permutations of the numbers [0..n-1]. You would like to rearrange source so that it equals to target. The only allowed operations is “swap a number with 0”. Find the minimum number of swaps?
e.g. {1,0,2,3} -> {1,3,2,0}  swap 0 with 3. one swap is enough.

My attempt on problem: If we consider arrays as strings we could use edit distance to convert source to target if other edit distance operations like insert,delete,replace etc are allowed but here only allowed operation is swapping.

Without loss of generality you can assume that the target array is $0,1,...,n-1$: you can "relabel" the target array as 0,1,2,...,n-1 (and relabel the corresponding numbers in the source array, too). The allowed operation becomes "swap a number with x" (where x is not necessarily 0) and the target array is 0,1,2,...,n-1.

You can build a directed graph with $n$ nodes and an edge from node $n_i$ to node $n_j$ if $n_i = j$, i.e. the target position of $n_i$ is $j$ (skip nodes that are already in the correct position). The resulting graph contains one or more distinct cycles.

You can arrange the cycle containing the zero following the arcs in the reverse direction, then "jump" to another cycle and arrange it; the "entry point" doesn't matter.

In the example of the figure above the swap number is zero and the target permutation is $0,1,...6$; after completing the first cycle (blue one) you must enter the second cycle (red one) in order to complete it; if $(n_i \rightarrow n_j)$ is a directed arc of the second cycle, then it must modified in $(n_i \rightarrow 0 \rightarrow n_j)$. The "entry point" is irrelevant (the number of swaps needed to arrange the second cycle doesn't change). You can also interpret the swaps on a cycle like a shift of its numbers.

The procedure always ends with the sorted array (after arranging a cycle, its numbers are never moved again). If there are $m$ cycles and the $i$-th cycle has $p_i>1$ numbers that needs to be arranged and cycle 1 contains the number used for the swaps, the total number of swaps is $(p_1-1)+(p_2+1)+...+(p_m+1)$. If the number used for the swaps is already in place the number of swaps is $(p_1+1)+(p_2+1)+...+(p_m+1)$. To prove that the number of swaps used is optimal, you can observe that every number of each cycle must be moved (requires a swap), and there is no way to move a number of a cycle without "moving" the zero on that cycle.

@Vor's solution is awesome!My simple solution.

public static void ReArray(int[] src) {

    if (src == null || src.length == 0) {
        return;
    }

    int[] reverseSrc = new int[src.length];

    for (int i = 0; i < src.length; i++) {
        reverseSrc[src[i]] = i;
    }

    for (int i = 0; i < src.length; i++) {
        if (reverseSrc[i] == i) {
            continue;
        }

        if (reverseSrc[0] == 0) {
            swap(reverseSrc, 0, i);
            System.out.println(Arrays.toString(reverseSrc));
        }

        while (reverseSrc[0] != 0) {
            swap(reverseSrc, 0, reverseSrc[0]);
            System.out.println(Arrays.toString(reverseSrc));
        }
    }

    System.out.println(Arrays.toString(reverseSrc));
}

public static void swap(int[] reverseSrc, int a, int b) {
    int temp = reverseSrc[a];
    reverseSrc[a] = reverseSrc[b];
    reverseSrc[b] = temp;
    System.out.format("Positon %d and Position %d are swaped. \n", a, b);
}


Find maximum in array without comparisons between elements Suppose $A$ is an array of integers, $|A|=n$, $A=\{a_i|1\leq a_i\leq N, i=1\ldots n\}$.

The goal is to find an efficient algorithm $\cal{F}$ to find maximum element in $A$ with these restrictions:

$\cal{F}$ should not compare any $a_i$ with any $a_j$ ever.
$\cal{F}$ also should not add, subtract or exploit some fancy facts about integers
$\cal{F}$ may, however, compare any $a_i$ with some predetermined constant number, and this number may depend on $N$

Why does algorithm exist? Well, counting sort will work, it never compares elements with each other. Its complexity is $O(n+N)$.

I propose this:

compare all $a_i$ with $N/2$, let $L=\{a_i\in A|a_i<\frac{N}{2}\}$, $U=\{a_i\in A|a_i\geq\frac{N}{2}\}$.

If $U$ isn't empty, we may throw $L$ away and compare $U$ with $3N/4$, etc...

If $U$ is empty, we have our initial problem but now the upper bound is $N/2$. Call algorithm recursively.

Basically, it is binary search on $N$, so it will do in $O(n\lceil\log N\rceil)$ in the worst case. If $N$ is big enough it is better than counting sort.

Two questions:

a) am I correct with my algorithm? I can't see any flows in binary search implementation.

b) it is not obvious to me that binary search in this problem is the best solution, is it possible to do better? If not, how to prove it?

I've added some more explanation to clarify the question. According to comments (thanks, EvilJS) I've used term "comparison-based sorting" wrong, so sorry for that.

a) am I correct?

No, that's not correct. Suppose this array is an unsorted array, and you want to find a maximum element in this array.

First, sorting this array in the increasing order. You can use mergesort or quicksort to sort the array. Mergesort will guarantee the time complexity in the worst and average cases is O(nlogn). However, quicksort will take O(nlogn) for the average case, and O(n) for the worst case. Regarding the worst case of quicksort, if partitioning the array into two groups which one group is empty and another one is (n-1), this will take O(n) time complexity.

Second, after you have a sorted array in increasing order, you can get the maximum element at the last element in the sorted array.

b) is it possible to do better?

You can use heapsort with max heaps property. In this case, the largest element is at the root for max heaps. Heapsort will take O(nlogn) since building maxheap takes O(n) and max-heapifying takes O(logn). It takes only O(1) to find a maximum element.


How was the ALU implemented in the first computer (i.e., Babbage's analytical engine)? I've seen circuit level implementations of ALU's before, but how are NOT/AND/ADD performed mechanically?

Babbage's arithmetic unit (ALU) for the Analytical Engine was originally called the mill. It wasn't constructed out of binary logic gates (AND, OR, NOT). Instead it works on the basis of counting gear teeth and escapements.

The mill is essentially an entire Difference Engine designed to be mechanically controllable/programmable (rather than needing humans to set the input gears to the correct number). The Difference Engine is much more primitive than what we would call a "calculator" today. It is bascially a mechanical abacus. Only, instead of beads it represents numbers by the rotation of gears.

I haven't tried building one so can't quite tell you the exact detail of how it works but in general it works like this:

Two rows of input gears are spun to set it to two numbers.
The gears are connected together in such a way that when you rotate them one "cycle" both will rotate another row of output gears to produce a result. Note that a "cycle" literally means what it means - there is a crank on one end of the machine that you rotate with your arms one round to get the result.
The operation can either add the sum of the input gears or it can subtract one input from another.

That's all it can do, nothing else.

Given that it can do addition and subtraction, and given that we can calculate multiplication by repeated addition and division by repeated subtraction, we can perform any calculation.

In reality Babbage optimized his mill to do more than simply add or subtract (though, the machine can indeed do that). The gears are stacked on top of each other with the output of each stage being used as input for the next stage to calculate polynomials (somehow, I don't know the details). So you can arrange the output rows to represent multipliers in a polynomial equations and you can cycle the mill x number of times to get the result for f(x). But that's more to do with the Difference Engine. The mill for the Analytical Engine could do less specialized calculations.

So Babbage didn't design his "logic" the way a digital designer would design a circuit. He designed it the way a Swiss watch maker would design a complex feature for a handcrafted watch (moon phase display for example).

a video of a working version built in 2008 in the Computer History Museum, at: http://www.computerhistory.org/babbage/