How to eliminate context-free grammar's ambiguity I want to write a CFG that generates the words over {a,b} with the same number of ocurrences of a's and b's.

I have come up with a couple of possibilties so far. I think they're correct but they're all ambiguous, and I want the grammar to be non-ambiguous, this is one option:

S -> aX | bY | ε

X -> bS

Y -> aS

This is another one:

S -> aSb | bSa | SS | ε

And another one:

S -> aSb | bSa | abS | baS | ε

These grammars can generate the word ab in at least two different ways, for example, so they are ambiguous.

Is there any "tip" or "way" to eliminate ambiguity in a context free grammar such as this one?

Thanks for your time and have a nice day! :D

There is no general trick — indeed, given a context-free grammar, it is undecidable to determine whether it is ambiguous or not, and it is also undecidable to determine whether the language it generates is inherently ambiguous or not, see for example this answer on cstheory.

In your case, one way to go is to think of $a$ as corresponding to $\nearrow$ and of $b$ as corresponding to $\searrow$. We are interested in paths that start and end on the $x$ axis, for example
$$
\begin{array}{cccccc}
& \nearrow & \searrow \\
\nearrow & & & \searrow \\\hline
& & & & \searrow & \nearrow
\end{array}
$$
We can decompose every such non-empty path into a first part, which ends the first time that the path reaches back to the $x$ axis, and the rest. If the first part starts with $\nearrow$, then it ends with a $\searrow$ and in between there is a path which never dips below where it started. We can denote such a path by $\top$. Any such path is either empty, or can be decomposed into a first part ending when the path reaches back to the initial level, followed by another $\top$ part. Putting everything together (and consider also the case in which the first part starts with $\searrow$), we obtain the following unambiguous context-free grammar (which for brevity is over $\nearrow,\searrow$):
$$
\begin{align*}
& S \to \epsilon \mid \color{red}\nearrow \top \color{red}\searrow S \mid \color{red}\searrow \bot \color{red}\nearrow S \\
& \top \to \epsilon \mid \color{red}\nearrow \top \color{red}\searrow \top \\
& \bot \to \epsilon \mid \color{red} \searrow \bot \color{red}\nearrow \bot
\end{align*}
$$


How to structure device driver software? I'm asking here for both the scientific, programmatic, and structural format of a device driver. What does that mean? Basically, I'm not asking how to write a driver in general ... I'm asking how to structure one to behave as software that can act as the "middleware" between higher-level code and the hardware itself. I've decided to embark on a journey of low-level computer programming (e.g. systems programming)
to develop reusable software that can "expose" accessibility of hardware memory access by driver calls.

I basically run a freelance group of a small programming team/company, and I've decided to take on development across various retro-gaming platforms from the ground up (those which have decent documentation, or reverse engineering will endue). What I'm asking here is how would one envision the development or structure of software that can act as a intermediary between the application software and the hardware; developmentally, structurally, and programmatically. My choice of console was originally the Nintendo 64's GPU (which I have documentation for). The issue isn't with writing the code to access the GPU, it's with developing a reusable driver/graphics engine (I'm new to it).

I would have asked this at Programmers.SE, but they reject these kind of questions since they're not about specific programming issues, but about careful design methodologies, modularity, and structuring.

So I'll ask again with hope to receive a somewhat explanatory answer on this process ... how do I go about the design methodology, structural format, or developmental logic to create a piece of software that can be accessed by other software to enable device access modularly? In other words, how do I structure and design a driver (i.e. what procedure should I take in creating such software)?

Again, to clarify, I am not asking how to write a driver, but how to go about structuring the system, methodology, and behavior of a driver. Are there any specific ways of going about this that prove successful (e.g. certain data types to define behavior for accessibility, methods used in accessing parts of a driver independently, etc.)?

That very, very much depends on the kernel for which you are writing your driver. I'm (a bit) familiar with Linux. There are structures defined into which your drver has to hook. Those structures define most of the structure you are looking for, the driver itself just hooks into the kernel's structures on startup, gets its marching orders through a structure to be filled with function pointers for the relevant operations on the hardware. See Corbet, Rubini, Kroah-Harman "Linux Device Drivers" (3rd edition, get it here). It is somewhat dated, but the fundamentals haven't changed that much. The Linux Drivers Project gathers people trying to write drivers.

For a graphics card, the picture is quite different, I believe you'll find the above split between the kernel and X.org.

(The above general picture, with the kernel defining the overall architecture and the driver filling in the details of what object-oriented programming fans would call an "object" in an operating system defined device type "class" is the only reasonable way of structuring a non-toy, non-one-machine-only operating system. Most of the time written in C, not C++ or ($deity forbid) Java, but OO all the same.)


Proof that a subtree of a red-black tree has no more than $\frac{3n}{4}$ nodes I have a red-black tree with $n$ nodes, rooted at $x$. How can I prove or disprove that the number of nodes in any subtree of $x$ (including the root of the subtree) will never be greater than $\frac{3n}{4}$?

Here is a natural approach to explore the extreme case.

Let node $r$ be the root of a red-black tree.

Let its left subtree be a red-black tree of black height $h$ that has the minimum number of the nodes among red-black tree of the same black height.

Let its right subtree be a red-black tree of the same black height $h$ that has the maximum number of the nodes among red-black tree of the same black height.

Now let $h=1,2,3,\cdots$ be larger and larger. Can you see the trend?

Here is a related exercise.

Exercise (red-black trees may not be weight-balanced). Given $\alpha\lt 1$, show that there is a red-black tree which has a proper subtree that has more than $\alpha$ of all nodes.


How exactly does a CPU do process scheduling? I know in theory how various scheduling algorithms work, such as round robin, where each process is given small time slices to run a few instructions, before the operating system passes execution onto the next process, and so on.

What I don't understand is how this is possible. The operating system is just some code, and so are all of the processes, so why doesn't this happen?

OS passes execution to the first process.
Now that process is running, the OS can't stop it, since the CPU can only run one instruction at a time, and that instruction is the process'.
Now the operating system has no control over the process, and can't stop it.

Now obviously this doesn't happen, but why not? How would the operating system say something like "Okay, you can run 3 instructions now, but after that let the other process run"?

The operating system arranges for periodic timer interrupts, which only it can handle, so it periodically regains control of the CPU without requiring the co-operating of any other process. Also, when a process tries to access the hardware, that is mediated by the operating system, which gives it another opportunity to decide which process to run next.


Prove or disprove: L^2 context free implies L is context free Clearly we have to disprove this. But I am finding it hard to prove it. I was trying in following way: Considering any non context free language L. I was trying to prove that L^2 is context free which will contradict given statement. But I don't know to how to prove it. Because by pumping lemma we can show only that language is not CFL but converse is not true. Can you please help me. Or is there any other way to prove it. Thanks

Hint. Let $U\subseteq\mathbb{N}$ be any undecidable set and let $I = \{2u+1\mid u\in U\} \cup \{0, 2, 4, \dots\}$. Let $L = \{a^i\mid i\in I\}$. Now prove that $L^2$ is context-free but $L$ is not.


How do I do sum of first k elements of a row of a Pascal's Triangle efficiently? More specifically, I want to:

$^nC_0 + ^nC_1 + ^nC_2 + ..... + ^nC_k$

I tried doing it linearly by calculating $^nC_{j+1}$ by multiplying $^nC_{j}$ with (n-j+1)/j.

The answer it gives is correct for small numbers. Since n and k can be large, I need have keep modding with P, a given prime number.

My method fails since I have to divide with j, which breaks the mod.
Any suggestions?

Your method is fine.  You just need to know how to do modular division.  Modular division is a bit different from division of two integers.  You can do modular division, say $x/y \bmod p$, by computing computing the modular inverse of $y$, $y^{-1}\bmod p$, and then multiplying that by $x$.  You can compute the modular inverse using the extended Euclidean algorithm.

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

A slight correction:

$${n \choose j+1} = {n \choose j} \times {(n-j) \over j+1}.$$

You had an off-by-one error in the formula.  To do this modulo $p$, replace dvision by $j+1$ with multiplication by the modular inverse of $j+1$ modulo $p$.


Is detecting "doubly" arithmetic progressions 3SUM-hard? This is inspired by an interview question.

We are given an array of integers $a_1, \dots, a_n$ and have to determine if there are distinct $i \lt j \lt k$ such that

$a_k - a_j = a_j - a_i$
$k - j = j - i$

i.e, the sequences $\{a_i, a_j, a_k\}$ and $\{i,j,k\}$ are both in arithmetic progression.

There is an easy $O(n^2)$ algorithm for this, but finding a sub-quadratic algorithm seems elusive.

Is this a known problem? Can we prove 3SUM-hardness of this? (or maybe provide a sub-quadratic algorithm?)

If you like, you can assume $0 \lt a_1 \lt a_2 \lt ... \lt a_n$ and that $a_{r+1} - a_{r} \le K$ for some known constant $K > 2$. (In the interview problem, $K = 9$).

This is an open problem.

Possibly some weak form of 3SUM-hardness could be proved by adapting a result from Mihai Pătrașcu's STOC 2010 paper "Towards Polynomial Lower Bounds for Dynamic Problems".  First, let me define a sequence of closely related problems.  The input to each problem is a sorted array $A[1..n]$ of distinct integers.

3SUM: Are there distinct indices $i,j,k$ such that $A[i] + A[j] = A[k]$?
Convolution3SUM: Are there indices $i<j$ such that $A[i] + A[j] = A[i+j]$?
Average: Are there distinct indices $i,j,k$ such that $A[i] + A[j] = 2 A[k]$?
ConvolutionAverage: Are there indices $i<j$ such that $A[i] + A[j] = 2A[(i+j)/2]$? (This is the problem you're asking about.)

In my PhD thesis, I proved that all four of these problems require $\Omega(n^2)$ time in a decision-tree model of computation that allows only queries of the form "Is $\alpha A[i] + \beta A[j] + \gamma A[k] + \delta$ positive, negative, or zero?", where $\alpha,\beta,\gamma,\delta$ are real numbers (that don't depend on the input).  In particular, any 3SUM algorithm in this model must ask the question "Is $A[i] + A[j]$ bigger, smaller, or equal to $A[k]$?" at least $\Omega(n^2)$ times.  That lower bound doesn't rule out subquadratic algorithms in a more general model of computation — indeed, it is possible to shave off some log factors in various integer RAM models.  But nobody knows what sort of more general model would help more significantly.

Using a careful hashing reduction, Pǎtrașcu proved that if 3SUM requires $\Omega(n^2/f(n))$ expected time, for any function $f$, then Convolution3SUM requires $\Omega(n^2/f^2(n\cdot f(n)))$ expected time.  Thus, it's reasonable to say that Convolution3SUM is "weakly 3SUM-hard".  For example, if Convolution3SUM can be solved in $O(n^{1.8})$ time, then 3SUM can be solved in $O(n^{1.9})$ time.

I haven't ground through the details, but I'd bet that a parallel argument implies that if Average requires $\Omega(n^2/f(n))$ expected time, for any function $f$, then ConvolutionAverage requires $\Omega(n^2/f^2(n\cdot f(n)))$ expected time.  In other words, ConvolutionAverage is "weakly Average-hard".

Unfortunately, it is not known whether Average is (even weakly) 3SUM-hard!  I suspect that Average is actually not 3SUM-hard, if only because the $\Omega(n^2)$ lower bound for Average is considerably harder to prove than the $\Omega(n^2)$ lower bound for 3SUM.

You also ask about the special case where adjacent array elements differ by less than some fixed integer $K$.  For 3SUM and Average, this variant can be solved in $O(n \log n)$ time using Fast Fourier transforms as follows.  (This observation is due to Raimund Seidel.)

Build a bit vector $B[0..Kn]$, where $B[i]=1$ if and only if the integer $A[1]+i$ appears in the input array $A$.  Compute the convolution of $B$ with itself in $O(Kn\log Kn) = O(n\log n)$ time using FFTs.  The resulting array has a non-zero value in the $j$th position if and only if some pair of elements in $A$ sum to $2A[1] + j$.  Thus, we can extract a sorted list of sums $A[i]+A[j]$ from the convolution in $O(n)$ time.  From here, it's easy to solve Average or 3SUM in $O(n)$ time.

But I don't know a similar trick for Convolution3SUM or ConvolutionAverage!


Why are word sizes in modern CPU’s a power of 2? Word size of most modern cpu’s is 32 or 64 bits. Both are a power of 2.

This looks “intuitively reasonable”, because a bit has 2 states, but I don’t actually have a hard argument for why this is the case. Moreover, in the past, word sizes of processors have been multiples of other numbers, such as multiples of 6 (because characters were encoded in 6 bits).

What is the reason that chip designers have chosen to make word sizes a multiple of 2?

There is no good reason really. Having 12/24/48/96 bit would have been much more useful.

Historically, if we had had 12 bit bytes, then color graphics storing 1 byte per pixel would have had 16 different values for red, green and blue components, and we would never have suffered the madness of color palettes in graphics hardware.

Nowadays, you could store Unicode codepoints usually in a 12 bit byte, and sometimes using two 12 bit bytes.

48 bit pointers would still be plenty (enough to address 256 Terabyte of RAM, but with 12 bits per byte, so this would actually equivalent to 384 Tera octets).

48 bit floating point is enough for most purposes (where 32 bit floating point isn't).


Check if intersection of several 2D half-planes is empty I have a large set of half-planes $a_ix+b_iy + c_i \geq 0$.
What I need is is the fastest way to determine if they have at least one common point.
Currently I build a convex polygon by adding half-planes sequentially, there are $O(n^2)$ checks if a point belongs to a half-plane.
I need an algorithm that does $O(n \log n)$ or $O(n)$ checks.

Your problem can be solved in linear time.

This paper describes a method to solve a system of $n$ linear inequalities with at most two variables per inequality and $m$ distinct variables in total in $O(n m^3 \log m)$ time. (I am swapping the meaning of $n$ and $m$ with respect to the paper in order to keep the name $n$ consistent with your question).

In your case $m=2$ therefore the resulting time complexity is $O(n)$.


What is the difference between Abstract Data Types and objects? An answer on Programmers.SE characterizes an essay by Cook (Objects are not ADTs) as saying

  Objects behave like a characteristic function over the values of a    type, rather than as an algebra. Objects use procedural abstraction rather than type abstraction
  ADTs usually have a unique implementation in a program. When one's    language has modules, it's possible to have multiple implementations  of an ADT, but they can't usually interoperate.

It seems to me that, in Cook's essay, it just happens to be the case that for the specific example of a set used in Cook's paper, an object can be viewed as a characteristic function. I don't think that objects, in general can be viewed as characteristic functions.

Also, Aldritch's paper The power of interoperability: Why objects are inevitable¹ suggests

  Cook’s definition essentially identifies dynamic dispatch as the most
  important characteristic of object

agreeing with this and with Alan Kay when he said

  OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things.

However, these companion lecture slides to Aldritch's paper suggest that Java classes are ADTs while Java interfaces are objects -- and indeed using interfaces "objects" can inter-operate (one of the key features of OOP as given by one of the bullet points above).

My questions are

Am I correct to say that characteristic functions are not a key feature of objects and that Frank Shearar is mistaken?
Are data that talk to each other through Java interfaces examples of objects even though they don't use dynamic dispatch? Why? (My understanding is that dynamic dispatch is more flexible, and that interfaces are a step towards objective-C/smalltalk/erlang style messaging.)
Is the idea of dependency inversion principle related to the distinction between ADTs and objects? (See the Wikipedia page or The Talking Objects: A Tale About Message-Oriented Programming) Although I'm new to the concept, I understand that it involves adding interfaces between "layers" of a program (see wikipedia page diagram).
Please provide any other examples/clarifications of the distinction between objects and ADTs, if you want.

¹  This paper (published in 2013) is easy reading and summarizes Cook's 2009 paper with examples in Java. I highly recommend at least skimming it, not to answer this question, but just because it's a good paper.

Google brought up a similar question with an answer that I think is very good. I've quoted it below.

  There's another distinction lurking here that is explained in the Cook
  essay I linked.

  Objects are not the only way to implement abstraction. Not everything
  is an object. Objects implement something which some people call
  procedural data abstraction. Abstract data types implement a different
  form of abstraction.

  A key difference appears when you consider binary methods/functions.
  With procedural data abstraction (objects), you might write something
  like this for an Int set interface:

interface IntSet {
  void unionWith(IntSet s);
  ...
}

  Now consider two implementations of IntSet, say one that's backed by
  lists and one that's backed by a more efficient binary tree structure:

class ListIntSet implements IntSet {
  void unionWith(IntSet s){ ... }
}
class BSTIntSet implements IntSet {
  void unionWith(IntSet s){ ... }
}

  Notice that unionWith must take an IntSet argument. Not the more
  specific type like ListIntSet or BSTIntSet. This means that the
  BSTIntSet implementation cannot assume that its input is a BSTIntSet
  and use that fact to give an efficient implementation. (It could use
  some run time type information to check it and use a more efficient
  algorithm if it is, but it still could be passed a ListIntSet and have
  to fall back to a less efficient algorithm).

  Compare this to ADTs, where you may write something more like the
  following in a signature or header file:

typedef struct IntSetStruct *IntSetType;
void union(IntSetType s1, IntSetType s2);

  We program against this interface. Notably, the type is left abstract.
  You don't get to know what it is. Then we have a BST implementation
  then provides a concrete type and operations:

struct IntSetStruct {
 int value;
 struct IntSetStruct* left;
 struct IntSetStruct* right;
}

void union(IntSetType s1, IntSetType s2){ ... }

  Now union actually knows the concrete representations of both s1 and
  s2, so it can exploit this for an efficient implementation. We can
  also write a list backed implementation and choose to link with that
  instead.

  I've written C(ish) syntax, but you should look at e.g. Standard ML
  for abstract data types done properly (where you can e.g. actually use
  more than one implementation of an ADT in the same program roughly by
  qualifying the types: BSTImpl.IntSetStruct and ListImpl.IntSetStruct,
  say)

  The converse of this is that procedural data abstraction (objects)
  allow you to easily introduce new implementations that work with your
  old ones. e.g. you can write your own custom LoggingIntSet
  implementation, and union it with a BSTIntSet. But this is a
  trade-off: you lose informative types for binary methods! Often you
  end up having to expose more functionality and implementation details
  in your interface than you would with an ADT implementation. Now I
  feel like I'm just retyping the Cook essay, so really, read it!

I would like to add an example to this.

Cook suggests that an example of an abstract data type is a module in C. Indeed, modules in C involve information hiding, since there are public functions that are exported through a header file, and static (private) functions that don't. Additionally, often there are constructors (e.g. list_new()) and observers (e.g. list_getListHead()).

A key point of what makes, say, a list module called LIST_MODULE_SINGLY_LINKED an ADT is that the functions of the module (e.g. list_getListHead()) assume that the data being input has been created by the constructor of LIST_MODULE_SINGLY_LINKED, as opposed to any "equivalent" implementation of a list (e.g LIST_MODULE_DYNAMIC_ARRAY). This means that the functions of LIST_MODULE_SINGLY_LINKED can assume, in their implementation, a particular representation (e.g. a singly linked list).

LIST_MODULE_SINGLY_LINKED cannot inter-operate with LIST_MODULE_DYNAMIC_ARRAY because we can't feed data created, say with the constructor of LIST_MODULE_DYNAMIC_ARRAY, to the observer of LIST_MODULE_SINGLY_LINKED because LIST_MODULE_SINGLY_LINKED assumes a representation for a list (as opposed to an object, which only assumes a behaviour).

This is analogous to a way that two different groups from abstract algebra cannot interoperate (that is, you can't take the product of an element of one group with an element of another group). This is because groups assume the closure property of group (the product of elements in a group must be in the group). However, if we can prove that two different groups are in fact subgroups of another group G, then we can use the product of G to add two elements, one from each of the two groups.

Comparing the ADTs and objects

Cook ties the difference between ADTs and objects partially to the expression problem. Roughly speaking, ADTs are coupled with generic functions that are often implemented in functional programming languages, while objects are coupled with Java "objects" accessed through interfaces.
For the purposes of this text, a generic function is a function that takes in some arguments ARGS and a type TYPE (pre-condition); based on TYPE it selects the appropriate function, and evaluates it with ARGS (post-condition). Both generic functions and objects implement polymorphism, but with generic functions, the programmer KNOWS which function will be executed by the generic function without looking at the code of the generic function.
With objects on the other hand, the programmer does not know how the object will handle the arguments, unless the programmers looks at the code of the object.
Usually the expression problem is thought of in terms of "do I have lots of representations?" vs. "do I have lots of functions with few representation". In the first case one should organize  code by representation (as is most common, especially in Java). In the second case one should organize code by functions (i.e. having a single generic function handle multiple representations).
If you organize your code by representation, then, if you want to add extra functionality, you are forced to add the functionality to every representation of the object; in this sense adding functionality is not "additive". If you organize your code by functionality, then, if you want to add an extra representation - you are forced to add the representation to every object; in this sense adding representations in not "additive".

Advantage of ADTs over objects

Adding functionality is additive
Possible to leverage knowledge of the representation of an ADT for performance, or to prove that the ADT will guarantee some postcondition given a precondition. This means that programming with ADTs is about doing the right things in the right order (chaining together pre-conditions and post-conditions towards a "goal" post condition).

Advantages of objects over ADTs

Adding representations in additive
Objects can inter-operate
It's possible to specify pre/post conditions for an object, and chain these together as is the case with ADTs. In this case, the advantages of objects are that  (1) it's easy to change representations without changing the interface and (2) objects can inter-operate. However, this defeats the purpose of OOP in the sense of smalltalk. (see section "Alan Kay's version of OOP)

Dynamic dispatch is key to OOP

It should be apparent now that dynamic dispatch (i.e. late binding) is essential for object oriented programming. This is so that it's possible to define procedures in a generic way, that doesn't assume a particular representation. To be concrete - object oriented programming is easy in python, because it's possible to program methods of an object in a way that doesn't assume a particular representation. This is why python doesn't need interfaces like Java.

In Java, classes are ADTs. however, a class accessed through the interface it implements is an object.

Addendum: Alan Kay's version of OOP

Alan Kay explicitly referred to objects as "families of algebras", and Cook suggests that an ADT is an algebra. Hence Kay likely meant that an object is a family of ADTs. That is, an object is the collection of all classes that satisfy a Java interface.

However, the picture of objects painted by Cook is far more restrictive than Alan Kay's vision. He wanted objects to behave as computers in a network, or as biological cells. The idea was to apply the principle of least commitment to programming - so that it's easy to change low level layers of an ADT once the high level layers have been built using them. With this picture in mind, Java interfaces are too restrictive because they don't allow an object to interpret the meaning of a message, or even ignore it completely.

In summary, the key idea of objects, for Kay - is not that they are a family of algebras (as is emphasized by Cook). Rather, the key idea of Kay was to apply a model that worked in the large (computers in a network) to the small (objects in a program).

edit: Another clarification on Kay's version of OOP: The purpose of objects is to move closer to a declarative ideal. We should tell the object what to do - not tell it how by micromanaging is state, as is customary with procedural programming and ADTs. More info can be found here, here, here, and here.

edit: I found a very, very good exposition of Alan Kay's definition of OOP here.


differences between theoretical research and applied research What would be the differences between these two branches of research? For what I know the theoretical research is the one that will not necessarily end up with an application part, but the applied research deals with experimentation.

So it would be safe to say that applied research = experimental research?

Could anybody can bring up some examples to show the difference between these two types of research in the field of Computer Science?

I have been searching for some information about these topics, but I was not able to get a definitive answer.

Thanks

Rule of thumb:

Theoretical research concerns itself with models: defining models, determining their properties and theorems that hold given a set of models.
Applied research concerns itself with the real world: solving problems given a real context governed by physical (or social) laws.

Obviously, the two are intertwined and not always clearly separated. For instance, TCSists sometimes call a piece of work "applied" if the model of choice somewhat resembles reality, in contrast to being completely academic.


Showing that Independent set of size $k$ can be decided using logarithmic space An independent set $I$ is a subset of the nodes of a graph $G$ where: no 2 nodes in $I$ are adjacent in $G$. For natural number $k$, the problem $k-\text{IND}$ asks if there is an independent set of size $k$.

I'd really love your help with showing that $k-\text{IND} \in {\sf L}$, i.e., can be decided using deterministic logarithmic space.

You can use the following algorithm.

I assume that the vertices are labeled $1,\ldots,m$. You enumerate all $k$-tuples $\{1,\ldots , m\}^k$. This can be done by reserving $k$ counters on the TM tape. Since $k$ is not part of your input this needs only $O(\log m )\subseteq O(\log n)$ space. However for every $k$-tuple you can test if it is an independent set. Simpy test all pair of selected vertices if there are not connected by an edge. Again, since $k$ is fixed the edges you have to test (depending on the current tuple) are known. Thus this test can be hard-wired into the TM program, and therefore needs no extra-space.


Number of maximal cliques in graphs without common neighbourhoods Let's consider a graph $G(n)$ of $n$ vertices such as no two vertices in $G$ have the same exact neighbors (different open neighbourhoods to be more specific; I wonder if this kind of graphs have already a name). Which is the maximum number of maximal cliques of such graphs? Is that amount polynomically bounded?
Additional related question: which extra conditions must such graphs have to be planar? This is in fact a related question because planar graph does indeed have a polynomically bounded amount of maximal cliques.

Suppose that $n$ is a perfect square, and identify its vertex set with $\{1,\ldots,\sqrt{n}\}^2$. Connect $(a,b)$ to $(c,d)$ if $a \neq c$ and $b \neq d$. You can identify a vertex from the set of its neighbors, so the open neighborhoods are all distinct. The number of maximal cliques is $\sqrt{n}!$, which isn't polynomial.


Pushdown automaton with binary stack I have a problem where I'm asked to prove that if P is a pushdown automaton, then  there exists another pushdown automaton P' with only two symbols in its stack alphabet that accepts the same language as P.
I've tried to codify the stack alphabet of P in binary, using the same ammount of symbols for each representation so I know where the codification of one symbol starts and ends, but I don't know how to simulate P with P'.

You're on a good path!  Keep at it.  Remember that a pushdown can have a finite-state control, and you can remember up to a finite amount of information in the finite-state control.  Also, it can have $\epsilon$-transitions (so the read head doesn't consume any of the input).  Those might be helpful.


Counting subarrays that satisfy either of two conditions We have an array of integers $a[]$, with each $|a[i]| \leq 10^{6}$, $size(a)\leq10^{5}$, and $a[i]-a[i-1]\leq100$.

Then we define the term range as a subarray $[x,y]$ of the array $a[]$,  $x \lt y$.

We need to find total number of ranges that satisfy the property that for two given ranges $([x_{1},y_{1}]$ and $[x_{2},y_{2}])$ either one or more of the below conditions are true:

1) $(y_{1} – x_{1} \neq y_{2} – x_{2})$

2) $a[x_{1}+k] – a[x_{1}+k-1] \neq a[x_{2}+k] – a[x_{2}+k–1]$ for some $k \in \{1, 2, ... y_{1}-x_{1}\}$.

How can we visualize this problem? Is this related to some classical problem?

I don't want to give away the solution -- I want you to have the chance to experience the pleasure of finding a nice solution on your own -- but I'll suggest a bunch of hints that might help:

To count the number of range-pairs that satisfy either 1) or 2), you could instead count the number of range-pairs that satisfy neither 1) nor 2) (and then adjust your answer appropriately).  What would it mean for a range-pair to violate 1) and violate 2)?  Try writing out the conditions.  I think you might find that those conditions are easier to think about.  When I suggest you write out the conditions, I really do mean it: write it down, in full, and then stare at the result for a while.  I think you'll be able to find how this is related to another problem that is easier to state.
You might look at the first derivative of the array $a[]$.  In other words, let the array $b[]$ be defined by $b[i] = a[i]-a[i-1]$ (so $size(b) = size(a)-1$).  Now translate the conditions so that they refer to $b$ instead of $a$.  Write down the result, simplify as much as possible, and stare at it.  I think you'll find that helps you write down a cleaner version of the problem statement, which makes this problem look even cleaner and helps you see how this might be related to some other problem that is easier to restate.  Hint: repeated substrings....
You might find it interesting and helpful to learn about algorithms for the longest common substring problem, the Rabin-Karp hash function, and rolling hash functions.  Suffix trees may be helpful, too.
If you're still stuck, try counting the number of such range-pairs where the ranges are of length 1 (i.e., $y_1-x_1=y_2-x_2=1$).  Can you do it?  Now try counting the number of such range-pairs of length 2.  How would you do that?  Can you do it?  Is there a simple way to think about what that's counting?  Now how about the number of range-pairs of length 3.  Once you've solved all three of those, does that give you any ideas for how to generalize?  I'm not trying to suggest that this is literally the algorithm you should use (it's one possible algorithm, but you can build better ones), but that this will help you conceptualize what this is asking you to solve and it might help you think about the problem more clearly so that you can identify even better solutions.

Finally: You'll need to spend some significant time struggling with this problem on your own.  Be prepared to have to try out many different ideas and have most of them go nowhere. Be persistent. Don't expect it's just going to magically come to you in 5 seconds.  Solving these kinds of algorithm problems takes hard work and a lot of effort, so don't just assume it's not going to work before you put in that kind of effort.

Bottom line.
I'm pretty sure this can be solved in $O(n\ell)$ time, where $n=size(a)$ and $\ell$ is the length of the longest repeated substring (and thus in $O(n \lg n)$ time on average, if the input string is random).  Also I believe it should be possible to solve this in $O(n)$ worst-case running time, using sufficiently advanced algorithmics machinery (augmented suffix trees).  Caveat: I haven't checked all the details carefully, so you should do that yourself.


Why is DFS not suited for shortest path problem? I am sorry for the repetition of the question. I understand that this question has already been answered before by the community, but most answers tend to focus on unweighted graphs. I want to know Can DFS we used to find the shortest path for weighted graphs? I know that Dijkstra's algorithm is used to find the shortest path for weighted graphs. But, what I want to know is what is fundamentally different in using DFS for unweighted graphs compared to Dijkstra (which is BFS + priority queue/set) and why can't we create DFS + priority queue/set implementation for shortest path problem?
Ref link: Shortest Path using DFS on weighted graphs,
Why can't DFS be used to find shortest paths in unweighted graphs?
Any help would be really appreciated.
Thanks!

TL;DR Depth First Search
I believe that Depth First search traverses the graph by recursively visiting the unseen vertices of the current vertex until they're exhausted.
for all vertices fresh = true
DFS(v):
   v.fresh = false
   for all the neighbors e of v:
      if e.fresh:
         DFS(e)

Now, weight on the other hand, is a restriction imposed on edges. Hence, the usage of Breadth First Search becomes handy. Because we traverse the graph based on layers or levels, where we're checking all the edges at a certain vertex.
Dijkstra's algorithm
Dijkstra's algorithm is pretty much tricky. You seen, the original paper does specify how prioritize to vertices based on the sum of the weight for each reached vertex.
But more importantly, it does not specify how to fulfill such a task. Indeed, the whole time complexity is dependent on the complexity of how we're prioritizing the vertices.
Prioritizing the vertices
Consider an abstract data type PriorityQueue, where it supports the following operations for an instance queue:

void add(item) to add an item to the instance queue
item get() to return and remove the current top priority from the instance queue.

Many data structures provide these elementary operations. But the bottleneck of the algorithm is to update the vertex's priority in case it was reached from a less weighted edge.
Consider an operation update(item,value) that reset the priority of the item to a certain value. There are many ways to extend PriorityQueue but all of them have different complexities.
Using Arrays
Arrays are finite contiguous chunks of memory, so we have

$O(1)$ to add() any item at the end, $O(n)$, otherwise since it involves swapping.
$O(n)$ to get() the current priority because we traverse the whole array.
$O(n)$ to update() any item for the same reason.

Using Heaps
Heaps are arrays that have a binary tree property, called the heap invariant which states the following

Every node is less than it's children (in the case of a MinHeap)

This provides $O(\log_2 n)$ to both add() and get() an item. But it costs $O(n)$ to update() any item's priority (since there is no order imposed on the children).
Using Binary Search Trees (Balanced)
It has the same costs as the heap does for both to add() and get() an item. But instead of $O(n)$ to update(), we have $O(\log_2 n)$. Since searching throughout the whole tree is logarethmic due to the following properties

Every node is greater than its left
Every node is less than or equals its right

Using Fibonacci heaps
Fibonacci heaps are an advanced data structure that is a forest of MinHeap trees.


Myhill-Nerode style characterization of CFL? Define the Nerode equivalence over a language $L \subseteq \Sigma^{*}$ as $u \sim_L v$ iff $uw \in L \Leftrightarrow vw \in L$ for every $w \in \Sigma^{*}$.

The Nerode equivalence ${\sim}_L$ has finitely many equivalence classes precisely when $L$ can be recognized by a finite-state automaton.  This is the Myhill-Nerode theorem.

  Is there a similar characterization of context-free languages?

Motivation:

The Nerode equivalence classes each correspond to a distinct state in any automaton that recognizes $L$.  Each CFL can be recognized by an NPDA, which has a finite number of states but also a potentially unbounded stack of alphabet symbols.  The stack keeps track of one possible way that a string can be parsed.  The number of equivalence classes may be infinite since the stack can store an unbounded number of symbols.

I am asking: is there always a way to clump together equivalence classes so that each clump represents one state of the PDA, with each class within the clump representing equivalent states of the stack for that PDA state?

For instance, the language of properly nested parentheses only needs states to handle pop and push, as the stack will keep track of the current nesting depth.  If such clumping can always be done, then whether the number of clumps is finite determines whether the language is context-free.

As pointed out by @sdcvvc in a comment, a form of this question was asked as https://math.stackexchange.com/questions/118362 although Yuval Filmus's answer to the related question at Example of a non-context free language that nonetheless CAN be pumped? is more relevant.

David S. Wise provides in his paper A strong pumping lemma for context-free languages a strong pumping lemma which is equivalent to being context-free. He also provides an additional equivalent condition (property 3 on page 362) which he claims could be viewed as an analog of the Myhill-Nerode theorem. As an application of the latter, he shows that $\{ a^nba^{mn} : m,n > 0 \}$ cannot be expressed as a finite intersection of context-free languages.

More information on the strong pumping lemma appears in one of my answers.


Understanding paging and internal fragmentation I am currently studing questions but stuck on this one, I hope someone can help me out to understand.

Question: Assume that we have a paged virtual memory with a page size of 4Ki byte. Assume that each process has four segments (for example: code, data, stack, extra) and that these can be of arbitrary but given size. How much will the operating system loose in internal fragmentation?

The answer is: Each segment will in average give rise to 2Ki byte of fragmentation. This will in average mean 8 Ki byte per process. If we for example have 100 processes this is a total loss of 800 Ki byte.

My question:
That 2Ki byte each segment is confusing but I think that is just a guess. Anyway, if we have 8Ki byte per process, that would not even fit in a 4Ki byte page isn't that actually a external fragmentation? Can someone explain the correct answer that is easier to understand?

If each page is 4 KB and segment has arbitrary size, then you lose from 0 to 4095 bytes on each segment, i.e. 2 KiB at average
I think it can be called internal fragmentation for pages, but external one for segments


Examples of sets $A$ and $B$ such that $A \leq_m B$ but not $B \leq_m A$ I know that such sets exist and they are called sets that are not m-complete, but I am not sure how to find them. Can someone give examples?

Let $A$ be a computable set of all even nonnegative integers, and $H$ be the language of the Halting problem. Assume also that $w_1 \in H$ and $w_2 \notin H$. Then define a mapping as following:

$$f(x) = w_1 \text{ if } x \text{ is even}, w_2 \text{ if } x \text{ is odd } $$
This function is clearly computable and $x$ is even iff $f(x) = w_1 \in H$, i.e., $A \leq_m H$. However, $H \nleq_m A$, otherwise $H$ would be computable/recursive.


Resolving NP problem with a deterministic turing machine Im studying Complexity Theory and i have a question.
What principle establishes that every NP problem can be solved by a deterministic turing machine in a exponential time ?

Transforming non-deterministic moves from a NDTM to deterministic moves in a DTM, needs exponential states to be explained. For example, a non-deterministic move can be done in $2$ different possibilities. Hence, the different combination of $n$ non-deterministic moves needs $2^n$ different deterministic computation path to be explained, as an instance.


Are all NP-complete languages downward self-reducible? Arora-Barak says that using the Cook-Levin reduction, one can show that all NP-complete problems are downward self-reducible. I know that SAT is downward self-reducible but I am not able to see how we can use this fact together with the Cook-Levin theorem to prove that all NP-complete languages are downward self-reducible.

Recall the (downward) self-reduciblity of a language.

A language $L \in \mathrm{NP}$ is self-reducible if for every verifer $V$ for $L$, there is a polynomial-time Turing machine $M$ such that for any oracle $O_{L}$ deciding $L$, and any $x \in L$, we have $V(x, M^{O_{L}}(x)) = 1$.

The book gives a proof of the self-reduciblity of SAT.
The idea for proving the self-reduciblity of all the $\mathrm{NP}$-complete language is similar.
Given an $\mathrm{NP}$-complete language $L$ and its verfer $V$, suppose that $L_{V}$ is the language of $V$.
For every string $w \in \Sigma^{*}$, we define $L_{w} = \{ z = x \Vert w : \exists u \in \Sigma^{*}, (x, w\Vert u) \in L_{V} \}$.
Clearly, $L_{w} \in \mathrm{NP}$.
Since $L \in \mathrm{NP}\text{-complete}$, there exists a Karp reduction $f$ such that
$$z \in L_{w} \Leftrightarrow f(z) \in L$$
Assume we have an oracle $O_{L}$ deciding $L$.
Now we design an algorithm that, given $x \in L$, finds $w$ with $(x, w) \in L_{V}$. Say the length of $w$ (given $x$) is $n = \mathrm{poly}(|x|)$. The algorithm proceeds as follows:
For i = 1 to n do:
    Set b[i] = 0;
    Set w = b[1]b[2]...b[i];
    If f(xw) is not in L (We run this step using our oracle for L)
        Set b[i] = 1;
    End if;
End for;
Return w;

Indeed, $w$ is a witness of $x$, i.e. $(w, x) \in L_{V}$.
And this algorithm runs in polynomial time.
Other languages in $\mathrm{NP}$ (that are not $\mathrm{NP}$-complete) may be self-reducible as well.
An example is given by graph isomorphism, a language that is not known (or believed) to be in $\mathrm{P}$ or $\mathrm{NP}$-complete.
On the other hand, it is believed that not all languages in $\mathrm{NP}$ are self-reducible.


Finding the number of squares by connected coordinates If I have a list of lists as below ,

 [[1, 2], [3, 4], [1, 5], [2, 6], [4, 8], [5, 6], [6, 7],
 [7, 8], [6, 10], [7, 11], [8, 12], [10, 11],
 [10, 14], [12, 16], [14, 15], [15, 16]]

and

[[1, 2], [2, 3], [3, 4], [1, 5], [4, 8],
     [6, 7], [5, 9], [6, 10], [7, 11], [8, 12],
     [9, 13], [10, 11], [12, 16], [13, 14], [14, 15], [15, 16]]

The above 2 lists can be visualized as in the image, where each point is represented by a list.

I know there is a graph traversal where every visited node can be tracked as we traverse through the graph. But in this case, there is no direction mentioned.

How should I approach this problem? I am also interested in hints.

Let $b(p, \ell)$ be a boolean value denoting whether the horizontal segment whose left endpoint is $p$ and whose length is $\ell$ exists. Then the values of $b(p,\ell)$ for all possible $p$ and $\ell$ can be computed in $O(n^3)$ recursively using the fact that

  $b(p,\ell)$ is true iff $b(p,\ell-1)$ is true and $b(p+\ell-1,1)$ is true where $p+\ell-1$ denotes the point on the right side of $p$ and the distance between them is $\ell-1$.

Here $n$ is the length of the grid.

Similarly, you can do the same thing for vertical segments.

Now you can check each possible square by checking its four edge segments. The whole running time is $O(n^3)$.

As j_random_hacker said in the comment,

  You can drop the space usage to $O(n^2)$ by instead calculating the length $w(p)$ of the longest horizontal segment having left endpoint $p$ for all $p$. Then $b(p,\ell)=(w(p)\ge\ell)$.


How do I solve interdependent recurrence relations? I have three functions with values given as

$$\begin{align*}
    P(0) &= 0 \quad &
    P(i+1) &= 5M(i)\\
    M(0) &= 1  \quad &
    M(i+1) &= R(i) + 2P(i)\\
    R(0) &= 3  \quad &
    R(i+1) &= R(i) + 3P(i)\,.
\end{align*}$$

If it was a linear recurrence with one function I could solve it using matrices. But here I cannot bring it to a single relationship. Each one is interrelated with the others.

How do I approach this problem?

Eliminate one recurrence at a time, by plugging in.

For instance, you can use the equation $P(i)=5 M(i-1)$ to eliminate every instance of $P(\cdot)$ in each of the other recurrences.  Plugging in, we get

$$M(i) = R(i-1) + 10 M(i-2)$$
$$R(i) = R(i-1) + 15 M(i-2).$$

Now you have two inter-related recurrence relations, instead of three; you've eliminated one.

Do it one more time, say to remove each instance of $M(\cdot)$.  You get something like

$$R(i) = R(i-1) + 15 R(i-3) + 150 M(i-4).$$

Do it again, to remove the $M(\cdot)$:

$$R(i) = R(i-1) + 15 R(i-3) + 150 R(i-5) + 1500 M(i-7).$$

Keep doing this, and you'll get a summation, say something like:

$$R(i) = R(i-1) + 15 R(i-3) + 150 R(i-5) + \cdots + 15 \times 10^{(i-3)/2} \times M(0)$$

(if $i$ is odd.)

Now you're down to a single recurrence relation.  Solve it.  Then, use the equations above to derive the solutions for $P(\cdot)$ and $M(\cdot)$.


Can Circuit Value Problem or HORN-SAT be reduced to PATH problem? PATH = {(X,R,S,T) | exists an x in S that is admissible}
Where R is a relation of X x X x X, S is a unary relation of X and T is a unary relation of X aswell.
An x element of X is admissible if it is in T or if there is two elements y z both admissibles, where (x,y,z) is in R.

So, is there any logspace reduction from CVP or HORN-SAT to this problem, so I can prove that PATH is P-Complete?

Hint: Reduce from the monotone circuit value problem. Let $X$ be the set of all inputs and internal gates in the circuit. Choose $T$ and $R$ so that an element is admissible if the corresponding input or gate is true (each AND gate will require one triple in $R$, each OR gate will require two). Choose $S$ to be the indicator of the output gate to complete the proof.


Completeness problem of TM $L = \{ \langle M \rangle \mid L(M) = \Sigma^∗ \}$

Is above problem R.E ?

I found an explanation in one of the websites and I have doubt in few lines of paragraph.

The explanation was

Now, given a halting problem $(\langle H \rangle, w)$, we proceed as follows: We make a new TM say $A$, which on input $x$, just simulates $H$ on $w$ for $|x|$ steps. If $H$ halts on $w$, $A$ goes to reject state. Otherwise it accepts. So, $L(A)=\Sigma^*$ if $H$ does not halt on $w$ and $L(A) =$ a finite set if $H$ halts on $w$. So we can reduce non halting problem to this problem. Hence given language is non R.E

Can someone please explain me how is $L(A) = \Sigma^∗$ if $H$ does not halt on $w$ ? It says if $A$ doesn't halt within $|x|$ steps then $L(A)$ is infinite. How can we say that ? What it TM $A$ halts on $|x+1|$ th  step? Even then it will be finite but this explanation considers it as infinite.

I understand how is it finite set if $H$ halts on w but I am not able to understand the non halting part.

Assume $H$ does not halt on $w$. To prove $L(A) = \Sigma^∗$ we need to show that $A$ accepts every $x$. Indeed, whatever $x$ is, we simulate the execution of $H$ on $w$ for only $|x|$ steps (a finite, known amount of steps). I.e., we do not simply run that program on its own, we keep an "alarm clock" counting the steps $H$ as it is running, and as soon as it reaches $|x|$ the alarm rings and we stop the simulation. In this way, no matter what $H$ does on $w$, the simulation will always terminate: either because $H$ halts before $|x|$ steps, or because the alarm rings and we abort the simulation.

Now, since $H$ does not halt on $w$ by hypothesis, $H$ will always make the alarm ring. In such case, $A$ accepts $x$ by construction, hence $A$ indeed accepts all inputs $x$.

For the other direction, assume that instead $H$ does halt on $w$. Let's write $k$ for the number of steps that make $H$ halt on $w$. We now need to prove that $L(A) \neq \Sigma^∗$. Take $x = 1^k$: we prove that $A$ rejects it. By definition, $A$ simulates $H$ on $w$ for $|x|=k$ steps, and that's just enough time to make $H$ halt. So, by construction $A$ rejects.


Building maze to maximize shortest path, may be given waypoints and teleports How would you go about solving this problem?  Is it something that could be expected to be computed/solved within a couple of hours of given a starting area with (32) threads on 3.0GHz Xeon cores?  (Assuming sizes between 8x8 and 30x30.  Using C or C++ if that matters)  Or, is this so complex that it would take way longer?

There is an area, where an automated traveler follows a shortest path algorithm at all times.  Playing the builder, find the way to maximize the number of points the traveler must visit.

The area is typically between 8x8 and 30x30, given in the form:

.F......
......a.
........
........
.....1X.
........
.A......
........
..O.....
.X......
..X.....
..X.....

Where there is:

Always a single O, the starting point
Always a single F, the ending point
Always many ., empty points that can either be traveled or built on
Sometimes X, points designating they are blocked for traveling or building
Sometimes pairs of letters (i.e. A and a, but never F, O, or X), indicating a teleport when visiting the uppercase letter for the first time to the lowercase letter
Sometimes numbers (i.e. 1), designating waypoints

The automated traveler follows a shortest path algorithm at all times.  It must begin at the starting point, if there are waypoints pass over them in order, and finish at the ending point.  The traveler may pass over the ending point or subsequent waypoints early, but the game doesn't end and the waypoints aren't counted as visited, until they are the active next destination.  If there are any, the traveler must not pay attention to any teleport spots; they must take the shortest path between points as if they cannot see these teleport spots.  The exception to this rule is if there are multiple paths with the shortest length between last source to next destination and one of them travels through an active teleport spot, the path with the teleport must be taken.  (Otherwise, can choose any of the multiple shortest paths.)  If the shortest path forces them into a teleport spot, they teleport the first time they visit the uppercase letter to the corresponding lowercase letter.  The traveler can move horizontally and vertically.  The traveler can move diagonally between two points if the 2x2 square containing both points is clear of blocking points.

So, if the traveler needs to travel from the lower left to upper right point, here they can move diagonally and only count 2 moves:

..
..

But here, again traveling from the lower left to upper right point, they cannot move diagonally and must count 3 moves:

X.
..

The game always starts with an open path to reach all required destinations.

You, the builder, get to take all of your actions first, and none once you decide you are complete and allow the traveler to begin.  The builder can place additional X points that block travel on them, but they cannot make it impossible to reach any of the required destinations.  The builder cannot place any other points, such as more teleports or waypoints.  The builder cannot remove anything given to them already in the area (other than replace empty points.)  Strategy may include blocking points to force: otherwise out of the way travel; backtracking; and traveling between teleports.  Optimal strategy might include trying to connect the starting, ending, and destination teleport spots in short paths, and forcing a long backtracking path to waypoints.

This is to come up with possible strategies for a tower defense game.  Certain aspects of the game, such as multiple waves, limitations on resources, and attack towers, are ignored to simplify and just focus on the maze-like aspect of the game.

Just a note: even the simpler version without waypoints and teleports is NP-hard:
Start with a maze in which the dots mimic the edges of a grid graph $G$ of max degree 3,  and $X$s are placed "around" them (the dots are "corridors"). Put the $O$ in a corner and the $F$ near it with a dot in the middle.
Maximizing the shortest path (adding more Xs) is equivalent to finding an Hamiltonian path in the original graph $G$ which is NP-complete (each new $X$ must block a "corridor", i.e. it removes an edge of $G$).


Is there a solution set for Knuth's The Art of Computer Programming series? Is there a solution set for the books in The Art of Computer Programming series written by Donald Knuth?

I've found solutions for Concrete Mathematics using Google, but not the above series.

The books contain worked solutions to some exercises and hints to some others. Others are open questions: this is indicated by their difficulty rating, and you shouldn't expect to find worked solutions to them except maybe, for a few, as papers in journals.


Radix sort slower than Quick sort? I would like to demonstrate that sometime radix-sort is better than quick-sort. In this example I am using the program below:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <time.h>
#include <math.h>

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

void bin_radix_sort(int *a, const long long size, int digits) {
    assert(digits % 2 == 0);

    long long count[2];
    int *b = malloc(size * sizeof(int));
    int exp = 0;

    while(digits--) {
        // Count elements
        count[0] = count[1] = 0;
        for (int i = 0; i < size; i++)
            count[(a[i] >> exp) & 0x01]++;

        // Cumulative sum
        count[1] += count[0];

        // Build output array
        for (int i = size - 1; i >= 0; i--)
            b[--count[(a[i] >> exp) & 0x01]] = a[i];

        exp++;
        int *p = a; a = b; b = p;
    };

    free(b);
}

struct timespec start;

void tic() {
    timespec_get(&start, TIME_UTC);
}

double toc() {
    struct timespec stop;
    timespec_get(&stop, TIME_UTC);
    return stop.tv_sec - start.tv_sec + (
        stop.tv_nsec - start.tv_nsec
    ) * 1e-9;
}

int main(void)
{
    const long long n = 1024 * 1024 * 50;
    printf("Init memory (%lld MB)...\n", n / 1024 / 1024 * sizeof(int));

    int *data = calloc(n, sizeof(int));

    printf("Sorting n = %lld data elements...\n", n);

    long long O;
    tic();
    O = n * log(n);
    qsort(data, n, sizeof(data[0]), cmpfunc);
    printf("%lld %lf s\n", O, toc());

    int d = 6;
    tic();
    O = d * (n + 2);
    bin_radix_sort(data, n, d);
    printf("%lld %lf s\n", O, toc());
}

It performs as follow:

$ gcc bench.c -lm
$ ./a.out
Init memory (200 MB)...
Sorting n = 52428800 data elements...
931920169 1.858300 s
314572812 1.541998 s

I know that Quick Sort will perform in O(n log n) while Radix Sort will be in O(d (n + r)) ~= O(6 * n). For n = 52428800, log(n) = 17. I am then expecting Radix Sort to be 3 times faster than Quick Sort...

This is not what I observe.

What am I missing?

qsort is not Quicksort. qsort is whatever the implementor of the standard library decided.
Sorting 50 million identical values is highly unrepresentative. There are qsort implementations that will sort 50 million identical, or 50 million sorted or reverse sorted elements in linear time.
Radix sort of 50 million numbers with six digits is obviously nonsense. Six digits means you expect only 64 different values and therefore would use counting sort. With less than 26 digits it doesn't make sense.
Your radix sort does an awful lot of copying, and worse, uncached copying.
Your radix sort doesn't produce a correctly sorted result if digits is an odd number.
Your qsort call doesn't produce a correctly sorted result if the array contains very large and very small numbers.


Why $2R\sigma\sqrt{T+logT+1}=\tilde{{O}}(\sigma\sqrt{T})$? On page 17 on the paper Online Learning with Predictable Sequences, we find a regret of an algorithm equal to

$$
\text{Reg}_T=\frac{R^2}{\eta}+\frac{\eta}{2}\sigma^2(T+logT+1)
$$
where $T$ is the entire time, $\eta$ is learning rate, $R$ is constant, and $\sigma^2$ is the variance of data. The above using arithmetic mean-geometric mean inequality can be lower bounded by

$$
\sqrt{2}R\sigma\sqrt{T+logT+1}\leq \frac{R^2}{\eta}+\frac{\eta}{2}\sigma^2(T+logT+1)
$$

why the left hand side is $\tilde{{O}}(\sigma\sqrt{T})$?

According to $\tilde{{O}}$ vs $O$, $\tilde{{O}}$ ignores logarithmic factors that means when $f(n) \in \tilde{O}(g(n))$ there exist a $k$ such that $f(n) \in O(g(n)\log^k g(n))$, now I have $f(T)=\sqrt{2}R\sigma\sqrt{T+logT+1}$, why I can write it $O(\sigma\sqrt{T}log^kT)=\tilde{O}(\sigma\sqrt{T})$? and what is my $k$?

What is $\tilde O$? There are two different definitions.

According to exercise 3.5 of Introduction to Algorightms by Corman et al., $\tilde O$ can mean $O$ with logarithmic factors ignored: $$\tilde O(g(n))= \{f(n): \text{there exist nonnegative constant } k \\ \text{ and positive constants } c, k, \text{ and }n_0
\text{ such that }\\ 0\le f(n)\le cg(n)(\log n)^k\text{ for all }n\ge n_0\}$$
According to Wikipedia entry, $f(n) = \tilde O(g(n))$ is shorthand for $f(n) = O(g(n)\left(\log g(n)\right)^k)$ for some $k$.

For any value $x>0$, $x^0=1$. If we take $k=0$ simply, we can see that for either definition,
$$f(T)=\sqrt{2}R\sigma\sqrt{T+\log T+1}=O(\sigma \sqrt{T}) =O(\sigma \sqrt{T}\,1)=\tilde{O}(\sigma\sqrt{T})$$

Here is the explanation for the second equality in the above equation.

$\log T=o(T) \Rightarrow
T+\log T+1=\Theta(T) \Rightarrow \sqrt{T+\log T+1}=\Theta(\sqrt T)$

W can also proceed more rigorously, using L'Hôpital's rule once.

$$\lim_{T\to\infty}\frac{\sqrt{T+\log T+1}}{\sqrt T} = \sqrt{\lim_{T\to\infty}\frac{T+\log T+1}{T}} = \sqrt{\lim_{T\to\infty}\frac{1+\frac1T}{1}}=1$$


Implement queue with a linked list; why would it be bad to insert at the head and remove at the tail? In my textbook, Data Structures and Algorithms in Java, the author says when implementing a queue using a linked list you choose the front of the queue to be at the head of the list, and the rear of the queue to be at the tail of the list. In this way, you remove from the head and insert at the tail.

The author then asks cryptically, "Why would it be bad to insert at the head and remove at the tail?" without providing an answer.

I can't see what the difference really is. In effect, "Head" and "Tail" are just arbitrary names we define. What would be so bad if to enqueue() we add a head and create a reference to the old head, and to dequeue() we take from the tail and move the tail over?

What is the answer to the author's question?

In a single linked list, every element has a pointer to the next element.  If you have an additional pointer to the tail element, it takes you a constant number og operations to add to the list at the tail:  get the tail pointer, add an element after the tail, put this new element as new tail.  Removing from the head also takes a constant number of operations:  make you new item new, head, point to old head.

However, removing from the tail demands a pointer to the predecessor to the current tail.  This takes you as many operations as there are elements, namely linearly many.

Another solution is to use a doubly linked list, then you can choose what you will, but it uses twice as much memory.


what is definition of algorithm in computer science? I have problems in writing algorithms before writing code for a particular program.

An algorithm is just like a recipe.

But when it comes to programming complex structures (like nested conditional statements and loops) in my code, I am not able to write one, and often get confused easily. How can I get over this thing?

An algorithm is, alas, an informal concept, which can not have a precise mathematical definition. One can still attempt at an informal definition, and argue that it conveys the right (informal) intuition.

Because of its informal nature, sometimes it's also easy to argue against a given definition, attacking the definition wording. For instance, I've read more than once that an algorithm is a "sequence of steps" which makes my eyebrows raise, since it suggests that any algorithm will always halt within those number of steps, no matter how large the input is. Once, I had a conversation with a physicist where I couldn't follow their argument, and it turned out they identified "halting algorithm" with "constant-time algorithm" since they believed the number of steps were fixed by the algorithm (hence independent from the input).

If I had to define an algorithm, very informally, I would say that it is an informal but unambiguous description that, to each input, it associates a finite sequence of elementary computation steps which can be used to obtain the desired output.

This is far from being perfect. For instance, what is a "elementary computation step"? Further, it does not express that the mapping form input to the sequence of steps must be effective -- otherwise we could associate to all halting TM encodings the steps print 1, and print 0 otherwise.

To fix these issues, I believe that we also need to convey the notion of computability in some way, which is however too much for that definition. One could refer to a specific formalism or programming language, but I'd want that definition to be computation-model-agnostic.

Indeed, one could say that an algorithm is an informal description of, say, a Java program, which is not as detailed as real code, yet is enough detailed that it could be turned into actual Java without needing to do further research, but only doing "coding". I would regard such a definition as quite inelegant, though.


DFA memory bandwidth When we talk about DFA, we say that each new character from the input requires one memory access. What does that mean?

This is what I think about this. Please tell me is this right?
For example, I have a transition table stored for a certain regular expression in memory (RAM). Now, for each input character the CPU will fetch the whole transition table to find out the next state. In this way, we have just one memory access?

This is not how memory access works. For each character read, you need (1) to read the character, (2) to access the transition table at the appropriate state and character. In your case it seems that we're not counting (1), and so (2) is the single memory access. The speed of this access depends on how big the transition table is. If it is small enough to fit in cache (which is usually the case), then after several transitions, the entire transition table would be in cache and so would be accessed quickly. If it is too big, you will have cache misses and everything would be slower. But in both cases only the particular cell is accessed! However, data is stored in caches in chunks knows as cache lines, which could explain your confusion (cache lines are not big enough to hold the entire transition table). Note also that there are several levels of cache.


Propositional truncation of excluded middle It is clear to me that it should be impossible to prove :

exclMidl = isProp A → ((A) ⊎ (¬ A))

Because it would give deciding oracle for every Proposition.

My question is about the following Types:

exclMidl' = isProp A → ∥ ((A) ⊎ (¬ A)) ∥

or

exclMidl'' = isProp A → ∥ ((A ≡ Unit) ⊎ (A ≡ Empty)) ∥

Are they provable in cubical Agda?
What HoTT can say about them?

Those types would only state that propositions are either True or False but would hide information about actual Truthness of A, preventing us from constructing universal oracle, but allowing, for example, to do a proof for both cases even for undecidable propositions.

Is my intuition about such types correct?

The only way to prove ∥ X ∥ is to prove X (unless you admit some other axiom).
So, assuming P is a proposition, there is no way to prove ∥ ((A) ⊎ (¬ A)) ∥ if you cannot prove ((A) ⊎ (¬ A)).

It is not a correct intuition that undecidable propositions are either true or false, just we do not know about it.

A formal system S with an undecidable proposition P can always be extended either in S'=(S,p:P), or S''=(S,p:¬ P) where p is taken as a new axiom. Both S' and S'' are then consistent formal systems, provided S is.
If P were already true or false in S, then either S' or S'' would be inconsistent.

A formal system is meant to be interpreted, and can usually be interpreted in different ways. Undecidable propositions in a formal system are propositions that can be true in some interpretations, and false in other interpretations.
A proposition is said to be true (resp. false) within a formal system when it is true (resp. false) in all possible interpretations. So there are lots of propositions that are neither true nor false within the formal system.

The confusion comes from the different meanings for 'true': the truth within the formal system usually does not match exactly the truth in the interpretation (or intuition) that you have in mind when you are working with the formal system...


Where are M-Trees applied in practice? My similarity search seminar topic are M-trees. I would like to give some examples about where they are practically applied, but I can't find anything googling.

Does someone know if M-trees are still used and what for? I am interested in answers regarding both practice and applied research.

M-trees appear in this survey of image retrieval techniques (emphasis added):

  In Berretti et al. [2000], curves are represented by a set of
  segments, or tokens, whose feature representations (curvature and
  orientation) are arranged into a metric tree [Ciaccia et al. 1997] for
  efficient shape matching and shape-based image retrieval.


Processing weighted points of interest. Is there a name for this task/algorithm? Is there a name for the following problem? Is there a measure of quality of a given solution? How can we even define what a proper solution is?

Context: I want to detect long lines (most lines over 1000 pixel long) in an image. It is known that most of the lines have similar alignment. To detect those I use the  Standard Hough Transform. To detect long lines I need a high angle resolution of the accumulator. Now the idea is not to use an equidistant partition of the angle axis but to create a new partition based on the number of votes for each angle.

The Problem: Given weights
$$a_0, \ldots, a_{n-1} \in [0,1] \text{ with } \sum_{k=0}^{n-1}a_k = 1$$
which correspond to the equidistant partition of the interval $[0,1[$
$$0, \frac{1}{n}, \frac{2}{n}, ..., \frac{n-1}{n},$$ return a new partition with less or equal elements which is "finer" around points with larger weights and "coarser" around points with smaller weights. E.g. given the weights $(0.75, 0, 0, 0.25)$ on the partition $(0, 0.25, 0.5, 0.75)$ the result should be a new partition like $(-0.083, 0.0, 0.083, 0.75)$. As $0$ seems to be a point of interest there are three points near it which reflects that.

My solution: The idea is to treat the vector of weights as a density function and to use the  quantile function of its cumulative distribution function (cdf).

Example: Given the weights $(0, 0.5, 0, 0.5, 0)$ we construct the density function:

Then the cdf looks like this:

Now we shift the given equidistant partition by $+1/(2n) = 1/10$ and put its values into the quantile function, i.e. we put those values on the $y$-axis and search for corresponding $x$-values of the cdf as marked by the blue lines. $y=0.5$ is omitted since it "cannot decide" which peak it contributes to. The so obtained $x$-values are shifted by $-1/(2n) = -1/10$ and returned as the new partition. The returned partition in this example is $(0.14, 0.22, 0.58, 0.66)$.

Here is a C++ function which performes those tasks, where the vector "weights" represents the input weights and "sample" contains the new partition after execution:

#include <vector>
using std::vector;

void weighted_partition(vector<double>& sample, const vector<double>& weights) {
    const int n = (int)weights.size();
    double y;
    double F = 0.0;
    int i = 0;

    for (int j = 1; j < 2*n; j += 2) {
        y = (double)j/(2*n);

        while (F < y) {
            F += weights[i];
            ++i;
        }

        if (F == y) {
            continue;
        }

        --i;
        F -= weights[i];

        sample.push_back((y - F + weights[i] * i) / (weights[i] * n) - 1.0/(2.0 * n));
    }
}

This algorithm seems to return solutions which are intuitively correct but how can you define "correct"?

Solution to your algorithm problem

There's a simple solution to your algorithmic problem.  Treat the $a_0,a_1,\dots,a_{k-1}$ as a probability distribution.  Apply kernel smoothing to turn this into a smooth probability distribution.  At this point, you have a probability density function (pdf).  Now compute a cumulative density function (cdf), and find the $n+1$ quartiles of the cdf.  These endpoints of your new bins.

This is "optimal", in the sense that given all of the information available to you, it gives the optimal bin-sizing for a particular distribution.  We could prove this by proving that for a particular pdf, this definition of bins ensures that each bin has exactly $1/n$ probability mass falling within it.

Other approaches to your computer vision task

The Hough transform might not be optimal.  There are other approaches you could also try.  For instance, there are algorithms for detecting lines that are approximately horizontal.  So, the following approach might be better:

Find one long line and approximately find its angle.
Rotate the image so that it is approximately horizontal (since the lines are all approximately parallel, that means all the lines will now be approximately horizontal).
Find all long, approximately-horizontal lines.

The problem of finding long, approximately-horizontal lines has been studied in the literature on image processing and deskewing scanned documents.  Or, if you want a free tool, take a look at existing tools, e.g., Leptonica, pagetools, ImageMagick (convert -deskew), and others.

Another standard approach is to apply the Hough transform twice:

First use the Hough transform to get a rough estimate of the angle.  For instance, you might sweep over some range of possible angles, sensitive to 1 degree or 0.1 degree increments.
Then, use a second Hough transform to get a rough estimate of the angle.  Now you have a much narrower range of possible angles (1 degree or 0.1 degree wide); do the Hough transform over this narrower range, sensitive to 0.01 degree increments (say).

This is more efficient then doing a single Hough transform sensitive to 0.01 degree increments.


Running Dijkstra on particular graph with negative weight After running Dijkstra on this graph from S, which shortest paths will be incorrect?

This graph has a negative weight, so which shortest paths will be incorrect? after my first attempt I got that Y and Z have wrong shortest paths, but that's not true. Can anyone explain why?

The shortest path tree of Dijkstra will set root as $S$ then it first selects the $Y$ with weight 8. Then it will look at the shortest distance of all the neighbor's of the tree. There will be two candidates $X$ and $Z$. It will choose $X$ since the distance is 10. Then finally, it will choose $Z$ with distance 11.

The Dijkstra's, as stated, cannot work correctly on graphs with negative weights.

The problem is that it is a greedy algorithm and once it finds the shortest path for a node it is not re-evaluating for any other possibilities may occur in the future. This is not possible if the graph has not negative weights.


Decision Problem vs. Optimization Problem Is the following statement correct?

If a decision problem is NP-complete, the corresponding optimization problem can not be solved in polynomial time.

We don't know that $\mathrm{P}\neq\mathrm{NP}$ so we don't know that the decision problem itself can't be solved in polynomial time!

But, under the assumption that $\mathrm{P}\neq\mathrm{NP}$, the optimization version of an $\mathrm{NP}$-complete problem can't be solved in polynomial time. If we could, for example, compute the shortest travelling salesman tour in polynomial time, we could certainly tell in polynomial time whether there's a tour of length at most $d$


Can I use breadth-first search for topological sorting? Can I use breadth-first search for topologicallly sort vertices and finding strongly connected components in a graph?

If yes, how can I do that? If not, why?

I tried with a simple acyclic graph of 3 vertices, gave the start and finish time as we do in DFS and then sorted them in non-increasing order. There was a conflict. The result was topologically sorted.

I find in all books that we use depth first search here. Is there any way that I can modify BFS so that I can topologically sort vertices?

BFS for topological sort seems possible to me.

All we need to add to the baseline BFS is a stack.  The idea is that in BFS, nodes are traversed by levels relative to the starting node.  When we get to the level where none of the nodes have un-visited children, we know that these nodes will be the first to put in topological ordering. Then we look at their immediate predecessors, and we know that they will be second to put in topological ordering. And we look at a level above, and so on.

Here is a pseudo-code snippet that does this on a subgraph reachable from the start_node (it'd be straightforward to extend it to the entire graph):

# Returns a list of nodes in topological-ordering.
def top_bfs(start_node):
    queue = [start_node]
    stack = []
    while not queue.empty():
        node = queue.dequeue()
        if not node.visited:
            node.visited = True
            stack.push(node)
            for c in node.children:
                queue.enqueue(c)
        else:
            # node's ordering should be lowered because previously visited.
            adjustedNode = stack.remove(node)
            stack.push(adjustedNode)

    stack.reverse()
    return stack


Is L closed under linear-time reductions? L is as usual the complexity class DSPACE($\log n$), of languages decidable using a deterministic Turing machine using logarithmic workspace.

  Is L closed under linear-time reductions?

It is possible that for some pair of languages Q and R, every linear-time reduction from Q to R requires more than logarithmic space.
Up to linear space could be used while still remaining within linear time.
So it isn't immediately obvious to me that L must be closed under linear-time reductions.

On the other hand, it is not clear what a counterexample would look like.
One wants a language Q that can be linear-time many-one reduced to a language in L (for instance, to undirected graph st-connectivity), yet so that Q is not in L.

L is closed under linear-time reductions if and only if L = P.

Proof:

If L is closed under linear-time many-one reductions then:

Since L has non-trivial problems, all problems that are solvable linear time are in L.

Let (x) be the modification of the most basic P-complete problem to ask about "the first sqrt(T) steps" rather than "the first T steps". Since unary-to-binary conversion can be done in linear time and [square-roots can be computed and TMs can be simulated in quasi-linear time], (x) can be solved in linear time. Since L has non-trivial problems, there is a linear-time many-one reduction from (x) to a problem in L. By this paragraph's assumption, that means (x) is in L.  Since L can square unary inputs, there is a logspace reduction from the most basic P-complete problem to (x). Thus (x) is P-complete. Since (x) is in L, that means  P ⊆ L .

If L is closed under linear-time many-one reductions then then P ⊆ L. With no assumptions, L ⊆ P.  Therefore, if L is closed under linear-time many-one reductions then then L = P. Since P can perform linear-time Turing reductions, P is closed under linear-time Turing reductions. Therefore, if L = P  then L is closed under linear-time Turing reductions.  QED


Infer number of comets, based upon observations of their periodic visits to Earth Can we algorithmically infer the number of comets that orbit the Earth, based upon periodic observations of them, if we cannot tell the comets apart?  In more detail:
The problem

There is an unknown, fixed number of comets, numComets that pass by
Earth and are visible from the ground.

Each comet takes a fixed number of years to orbit Earth.

Based only on this knowledge and the dates recorded that a comet was
sighted in the night sky, determine numComets, AND determine
the orbital period of each comet. You can use an unlimited amount of
observation data (time), but the solution in the shortest amount of
time is preferable.

Assumptions you can make

All comets look identical from the ground; there is no way to
visually identify them.

No other object will be mistaken for a comet, and all comets will be
seen.

No comet takes more than 100 years to orbit Earth, and no new comets
will be introduced.

As current answers have pointed out, the problem as it lay now is unsolvable. Would a solution be possible if numComets is known? (Even roughly get the right answer?) What modifications to the problem would have to be made otherwise, to still encasulate the spirit of the problem, and make it solvable? (or is it dead with no hope of solving accurately?)
Further assumption
All comets start at a different point in their orbit. I.e. They do not all start their orbit at the same place like racehorses coming out of a gate.
Clarification
Comets are only recorded once per year. So there is no difference between a comet that passes at the beginning of a year and at the end. The problem could just as easily have been worded as days.

Based on the restriction you gave, that you cannot identify one comet from another, there is no difinative method of calculation. Here is a proposed situation, There are 2 comets following the same trajectory, they each orbit at exactly ten year orbit durations, so each one is seen every ten years, they are however exactly 5 years apart in their orbits. From the ground if we cannot differentiate between these two comets we only see a comet appear overhead regularly every 5 years, there is no way to tell if this is one comet appearing ever 5 years, or two comets appearing every ten years, but 5 years apart. From this it is impossible to deterministically say how many comets there are, so no algorithm can give you numComets with the assumptions that you have specified.


Solving recurrence $T_k(n) = T_k\left(\left \lfloor \frac{n}{2} \right \rfloor\right) + T_k\left(\left \lceil \frac{n}{2} \right \rceil\right)$ I am currently solving a problem that I have reduced to computing the following function efficiently.

$$T_k(n) =  T_k\left(\left \lfloor \frac{n}{2} \right \rfloor\right) + T_k\left(\left \lceil \frac{n}{2} \right \rceil\right)$$

The base cases are $\forall n < k: T_k(n) = 0$ and  $\forall k \leq n < 2k: T_k(n) = 1$ Note: $n$ and $k$ are non-negative integers.

I need to compute this function for multiple values of $k$ and $n$.
I can compute this function in $\theta(n)$ by a simple recursive function using just the definition and speed up the computation by using memoization. However, this isn't fast enough and I was wondering if there is a closed form expression for it and can be computed in $o(n)$.

I have no idea how to solve this recurrence.

Observe that $T_k(2^n k) = 2^n$. Furthermore, it is easy to see that either $T_k(\alpha) = T_k(\alpha-1)$ or $T_k(\alpha) = 1+T_k(\alpha-1)$. Using the previous two results, it can also be shown that $T_k(2^n k - 2^{n-1}) = T_k(2^{n-1} k)$.

Now, consider
$$\delta_k(n) = T_k(2^n k - 2^{n-1} + 1) - T_k(2^n k - 2^{n-1} )$$

It should be easy to prove by induction that for all $k, n$ it holds that $\delta_k(n) = 1$. This should be sufficient to uniquely determine the value of $T_k(n)$ for all $n$.


Proving that language is regular or not How to prove that the language over the alphabet $\{0, 1, +, =\}$ is regular or not:

$\{a+b=c:a,b,c \text{ are integers in binary for which } a \text{ plus } b\text{ equals } c\}$

I started with the pumping lemma:

  |$y$| ≥ 1
  |$xy$| ≤ $p$
  for all $i$ ≥ 0, $xy^iz$ ∈ $L$

But I don't know what to do next. How can split "$a+b=c$" string to start with the pumping lemma? Or I should apply another method?

The easiest way is to take the intersection of your language with $1^*+0=1^*$, which is
$$ \{ 1^n+0=1^n : n \geq 0 \}. $$
A similar option is to intersect with $1^*+1=10^*$, which gives
$$ \{ 1^n+1 = 10^n : n \geq 0 \}. $$
I'll let you finish the argument.


How to count number of 1s of the first k positions in a bitset (bitmap)? Input: Given a bitset $b$, which is is an array of 0s and 1s, of length $L$, and a positive integer $k$.

Output: the total number of 1s in the first $k$ position of $b$.

Obviously it can be done in $O(k)$, is there any more efficient way in C++ such as $O(\frac{k}{W})$, where $W$ is the word size of the machine? Note that the popcount instruction only works when $k=L$, but $k$ is varying.

Popcount is going to be your best option here. As j_random_hacker mentions in a comment, popcount on a single word can be done in $O(\log W)$ time if implemented by hand, or $O(1)$ if the machine provides a dedicated opcode for it (which should take a constant number of clock cycles—but then again, $W$ should also be a constant for any given machine).

(Note: if $b$ is longer than a single word, then you can just use popcount directly on the first $\lfloor \frac{k}{W} \rfloor$ words, and ignore the last however many others, in $O(\frac{k}{W})$. It's only the one word in the middle that you need any fancy algorithm for. So I'm going to be solving the special case where $k < W$. If this isn't the case, which it normally won't be, then replace $k$ with $k \bmod W$.)

The part that depends on $k$ is getting rid of the $W-k$ unneeded bits. One way to do this is masking: generate a mask of $k$ ones, then AND your value with it. (You can generate such a mask by starting with 1, left-shifting $k$ times, then subtracting 1 and taking the complement. Or you can start with only the highest bit set and arithmetic-right-shift $k$ times.)

Another way is to just push the unneeded bits off the end of the word: logical-right-shift your number $W-k$ times and the unwanted bits will be gone.

Which of these is most efficient depends on the specifics of your machine. If it can do bitwise operations and variable shifts in a constant number of clock cycles, then the whole thing is still $O(1)$. If it can't do variable shifts, then it takes $O(k)$; if it can't do constant-time bitwise operations, then there's no way to get better than $O(W)$.


Polysize bounded depth circuit for modified MAJORITY problem I am trying to show the existence of a polynomial size, bounded depth monotone circuit on the inputs $(x_1,\ldots, x_n)$ that gives $1$ if $\sum x_i \geq n/2 + n/\log n$ and $0$ if $\sum x_i \leq n/2 - n/\log n$. This is a modified form of the MAJORITY problem.

I want to use the probabilistic method but I cant seem to get it to work. I found a way to get a circuit that was not of bounded depth, iterate a bunch of random layers of gates that compute the MAJORITY function for three randomly selected inputs. This will, for $\mathcal{O}(\log n)$ depth, give the right result with overwhelming probability, so one such circuit is always correct.

I think I should have layers of alternating AND and OR gates, but since the $n/\log n$ factor is so small, even when we should get a $1$ for instance, the probability that a random input is a $1$ is only $1/2 + 1/\log n$, not really so high. I cannot seem to amplify this enough to take care of both cases.

Any help?

This task is known as approximate counting or approximate majority. The first to construct such a circuit was Ajtai in his celebrated 1983 paper $\Sigma_1^1$-formulae on finite structures, which also proves the first switching lemma. You can check out Section 3 for the construction. For a more modern account, see Section 2 of Viola's Randomness buys depth for approximate counting.


What purpose was the Von Neumann machine intended for? And what hardware limitations existed when von Neumann invented it? Its namesake invented the Von Neumann architecture (VNA) in a specific computing environment and a specific context. In light of those two:

What kind of limitations was the VNA designed to work with?
What features in the VNA reflect that?
What kind of purpose did Von Neumann intend for the VNA?
How did the design of the VNA accomplish his purpose?

The von Neumann architecture was built for sequential computing. It was groundbreaking because it combined the instructions in memory along with the data for the instructions in the same space. Before this, programming required rewiring because each machine was built with a specific purpose in mind.

The essential idea is abstraction on some level. The people who design the actual machines don't need to concern themselves with what software will be written for the machine. Rather, they make a few basic commands extremely efficient. The software teams then efficiently use these commands, allowing a generalizable/abstractable computer model.


Finding maximal and average number of time slots in an Adaptive tree walk protocol Tried to research here and on other sites with no luck regarding finding the maximal and average number of time slots in an Adaptive tree walk protocol. i'll explain what i mean here:

In a simple(provided an image for illustration at the end of the post) Adaptive tree walk protocol, Divided by time slots where a station can only transmit at the beginning of each time slot.

If for instance stations C and A want to broadcast  in time t=0 with probability p(for simplicity) (None of the other stations want to transmit at all), Is it possible to know the maximal or average number of time slots that will pass until(including) the slot in which there will be a successful broadcast?

Simple network diagram i am asking about:

Note: for simplicity, in this question, no other station except C and A want to broadcast at all

It is clear that you cannot know the maximum if $p \neq 1$, because there is always some chance, no matter how small, that neither station will transmit after any $n$ attempts.

However, if $p=1$ then the answer is always 3 (both average and maximum): first all stations under 1 transmit (both A and C), then under 2 (same), then under 4 (just A – success).

Regarding the average (excepted value), it's a combination of two things: the average tries you need until any station transmits, and the expected value of a successful transmission assuming at least one station transmitted. The first is a standard geometric distribution, where the expected value is $E=1/p$.


Amortized analysis - increment in ternary counter What is the amortized analysis of increment action in a ternary counter that is initialized to 0?

The amortized cost per increment will be $O(1)$. In order to show it let's use the aggregate method.

0  - 000
1  - 001
2  - 002
3  - 010
4  - 011
5  - 012
6  - 020
7  - 021
8  - 022
9  - 100
10 - 101
11 - 102
12 - 110
13 - 111
14 - 112
15 - 120
...

We can notice that the bits in the 0th place are changing in every increment operation ($3^0$). The bits in the 1th are changing in every 3th increment operation ($3^1$). The bits in the 2th place are changing in every 9th increment operation ($3^2$). And so on.

The total number of changes equals to the sum of times that every bit has changed. Let's assume $n\lt 3^{k+1}$ for some $k$.
So the total number of changes in $n$ increments is no more than
$$n+\frac n3+\frac n9+\frac n{3^3}+....+\frac n{3^k} < \frac32n$$
Assuming it takes $O(1)$ to perform the change of one bit and the associated bookkeeping, the total cost of the sequence is $O(n)$.
So the amortized cost per operation is $O(n)/n= O(1).$


Randomized Algorithm in $O(d)$ for Solving Unknown Degree $d$ Polynomial Function Using an Erroneous Oracle Consider the field $GF(p)$, where $p$ is a prime number. If there is a function $f: GF_p \times GF_p \rightarrow GF_p$ which has an unknown degree $d$ polynomial, with $1 < d < p / 4$.

Although $f$ is unkonwn to us, there is an erroneous oracle $O$ satisfy the following property:
$\underset{(x,y)\in GF_p \times GF_p}{Pr}[O(x,y) = f(x,y)]\ge1 - \frac{1}{20d}$.

The question asks us to come up with a randomized algorithm which makes $O(d)$ queries to the oracle $O$ and returns the correct value of $f(0,0)$ with probability at least 0.9.

The following is my thinking process: the probability of $O(0, 0) = f(0, 0)$ is at least $1 - \frac{1}{20d}$ according to the condition before. If the probability is at least 0.9, then $d$ should be $d \ge \frac{1}{2}$. Then $p$ should be larger than $2$. We can assume the expression for $f$ is $a_db_dx^dy^d + a_db_{d-1}x^{d}y^{d-1} + a_{d-1}b_dx^{d-1}y^d + a_{d-1}b_{d-1}x^{d-1}y^{d-1} + ... + a_0b_0$. There are total $d^2$ number of items in the function. The randomized algorithm is that we could randomly select the value of $x$ and $y$ from $GF_p$, and at the following $d^2$ steps, we decide the parameters of the polynomials.

for i from 1 to d steps:
    for j from 1 to d stpes:
         randomly assign the values of other parameters except a_ib_j;
         solve the value of a_ib_j using the randomly assigned x, y and
         the result queried from Oracle with x and y;

This is just my general idea. The problem is I do not know the degree $d$, so I cannot decide the exact number of steps $d^2$. And even if I know the degree $d$, how can I manage to decrease the time from $O(d^2)$ to $O(d)$?

Or maybe I am going in the wrong way. Can somebody help me with this?
Any help would be appreciated. Thanks in advance.

Some hints:

Could you solve the problem if the function was of the form $f : GF_p \to GF_p$, i.e., a univariate polynomial?  I suggest solving that special case first.  The below are some hints on how to do that:

If the error was zero, would you know what to do?  Could you devise a strategy that would always work in that situation?  How many queries would your strategy need?

Now suppose you applied your strategy, in the situation where there could be errors (but with the error probability bounded as you've described).  What's the probability that your strategy gives the wrong answer?  What's the probability that your strategy gives the right answer?

You might find it useful to use a union bound.

Can you think of any way to check whether a possible solution is correct?

Finally, once you can solve the univariate case, can you think of any way to repeat that procedure multiple times to handle the situation of a polynomial in two variables?


Algorithm / data structure to filter documents by number of missing words Is there a data structure or an algorithm or a combination of both to allow me to filter a set of documents based on the number of missing words (compared to another list)?

Problem Definition

We have a list of documents $D = \{d_1, d_2, \dots, d_n\}$. Each document $d_i$ consists of a subset of words from a word pool $W = \{w_1, w_2, \dots, w_k\}$. For example, $\text{words}(d_1) = \{w_1, w_5, w_{7}\}$.

Each person $p_j$ also has a set of words $\text{words}(p_j)$.

The goal is to find all documents where the length of the set difference between both is smaller than a threshold $t$:

$$
|\text{words}(d_i) \setminus \text{words}(p_j)| < t
$$

$\text{words}(p_j)$ will in most of the cases be much larger than $\text{words}(d_i)$ (i.e. there will be a lot of words in the person's set that are not in the document's set).

Complexity

The sizes will probably be around these numbers:

documents: millions or tens of millions of documents
words: around 100k different words (per independent set)
person: between 1 and 1000 people

Use Cases

My actual use case for this is to retrieve foreign language texts where I do not know all the vocabulary, yet. I have a list of words that I know for each language and I want to find documents from a collection of texts that contain between 1 and 10 words that I do not know, yet. That way, I expect to be able to find texts that I can understand while also improving my vocabulary skills.

Another use case might be finding recipes that match a user's stock at home. In this case, you might want to find documents (recipes) that contain between 0 and 2 missing items, so that the user either has to buy nothing or can replace the few missing items with something similar.

My current approach

While it is easy to find documents that have an overlap of at least $t$ words, I found the opposite (find documents that have a difference of at most $t$ words) quite complex. At the moment I fell back to a two stage approach:

I first filter documents by the length of the text and the length of the sentences and compare them to an average value I store for myself
In the filtered list I then loop in my code and calculate the set difference for each document and delete all that have more than $t$ unknown words.

Use a locality sensitive hash, like MinHash or SimHash.

You could also sort the set of words, extract shingles, and hash them using MinHash or something similar.