How the website owner keep track of your times of access? To be specific, I am using the online website of Strait Times News. It limits users to 30 articles to read per month. I just do not understand how do they know you are accessing? We use different IP each time we go online, don't we?
 Is there anyway to hack this?

I am not sure how this website keeps track but I can tell you the general flow how usual websites keep track of user's data.

If the you are registered user on the site it doesn't matter which ip you use it can be tracked easily.
To be more specific when you read the complete article a tracker can be anywhere from page-end scroll to read-more button.

Edit1: Looks Like the website you are talking tracks user based on (article click+ip+ cookie) so it is easy just to choose new ip + incognito browsing to get 30 article limit each time.


What are string matching algorithms used in text editors like Atom and sublime I know there are many algorithms for finding a pattern in a text like Boyer Moore, KMP, RabinKarp and so on.
I want to know what is the one that is mostly prefered by text editors and IDEs, as I find them efficient.

Since Emacs is the superior editor, you can take a look in the source code yourself:  search.c
Emacs uses the Boyer–Moore string-search algorithm, so that's probably what you should prefer too.


CFG that generates $1^*$ is decidable I read somewhere that the problem which asks whether or not a $CFG$ $G$ generates $1^*$ is decidable. The proof goes like this:

$1^* \cap G$ is context free since it is the intersection of a regular language and a $CFG$, therefore we can test if $1^* \cap G$ is empty since it is decidable to check if a $CFG$ is empty. If $1^* \cap G$ is empty, reject, otherwise, accept.

I have doubts however with this proof since it only shows that some string in $1^*$ is generated by $G$, but not whether $G$ generates all strings in $1^*$.
Moreover, if this proof is correct, we can use the same proof outline under the alphabet $\Sigma=\{0,1\}$ to show that $G$ generates $\Sigma^*$, or that $\Sigma^* \subseteq G$. However, it is known that it is undecidable whether $R \subseteq G$, where $R$ is a regular language, and $G$ is a $CFG$ (by setting $R=\Sigma^*$, and $\Sigma=\{0,1\}$.
But to show that a $CFG$ generates $1^*$ is decidable, the only way I can think of is to use something similar to the proof that it is decidable for a $PCP$ instance to generate some string in $1^*$ (i.e., $w=v$, where $w,v \in 1^*$), i.e. we can check if the $CFG$ has rule $S \rightarrow S1$, then accept. Otherwise, if it has rules of the form $S \rightarrow 1^aS1^b$ such that $a > b$, and rules of the form $S \rightarrow 1^cS1^d$ such that $c < d$, then accept... But is there a simpler way to solve this problem?

Maybe you're confusing two different problems.
The algorithm you are describing shows that the problem of testing whether a CFG generates some string from $1^∗$ is decidable (e.g., see here at page 21). Anyway, the problem of testing whether a CFG generates all the strings of the language $1^∗$ is truly decidable. Consider all production rules to be simple (I mean, no "$|$" on the right), and eliminate all productions including a teminal character different from 1 on the right. Now you have a CFG over a terminal alphabet of a single letter, and then it generates a regular language (see here). All that remains is to test if two regular languages are equal. Moreover, there are effective procedures to convert a CFG over a one letter (terminal) alphabet into a regular grammar (e.g., see here).

I was forgetting the last part of your question: the fact that it is undecidable whether $R\subseteq G$, where $R$ is a regular language, and $G$ is a CFG, does not implies that for some specific regular languages you can not decide the inclusion. For example, if $R$ is finite (possibly empty), then testing for $R\subseteq G$ is decidable (see the first link above).


Algorithm to decide if $n \le m!$ This is an assignment of an introductory course of complexity theory and I need to find a way to do the following:

Given $n,m \in \Bbb N$, is $n \le m!$ ?

The idea is to provide a Post Machine that can decide this in an efficient way, using $n,m$ in a binary codification.

We know that the factorial isn't efficient, so the problem actually is just to find a way to decide this, if it's possible.

I know how to compare if $n\le m$, but the factorial is my problem.
I don't how how to compute $m!$ with a Post Machine, if possible, in polynomial-time.

I guess that the most simple way to do this is comparing $n$ with factorials of numbers that are lower than $m$, but the factorial it's still my problem.

My question, is there an algorithm that can help me?

Here is a different solution than the one I suggested in the comments. Compute the sequence of factorials $1!,2!,3!,4!,\ldots$ until you get a number which is at least $n$. Since $(k+1)!/k! = O(\log (k!))$, you only compute numbers of magnitude $O(n\log n)$ and so of length $(1+o(1))|n|$ (here $|n|$ is the length of $n$ encoded in binary). Having found the least $k$ such that $n \leq k!$, we know that $n \leq m!$ iff $m \geq k$.

Since the sequence of factorials grows so fast, the running time isn't too bad — it's quasilinear in $|n|$ (at least in the RAM model). I'll let you work that out.


Simulating a sequence of events concurrently subject to a happened-before partial order I am building a strategy game where multiple units(5 - 20) is fighting each other in the same time.

I have a logic part that calculate those actions for each turn, and than pass it to the game engine to animate. This is the list of action that I currently supporting:

perform attack
perform miss
perform taking damage
perform dying
perform moving

If I animate all the actions at once than it look messy:

  Unit A attacks unit B, while unit B is not even there, it went to
  attack unit C

If I animate all the actions one by one, than it looks lame

  Unit A attacks unit B, the other 18 units is just stand and waiting
  for the unknown...

How can I find what actions I can perform in parallel?

For now my best solution, is to wait for unit to finish attacking before attacking it, it cover many scenarios but it still got halls.

  Unit A attacks unit B, unit C waiting for A to finish attacking in
  order to attack him. Unit D attacks and kill unit C.

Edit based on D.W answer:

This solution cover most of the cases but, I found a hall in it.

Think about the next scenario

  A attacks B, B attacks C, C attacks D

Because each of those action has a dependency on the prevues one, your algorithm would suggest to break it in to 3 sequences.

A attacks B
B attacks C
C attacks D

How ever I would like to break it in to, two sequences:

A attacks B, C attack D
B attacks C

I want to use your algorithm solution iff B kills C.

Try identifying all dependencies between actions, then build a DAG that represents the dependencies: each vertex is an action, each edge is a dependency between two actions.  From this you can identify how to perform the maximum number of actions in parallel.  Basically, the algorithm is:

Find all the sources.  Perform all of those actions at once.
Delete all of those sources, and the edges going out of them.
Go back to step 1.

A source is a vertex with in-degree zero, i.e., with no edges entering into it.  In your context, it will be an action all of whose dependencies have been satisfied.

For instance, if action 1 must occur before action 2, which must occur before action 4, and action 3 must occur before action 4, the resulting order you get using this algorithm is: first actions 1 + 3 are performed (because they are the two sources); then action 2; then action 4.


Find perfect matching faster than MCM, in graph that has perfect matching? Given an unweighted bipartite graph which has a perfect matching, is there an algorithm for finding a perfect matching in the graph that is faster than the best known algorithm for finding a maximum cardinality matching (MCM)? For example, is there some way to take advantage of the fact that the graph is known to have some perfect matching to help find one faster?

If yes, could you please help to point out some references? If it is impossible, could you briefly explain the reason? Comments and suggestions are also welcomed.

Hopcroft-Karp isn't necessarily optimal, and you can already find asymptotically faster algorithms in the relevant Wikipedia pages: https://en.wikipedia.org/wiki/Matching_(graph_theory)#In_unweighted_bipartite_graphs, https://en.wikipedia.org/wiki/Maximum_flow_problem#Solutions.  Note that you can use any network flow algorithm to find a perfect matching.

For instance, you can achieve $O(n^{2.373})$ running time using fast matrix multiplication, though this is only a theoretical result; in practice it's slower.  However, this is already enough to demonstrate that there's no way we're going to prove that you can't do better than Hopcroft-Karp (because you can).  For sparse graphs ($|E|=O(n)$), Madry's algorithm achieves $O(n^{1.43})$ running time.  Neither of these use/exploit the fact that the graph already contains a perfect matching.


Finding all marked elements using Grover's algorithm Grover's algorithm uses an oracle function $f(x) \to \{0,1\}$ to find the location of a single marked element from an unordered database of $2^n$ elements with high probability. As part of an assignment I am supposed to design a variant of the algorithm that finds all of the $t$ marked elements ($t$ is known). I want to do this by repeating the following procedure $t$-times:

Use Grover's algorithm to find any marked element $x$.
Delete $x$ from the data base.

I think my solution is correct, but I am still not feeling comfortable with quantum computing. In particular, I am unsure of how one could implement the removal step since it would mean to manipulate the function $f$.

Can anyone clarify?

After discussing the problem with some people from my institute that work on quantum computing, it turns out that one can augment the oracle to not provide elements that have already been found in previous iterations of the search. The trick is to modify Grover's algorithm as follows:

Say, we already know that 2 is an answer (from a previous iteration). After using the oracle to invert the phase of the marked elements within Grover's algorithm, we apply another operation that inverses the phase of the known answers again (thus cancelling the previous inversion for answers that are already known). Accordingly, the inversion about the mean in Grover's algorithm will not amplify the amplitude of these states.


Where are 'Base & Bounds' registers located? I read about virtual memory from L08/CS152 of U.C Berkeley and used to deep dive into the details of VM hardware implementation, yet didn't find any document or figure on the course specifying where the 4 “Base & Bounds“ registers (Data Bound Register, Data Base Register, Program Bound Register, Program Bound Register) used in the figure below are located. In order to have more detailed information, I did many searches for “MMU architecture”, “X86 architecture”, “bound register',  “base register”, and so on .. But without success.

Are B&B registers located on the MMU or on the CPU? Can anyone provide any related hardware architecture reference?

The values for base and limit must be stored in registers somewhere; it would be highly inefficient to read these from memory on every memory access.

The distinction between "CPU" and "MMU" isn't really an important one on the old Cray vector architectures, and also isn't really important today. This is more about older microprocessors where a "processor" lived on more than one die (e.g. the 68000 architecture which had an external MMU). Today, address translation is closely tied to the rest of the CPU. This actually made the news this week, since Meltdown uses the interaction between the MMU and instruction speculation as a side-channel attack against some Intel CPUs. But I digress.

The diagram is talking about Cray vector computers, so probably the best reference is to look at an old Cray manual.

So here is the Cray Y-MP EL (i.e. the "entry level" model) functional description document, and the description of the exchange mechanism in particular:

  Address Base and Limit Fields

  Four registers in the exchange package define a program's data range
  and instruction range anywhere in memory and allocate specific amounts
  of memory to each range. This memory allocation technique has two
  benefits. First, all programs are relocatable. When a program is
  written, the programmer does not need to know where in memory the
  instruction and data fields will be located. Second, each program can
  have its memory access restricted to certain parts of memory. A
  program can be halted if it tries to run an instruction outside of its
  allowed instruction range or if it tries to read or write data outside
  of its allowed data range. This is especially important where more
  than one program occupies memory at the same time; programs can be
  prevented from executing instructions or operating on data that
  belongs to other programs. The four registers are described in the
  following list.

  The instruction base address (IBA) register holds the
  base address of the user's instruction range. It determines where in
  memory an instruction fetch is made. This is done by adding the
  contents of the P register to the contents of the IBA register. The
  sum equals the absolute memory address for the fetch.
  The limit address (ILA) register holds the upper limit address of the
  user's instruction range. It determines the highest absolute address
  that can be accessed during an instruction fetch sequence. If this
  absolute address exceeds the limit, a program range error flag is set,
  which generates an interrupt.
  The data base address (DBA) register
  holds the base address of the user's data range. It determines where
  in memory a program's data field is located. This is done by adding
  the memory address generated by the instruction to the contents of the
  DBA register. The sum equals the absolute address for any memory read
  or write operation.
  The data limit address (DLA) register holds the
  upper limit address of the user's data range. It determines the
  highest absolute memory address that a program can use for reading or
  writing data. If this absolute address exceeds the limit, the memory
  reference is aborted. The operand range error flag is set, which
  generates an interrupt if the interrupt-on-operand range error bit is
  set.

Altering these registers is typically a privileged operation, in that it is reserved for supervisor-level code rather than user-level code. On Cray machines, these registers were set with an "exchange package", which is more or less the equivalent of a process control block, so it was presumably an operating system routine that set the registers when a task was run.

Now let's take a quick look at a modern architecture.

For Intel x86, this is called memory segmentation. The base and limit registers aren't accessed like normal registers, but are stored in a special data structure called a segment descriptor, which is loaded with the LGDT or LLDT instruction. The difference between the two is that the x86 architecture supports two descriptor tables: "global" and "local". Each process can have its own local table, which is used for features such as thread-local storage.

The situation changed completely with the advent of 64 bit CPUs. In 64-bit mode, segment descriptors are, for the most part, no longer used. There are two segment selectors, FS and GS, which support loading a base field using the model-specific register mechanism, as well as a special instruction called SWAPGS, the details of which are only important for operating system implementors. Note that these selectors have no limit field. Protecting memory from unauthorised access is handled using the paging mechanism, not segmentation limits.

This brings the Intel architecture in line with most other modern CPUs, such as ARM, which do not support memory segmentation.


"Or" in regular expressions I'm a bit new to automata theory, I'm sorry if this question is a bit too simple. If this question has been answered somewhere already, please point me to it.

One basic problem I wanted to solve was defining the minimal set of states need to construct a (minimal) DFA that accepts

$$(a^+)+bcd^*\,.$$

I'm not sure how to treat the OR operator here, though.

I assume it means I can accept either ($a^+$) OR $bcd^*$ OR both (but in the given order), but does it mean I can ignore the order as well (meaning that, e.g. $bcdddaa$ would be acceptable as well)?

If anyone could explain, I would appreciate it. I understand the meaning of other operators.

You're confusing "or" with concatenation.  Also, In computer science, a string matching a regular expression means that the whole string matches whereas regular expressions used in computer software usually just require some part of the string to match the expression.

A string matches $a^+$ if the whole string is composed of $a$s and nothing else, and there's at least one $a$.  A string matches $bcd^*$ if it consists of a $b$ followed by a $c$ followed by zero or more $d$s and nothing else.

A string matches $a^++bcd^*$ if it matches $a^+$ or it matches $bcd^*$ or if it matches both. However, it's not possible to match both: a string can't be composed entirely of $a$s and also begin with a $b$ and a $c$.

In particular, $aabcdd$ doesn't match $a^++bcd^*$ because it doesn't match $a^+$ (it contains characters that aren't $a$) or match $bcd^*$ (it doesn't even begin with $b$).  However, $aabcdd$ does match $a^+bcd^*$, which is the concatenation of $a^+$ and $bcd^*$.  $bcddaa$ matches neither $a^++bcd^*$ nor $a^+bcd^*$.


Merkle tree sorting leaves and pairs I am implementing a Merkle tree and am considering using either of the two options.
The first one is sorting only by leaves. This one makes sense to me since you would like to have the same input every time you are constructing a tree from the data, that might not arrive sorted by default.
       CAB
      /    \
     CA     \
   /    \    \
  C     A     B
/  \  /  \  /  \
1  2  3  4  5  6

The second one is sorting by leaves and pairs, which means that after sorting the leaves, you also sort all the pairs after hashing them, however I'm not entirely sure about the benefits of this implementation (if any).
       ACB
      /    \
     AC     \
   /    \    \
  C     A     B
/  \  /  \  /  \
1  2  3  4  5  6

I have seen these implementations of Merkle trees in the past but am not sure about their benefits. So why choose one over the other?

A bit late to the party, but the second approach can be useful to simplify the merkle-path. When hashing a pair, it's required to know if the leaf is on the left or right side of the pair. This can become quite complex, for example, when implementing multi-leaf inclusion proofs. By sorting the pairs before hashing, it doesn't matter which side the leaf actually has in the pair, as you're applying the same rule every time. Pretty neat solution in my opinion.


Demonstrating that for every monotonic grammar there is an equivalent context-sensitive grammar I'm trying to understand the equivalence in expressive power of formal grammars whose rules take the form:

$$ \alpha \rightarrow \beta $$ where $ |\alpha| \leq |\beta| $ (called a monotonic grammar), and grammars whose rules take the form:

$$ \alpha B \gamma \rightarrow \alpha C \gamma  $$

where $\alpha $ and $\gamma$ are strings of terminals & non-terminals or possibly empty, and $B$ and $C$ are single non-terminals. I understand that grammars of the second kind are already, by definition, grammars of the first kind, but I'd like to understand how to derive a grammar of the second kind, given one of the first kind (a monotonic grammar). Can anyone suggest a good reference for this? Many thanks in advance.

First replace ever terminal $a$ with a non-terminal $X_a$ and add a production $X_a \to a$, because context sensitive grammars only work on non-terminals. Then, for every production $A_1\dots A_n \to B_1\dots B_n$ create new non-terminal $D$ and replace the production with a sequence of productions $$\begin{align} A_1A_2\dots A_n &\to DA_2\dots A_n \\ DA_2A_3\dots A_n &\to DB_2 A_3 \dots A_n \\DB_2A_3A_4\dots A_n &\to DB_2 B_3A_4 \dots A_n \\ &\vdots \\ DB_2\dots B_{n-1}A_n &\to DB_2\dots B_{n-1}B_n \\ DB_2 \dots B_n &\to B_1B_2 \dots B_n \end{align}$$which are all context sensitive. Also, replace every production $A_1 \dots A_n \to B_1 \dots B_m$ where $n < m$ with $$\begin{align} A_1\dots A_n &\to B_1\dots B_{n-1}C \\ C &\to B_nB_{n+1} \dots B_m\end{align}$$where the first production can be made context sensitive as previously shown and the second one is context free. Of course, this construction may introduce problems (if $B_1A_2 \to \dots$ is already in the grammar, for instance). This is easily solved by adding new non-terminals.


Turing machine and boolean circuits As an example of languages that are in P/poly is the UHALT Problem :

  UHALT = { 1^n: n's binary expansion encodes a pair  such that M halts on input x}

We can create a boolean circuit of just AND gates.
However, we can create it only for a fixed 'n', not for all n's ...

My question is : when we consider a language like the UHALD problem, do we consider all of the 'n' possible values ,ie for every 'n' we have a different language? or for every n we have a different language ?

In Turing-machines, i think we can loop, but in boolean circuits.. i dont think we can, thus the impossibility (in my point of view) of making, for example, a circuit for the UHALT problem for every n there is.

The Boolean circuits you are referring to are a non-uniform model. This means that, for every input length, you have a different circuit. When we say that Boolean circuits solve a particular problem what is actually meant is that a family of circuits does, which is an infinite sequence $(C_n)_{n \in \mathbb{N}_0}$, $C_n$ being the circuit for inputs of length $n$.

Moreover, Boolean circuits in general are intrinsically non-uniform models of computation anyway since the input gates count as part of the circuit. If you insist on an arbitrary number of input gates, then you necessarily end up with a circuit of infinite size (which is a no-no). (In fact, this is why we use the notion of constructability to obtain uniform circuits; any sort of uniformity must be extrinsic to the circuit.)


Algorithm for Items Best Fit/Arangement in a Box I was looking for an algorithm that will give the best fit arrangement of package items in a box. For example given a large box and various items with multiple shapes(can be rectangle, square and so on and so forth), how will I arrange the items so that it will fit in the box? DO we have already an algorithm for that? If yes, what algorithm is it?

If no, I was thinking of making an algorithm for it.

Yes, there are plenty of algorithms.

Here are some existing literature about packing rectangles.

What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way?
Pack rectangular objects of different sizes in a fixed size rectangle?
Approximation Algorithms for Rectangle Packing Problems.
Optimal rectangle packing.

Here are some libraries that can be used readily.

Python 2D rectangle packing library
Rectangle packing program
Github topic on packing algorithms


Context formal language recognizing even number of 0's and odd number of 1's I have an assignment, it's asked to write a context free grammar recognising the language $L=\{ w \mid w\text{ has an even number of }0\text{s and an odd number of }1\text{s}\}$, over the alphabet $\{0,1\}$.

My first guess was:

$$
\begin{align}
S &\rightarrow A1A\\
A &\rightarrow A0A0A \mid A1A1A \mid \varepsilon
\end{align}
$$

But I realized it's wrong, since, for example, it doesn't accept the string $01011$ (I think my CFG forces pairs of $0$s).

Any suggestion?

This language is, in fact, regular – it is accepted by an automaton with just four states. I suggest that you first figure out what this automaton is and use what you learn to figure out a grammar. In particular, you don't need any context-free "tricks" or techniques.

If you need to, mouse-over the yellow area below to see a more detailed hint for the automaton.

   Think about what data you need to know when you reach the end of the string, in order to decide if your input is in the language. What is the value of that data when you haven't read any input? How do you update that data as you read the input?


Approximating Deep Neural Networks (DNNs) with Binarized Neural Networks (BNNs) I am working currently as a research intern on Binarized Neural Networks where the weights and the activations of the network are binary. The architecture of this type of networks makes them memory efficient and computationally efficient, which makes them ideal for resource constrained environments, like embedded devices and mobile phones.

The interesting part about BNNs is that we can encode a binarized network as a CNF formula (Boolean Formula). Using this formula, we can verify some properties of the network like Robustness against adversarial examples (carefully crafted samples looking similar to usual inputs but designed to mislead a pre-trained model). We can also extract explanations that support neural network decisions, hence make the neural network explainable.

Currently, I am trying to make a DNN explainable by verifying its decisions using BNNs. The first direction of research is to reduce a DNN to a BNN. Of course the two networks should be equivalent. I am researching ways to make this reduction but I haven't found any works in the subject.
Is it possible to carry out this transformation ? Is there any techniques that can "binarize" a DNN ?

Thanks :)

I expect you'll run into two challenges in this line of research: (1) there are no known ways to construct a BNN that exactly matches an ordinary neural network; (2) verifying a BNN with a SAT solver won't scale to the size models needed for most interesting tasks.

Since you asked specifically about (1), no, I don't know of any way to do that.  Probably you won't find exact equivalence.  You might be able to train a BNN that has a very high agreement with the ordinary neural network on the training set; I don't know whether it will have the same adversarial examples or not.


How To Merge Together Two Circular Doubly-Linked Lists In O(1) Time? I'm implementing a Fibonacci Heap, where the lists are stored as a circular doubly-linked lists. What I'm trying to do is given a pointer to a random node in one linked list, and a random node in another, I want to merge them together in O(1) time. I tried drawing this out, but I couldn't seem to figure out how to do this. Here is my first idea, in pseudocode:

union(Node one, Node two) {
    if other = nil
        return

    p1 = one
    p2 = one.right
    p3 = two
    p4 = two.right

    p1.right = p4
    p4.left = p1
    p2.right = p3
    p3.left = p2
}

Each Node has a left and right attribute, which stores the node to the left and right, respectively. However, this didn't work. Can anyone figure out how to merge together two linked lists?

There is no need to use temporary variables. See the following picture and the associated pseudocode below. You want to reassign the gray pointers to their colored counterpart. You just have to be careful with the order of the instructions.

one.right.left = two.left;  //red
two.left.right = one.right; //blue

one.right = two; //green
two.left = one;  //purple


Find all vertices that are included in a simple cycle through a fixed vertex in a directed graph Given a directed graph $G = (V, E)$ and a vertex $v \in V$, how to find all vertices $v'$ such that exists a simple cycle $v \to ... \to v' \to ... \to v$? That is, to find the set of vertices $$V' = \{v' : \exists c, \text{c is a simple cycle in G}, v \in c, v' \in c \}$$
I found this question related: Find all cycles through a given vertex. I can first find all cycles and then union them to get $V'$. However, is there a more efficient way to do so?

I believe the problem is NP-hard, by reduction from the two disjoint paths problem.
The two disjoint paths problem is as follows:

Given a directed graph $G$ and $(s_1,t_1),(s_2,t_2)$, find two paths $s_1 \leadsto t_1$ and $s_2 \leadsto t_2$ that are vertex-disjoint (they have no vertex in common).

This problem is NP-hard.
We can reduce two disjoint paths to your problem.  In particular, given $G$ and $(s_1,t_1),(s_2,t_2)$, we construct a new graph $G'$ by adding new vertices $v,v'$ and  adding edges $v \to s_1$, $t_1 \to v'$, $v' \to s_2$, $t_2 \to v$.
Notice that any pair of vertex-disjoint paths $s_1 \leadsto t_1$, $s_2 \leadsto t_2$ will yield a simple cycle
$$v \to s_1 \leadsto t_1 \to v' \to s_2 \leadsto t_2 \to v.$$
Also, within any simple cycle $v \leadsto v' \leadsto v$ we can find simple paths $s_1 \leadsto t_1$, $s_2 \leadsto t_2$ that are vertex-disjoint.  It follows that there exists a simple cycle $v \leadsto v' \leadsto v$ in $G'$ iff there exist two vertex-disjoint paths $s_1 \leadsto t_1$, $s_2 \leadsto t_2$ in $G$.  So, any algorithm for solving your problem would immediately yield an algorithm for solving the two disjoint paths problem.


How to determine the set of real numbers corresponding to a given floating point number? Let's say we consider IEEE 754 double precision floating-point numbers, and we use RNTE - Round To Nearest, Ties to Even - rounding.
I know that the RNTE rounding works this way:
given two consecutive floating-point numbers, a and b, and a real number x,

if a <= x < (a+b)/2, x gets translated to a
if (a+b)/2 < x <= b, x gets translated to b
if x = (a+b)/2, x gets translated to the number with an even significand between a and b

For example, I want to know which are the real numbers that are "mapped" to 1, where 1 is a floating-point number. How should I proceed? I thought that I must consider both the cases where 1 is a and where 1 is b in the above definition, and so consider both the previous and the next floating-point number. Is it correct? Is there a simpler way?

The powers of two are more interesting than most other numbers.
Assume you are using double precision IEEE 754 format floating point numbers. Let $u = 2^{-52}$, Then the next floating point number larger than 1 is $1+u$, and the next floating point number smaller than 1 is $1 - u/2$.
A real number x is rounded to 1 if $1-u/4 ≤ x ≤ 1+u/2$. For any floating-point number f with $1 < f < 2$, x is rounded to f if $f - u/2 ≤ x ≤ f + u/2$ if the last bit of f is even, and if $f - u/2 < x < f + u/2$ if the last bit of f is odd.
Numbers x with $f - u/2 < x < f + u/2$ are always rounded to f, because f is the nearest floating point number. For the numbers $x = f ± u/2$, $f$ and $f ± u$ are equally far away, so the round-to-even rule decides.


Best data structure for high dimensional nearest neighbor search I'm actually working on high dimensional data (~50.000-100.000 features) and nearest neighbors search must be performed on it. I know that KD-Trees has poor performance as dimensions grows, and also I've read that in general, all space-partitioning data structures tends to perform exhaustive search with high dimensional data.

Additionally, there are two important facts to be considered (ordered by  relevance):

Precision: The nearest neighbors must be found (not approximations).
Speed: The search must be as fast as possible. (The time to create the data structure isn't really important).

So, I need some advice about:

The data structure to perform kNN.
If it will be better to use an aNN (approximate nearest neighbor) approach, setting it as accurate as possible?.

Here is a closely related question (although different enough that I wouldn't call this a duplicate): https://stackoverflow.com/questions/5751114/nearest-neighbors-in-high-dimensional-data

As you said, all known structures degrade to linear search as the dimension grows. More specifically, the efficiency degrades as the dimension approached the number of points in the feature space (binary search doesn't help with two points, K-D trees are useless on three points, etc.).

However, if the time to create the data structure does not matter at all, you can create a complete graph with sorted edge lists. That is, every node keeps track of its neighbors in nearness order. This would take $O(n^2 \log n)$ time to create, but would give you the kNN of any point in $O(1)$.


Why isn't there a universal separator character for data files? I am not sure if this is the correct forum for this question, but... After so much time and usage of spreadsheets and data files in general, there is a need to cater for all types of files containing all sorts of characters used as a field separator. Why hasn't a universal separator character evolved so that no-one has to bother with tab vs. pipe vs. comma (with and without quoted fields) vs. whatever? You would think that there would be a dedicated key on the keyboard like the "Enter" button used for field separation that is non-printable and that would reduce the number of data file types to one (with the exception of proprietary formats).

We could have a field separator, but we don't, because of historical reasons. Most of the characters are brought from the era of typewriters. So we have line-separator ^M and page-separator ^L, and we actually have record separator \037 and unit separator \038 which can be used as field separator. But in reality no one uses that. First if you have a text file like csv, you want to use separators which are visible like , : TAB or SPACE. If your file is binary you are free to do almost anything with it.

Now it is too late to have a universal field separator. You can have your own private field separator of your choice. Just don't use it in your fields too.


Definition of $\Theta$ for negative functions I'm working out of the 3rd edition CLRS Algorithms textbook and in Chapter 3 a discussion begins about asymptotic notation which starts with $\Theta$ notation. I understood the beginning definition of:

$$\Theta(g(n)) = \{ f(n)\,|\, \exists\, c_1, c_2 > 0, n_0 \in \mathbb{N}: 0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n)\ \ \forall n \geq n_0\}$$

But then on the next page the text says that:

  The definition of $\Theta(g(n))$ requires that every member $f(n) \in \Theta(g(n))$ be asymptotically nonnegative, that is, that $f(n)$ be nonnegative whenever $n$ is sufficiently large. (An asymptotically positive function is one that is positive for all sufficiently large $n$.) Consequently, the function g(n) itself must be asymptotically nonnegative, or else the set $\Theta(g(n))$ is empty.

That last part about the how if the function is negative the set $\Theta(g(n))$ is empty and the general requirement of a positive function is sort of confusing. Can anyone out there clarify this definition for me and what it means, possible with an example, it would be much appreciated.

This is just a technicality. In asymptotic analysis we are only "really" interested in positive functions like $n^3$ or $n\log n$. However, if we want to be very formal and general, we could take into account non-positive functions (and that could turn it to be useful, see below). The definition of $\Theta$ states that $f(n) = \Theta(g(n))$ if from some point on, $f(n)/g(n)$ is bounded from both sides by constants, and furthermore $g(n) \geq 0$. (That's what you get if you unroll the definition.) In particular, if $f(n) = \Theta(g(n))$, then from some point on, $g$ is non-negative.

Here is an alternative definition of big $\Theta$. Suppose $f,g \colon \mathbb{N} \rightarrow \mathbb{N}$ are positive functions, that is $f(n),g(n)>0$. Then $f(n) = \Theta(g(n))$ if there exist positive constants $c_1,c_2$ such that $c_1 \leq f(n)/g(n) \leq c_2$. I don't know why the more complicated definition is presented in introductory texts.

What are the advantages of the more complicated definition? It can handle functions which have some non-positive values (there has to be a finite number of them). For example, this definition accommodates the (true) statement $n-10 = \Theta(2n-30\log n)$. Although functions encountered in practice are usually positive, sometimes negative functions could be encountered: for example, say we're interested in some genuine complicated function $k$, and we estimate it from below by a function $t$, which is however negative for small $n$.


Computing the error bound of floating-point expression How should I compute the maximum absolute and relative error of the following IEEE-754 floating-point expression?

a.y + (x - a.x) * ((b.y - a.y) / (b.x - a.x))

Also, we assume, that

the optimizer leaves the expression in the specified form
the default rounding mode (round to nearest even)

IEEE 754 gives you the maximum relative error of each operation. You have three differences with a maximum relative error each. Multiplication and division adds the maximum relative error of each operand, plus the maximum relative error of the multiplication and division.

Then you have a final addition. If the right hand side is very close to the negative of the left hand side of the "+" then the relative error is unlimited. You'd need to analyse how close to -a.y the right hand side can be.

For absolute error, you convert the relative error of the right hand side into an absolute error.


Are probabilisitc algorithms deterministic? I got confused with deterministic and probabilistic algorithms. Am I right by assuming that algorithms are called probabilistic once they use some sort of randomness?

Initially, I thought only algorithms outputting random numbers are called probabilistic. They are obviously non-deterministic.

However, what about the following algorithm: Take BubbelSort and randomly decide whether to start sorting from left to right or from right to left. If you modify the sorting order, the algorithm is deterministic, because small values will always be on the left and great values on the right side (or vice versa). As there is some randomness in the algorithm, do we call this algorithm probabilistic?

In short: Any algorithm using some randomness is called probabilistic. Is that correct? However, this term has nothing to do with determinism and non-determinism. Is that correct?

A probabilistic algorithm is one which has access to the output of a random source during its computation. It might be the case that although the algorithm uses randomness, the output is deterministic, i.e. for every possible random string obtained from the source the output is the same (you can always just ignore the source and act solely on the input).

Note that when you're dealing with probabilistic algorithms, your output becomes a random variable. The output can be deterministic in the sense that it is always the same, or can take some value with probability 1 (which is a weaker statement).


Finding simple cycle of minimal weight in directed bipartite complete graph with negative cycles Given a weighted complete bipartite directed graph K_{m,n}, is it possible to find a simple cycle (every node is visited at most a single time) with minimal weight in polynomial time (in m*n) when there exist simple cycles with negative weight?

For general graphs this problem is NP-complete (Finding the lowest-weight negative cycle in a weighted digraph). Using Bellman-Ford it is possible to find a cycle with negative weight if such a cycle exists, but this algorithm gives no guarantee that it is the most negative cycle.

In total there are

simple cycles in this graph, so checking all of them would already give a subexponential algorithm. But can this be reduced to a polynomial time algorithm?

Some assumptions I can make:

The absolute value of the weights are bounded by a constant C.
There exists a negative simple cycle and all negative simple cycles visit at least 4 nodes.

Thanks.

No.

That is, there is no polynomial time algorithm in $m\times n$ that can find a simple cycle with minimal weight in any given weighted complete bipartite directed graph K_$\{m, n\}$ in the sense that it is a NP-complete problem.

To prove it, let us reduce the undirected Hamiltonian cycle problem, one of Karp's 21 NP-complete problems, to the current problem by a polynomial-time reduction.

Let $G$ be an undirected graph with vertices $V$ and edges $E$. For each vertex $u$ in $G$, we create two new vertices, $u_{in}$ and $u_{out}$. Let $V_{in}=\{u_{in}|u\in V\}$. Let $V_{out}=\{u_{out}|u\in V\}$. Let $K$ be the complete bipartite digraph connecting the vertex sets $V_{in}$ and $V_{out}$. For every vertex $u\in G$, both edges $(u_{in},u_{out})$ and $(u_{out}, u_{in})$ in $K$ weigh 0. If edge $(u, v)$ is in $G$, then the both edge $(u_{out},v_{in})$ and edge $(v_{out},u_{in})$ in $K$ weigh $-1$. Any other edge in $K$ weigh $|V|$. $K$ with its edge-weights thus defined is a weighted complete bipartite directed graph with $|V|$ vertices in each of its two vertex sets (that is, $m=n=|V|$ for $K$).

Each simple cycle in $G$ corresponds to a simple cycle in $K$ with the same weight in the natural way as illustrated by the following example. A cycle $a, b, c, a$ in $G$ corresponds to the cycle $a_{in}, a_{out}, b_{in}, b_{out}, c_{in}, c_{out}, a_{in}$ in $K$. In particular, a Hamiltonian Cycle in $G$ corresponds to a simple cycle in $K$ of weight $-|V|$. Conversely, it is easy to see that a simple cycle of weight $-|V|$ in $K$ corresponds to a Hamiltonian Cycle in $G$ under the same correspondence. Note that a simple cycle of weight $-|V|$ in $K$ must be simple cycle of minimal weight in $K$.

Assume we can find a simple cycle $C$ of the minimal weight in $K$ by some algorithm. We can then check the weight of $C$. If the weight of $C$ is $-|V|$, the simple cycle in $G$ that corresponds to $C$ is a Hamiltonian Cycle. Otherwise, there is no Hamiltonian Cycle in $G$. So we have reduced the undirected Hamiltonian cycle problem to the current problem. We can see easily that this reduction is a polynomial-time reduction.


Program synthesis, decidability and the halting problem I was reading an answer to a recent question, and sort of a strange, ephemeral thought came to mind. My asking this might betray either that my theory chops are seriously lacking (mostly true) or that it's just too early for me to read this site. Now, with the disclaimer out of the way...

It is a well-known result it computability theory that the halting problem cannot be decided for TMs. However, this doesn't exclude the possibility that there exist machines that can solve the halting problem for certain classes of machines (just not all of them).

Consider the set of all decidable problems. For each problem, there exist infinitely many TMs which decide that language. Could the following be possible

There is a TM that decides the halting problem for a subset $S$ of Turing machines; and
All decidable problems are decided by at least one Turing machine in $S$?

Of course, finding the Turing machine in $S$ may not be computable itself; but we ignore that problem.

EDIT: Based on Shaull's answer below, it seems that either (a) this idea is too ill-specified to be meaningful or (b) my previous attempt wasn't quite on the mark. As I try to elaborate in the comments to Shaull's answer, my intent isn't that we're guaranteed that the input TM is in $S$. What I really meant by my question is whether there could exist such an $S$, such that membership in $S$ is a decidable problem. The program to solve the halting problem for $S$ would, presumably, write "invalid input" on the tape or something when given an input that it recognizes as not being in $S$. When I formulate it like that, I'm not sure whether this allows us to solve the halting problem or not, or whether Rice's theorem applies (is decidability a semantic property of a language w.r.t. Rice's theorem?)

I think there may be a problem with the formulation of the problem.

Consider the set $S=\{M: M $ is a decider of its language $\}$.
The halting problem is decidable for this set (that is, if we are promised that the input is in this set). In fact, it is trivial (the machines in $S$ always halt).

Also, clearly every decidable language is in $S$.

EDIT: Based on the changes in the question - indeed, membership in $S$ would be undecidable: if $S$ contains a machine for each decidable language, then $S\neq \emptyset$. Thus, by Rice's theorem, if $S$ is decidable then $S$ contains every machine, but then the halting problem is undecidable on $S$.


Why are we interested in square-free words? There is wikipedia page about square-free words, and there are a lot of theorems about these words, and examples of infinite square-free words.

I am wondering: why are we interested in these words?

Are there real-life applications of these words? Why are square-free words more useful to consider than other words?

Well, take a moment to reflect. Is a word or a string one of the most important and most common entities in this world? What are the most basic properties of a word or string?

its alphabet
its length
its sound
its meaning
its syntax or grammar
its origin
its usage as how to form sentences.
hmm, does it repeat part of itself? Or never (square-free)?

It looks like the property of being square-free is almost a fundamental property of a word (or a phrase, or a sentence).

In fact, it is amazing to me that the formal study of square-free words has not made it way into most of textbooks about the theory of automata and computation. It appears that the study of square-free words turns out to be a rather isolated field with less impact.

Nevertheless, the study of square-free words and related concepts is interesting and fruitful, as you have observed. I am, for one, charmed by the square-free words of infinite length over three letters 1.

"Real-life" application related to square-free words are sparse indeed. Abelian square-free words in algorithmic music by Laakso, T. might count as one; however, I cannot find that paper. (Gefwert, C., Orponen, P., Seppänen, J. (eds.) Logic, Mathematics and the Computer, vol. 14, pp. 292–297. Finnish Artificial Intelligence Society, Symposiosarja, Hakapaino, Helsinki).

Here are two related exercise to entertain your mind.

An abelian square is a subsequence of the form $s_1s_2$ where $s_2$ is a permutation of $s_1$. For example, $abcbac$ is an abelian square since $bac$ is a permutation of $abc$.

Exercise 1. (easy) Let the alphabet consist of 3 letters. Show a word of length 7 that is free of abelian square. Show that every word of length eight contains an abelian square.

Exercise 2. (very very hard) There is an infinite abelian-square-free word over an alphabet of size four.


Merging two complete heaps Suppose you have two heaps each containing $2^k - 1$ elements.

Design an efficient algorithm for merging these two heaps into a single heap.

My approach was to assume two heaps are maxheap. Create one node with value $-\infty$ and attach one heap as left subtree and another as right subtree, and call the heapify procedure. So it should take $O(\log(2(2^k-1)+1))=\log(k)$ time.

But my confusion is $-\infty$ valued node doesn't necessarily go at the last node of heap.

Calling heapify once isn't going to build a heap in one iteration  . Instead merge the two arrays which contain both heaps initially and call BuildHeap() procedure. You will get a heap in O(n) time.


Comparing $2^{F_n}$ and $2^{\varphi^n}$ if we define $F_n$ be the $n$th fibonacci number and $\varphi$ be golden number then can we say that

$2^{F_n} \in \Theta(2^{\varphi^n})$

or in other word

$2^{\frac{\varphi^n - (-\varphi)^{-n}}{\sqrt{5}}} \in \Theta(2^{\varphi^n})$

It's simple to show that $F_n \in \Theta(\varphi^n)$ but about above one I don't have any Idea

Hint: We have $F_n = [\varphi^n-(-\varphi)^{-n}]/\sqrt{5} = \varphi^n/\sqrt{5} \pm o(1)$, since $|1/\varphi| < 1$. Hence
$$ 2^{F_n} = 2^{\varphi^n/\sqrt{5}} 2^{\pm o(1)} = 2^{\varphi^n/\sqrt{5}} (1\pm o(1)). $$
In particular, $2^{F_n} = \Theta(2^{\varphi^n/\sqrt{5}})$. I'll let you compare $2^{\varphi^n/\sqrt{5}}$ and $2^{\varphi^n}$ yourself.


Who conceived the concept of Discrete Event Simulation, and when? I'm trying to trace back the origin of the general concept of Discrete Event Simulation and found a 1968 article by Fishman and Kiviat mentioning the term. It is titled The statistics of discrete-event simulation.

However, I'm unable to verify this as the origin of the term.

Is there further historical information on this?

Cornell's Conway, Johnson and Maxwell's paper Some Problems in Digital Systems Simulation, was published in 1959 in Management Science.  It discusses many of the key points of a discrete event simulation, including managing the event list (they call it an element-clock) and refer to "more efficient but more complicated methods" for locating the next event, but don't discuss the heap data structure.  This paper refers to earlier publications, but they don't seem to discuss the specifics of a discrete-event simulation like this paper does.


Lexicographically smallest down-right path in matrix Here is the problem which I thought was simple dynamic programming, which is however not the case.

Given an $N \times M$ matrix of numbers from 1 to $NM$ (each  number occurs only once), find a path from top left to right bottom while moving right or down only. If we sort all values visited in this path it should be lexicographically smallest.

I thought smallest sum path will be the answer, but it need not be true.

Every path must hit the top left and bottom right corners. Let $x$ be the minimal element among the remaining $NM-2$ elements. The lexicographically smallest path must go through $x$. If $x$ is at address $(i,j)$, this decomposes the original problem to two problems of the same form: one on an $i \times j$ matrix, and the other on an $(N-i+1) \times (M-j+1)$ matrix. (This requires a proof, but intuitively seems correct.)

To implement this algorithm efficiently, we need an efficient data structure for the two-dimensional range minimum query problem. Brodal, Davoodi and Rao give, in their paper On Space Efficient Two Dimensional Range Minimum Data Structures, a data structure that answers queries in $O(1)$ time, after $O(NM)$ preprocessing.

Actually, we need to find the minimum of a rectangle without two of its corners, but this domain can be written as the union of three rectangles, so such a query can also be answered in constant time.

Using such a data structure, we obtain an algorithm running in linear time $O(NM)$.

In fact, it suffices to use a much simpler data structure supporting one-dimensional range minimum queries; see Fischer, Optimal Succinctness for Range Minimum Queries for appropriate references. Suppose that $N \leq M$. Using a range minimum query data structure on each row, we can answer a two-dimensional range minimum query in time $O(N)$. Since the algorithm above makes only $O(N+M) = O(M)$ such queries, the overall complexity is still $O(NM)$.


Remove duplicated in array with best performance I am trying to remove duplicates from an array using the following two algorithms

   void PrintDuplicates(int[] arr)
   {
       if (arr == null)
           throw new ArgumentException("arr can't be null.");

       Hashtable table = new Hashtable();

       for (int i = 0; i < arr.Length; i++)
       {
           if (table.ContainsKey(arr[i]) == true)
           {
               // Console.WriteLine(i);
           }
           else
           {
               table.Add(arr[i], "");
           }
        }
    }

    void PrintDuplicatesWithSort(int[] arr)
    {
        if (arr == null)
            throw new ArgumentException("arr can't be null.");

        arr.ToList().Sort();

        for (int i = 0; i < arr.Length - 1; i++)
        {
            if (arr[i] == arr[i + 1])
            {
                // Console.WriteLine(i);
            }
        }
    }

Time complexity of the first algorithm to my understanding is O(n), while time complexity of the second is O(n) for sorting plus O(n-1) for the loop meaning total of O(2n-1).

However when I benchmark the code on this array int[] arr = { 4, 2, 5, 4, 1 }; the one with the higher complexity performs two times better. This implementation is using .net which uses insertion sort and implementation of hashtable that searches in O(1) according to their documentation. What am I missing here?

Sorting is $O(n\log n)$, not $O(n)$.

Also these are asymptotic bounds. Even if one algorithm is $O(n)$ and another is $O(n^2)$, it is possible that, for small-ish values of $n$ the second algorithm is faster.

More concretely, $f(n) = 1000 n$ is $O(n)$ and $g(n)=n^2/1000$ is $O(n^2)$, and both bounds are tight. Still, it will take a while for the first function to become smaller than the second one: for $n<1000000$ the second one is smaller.


Proving equivalence of two Turing machines I have the following Turing machine: A 2R-3L-TM is similar to a standard TM with the change in which the head can only move either 3 cells to the left or 2 cells to the right (those are the only possible moves).
and I want to prove equivalence between 2R-3L-TM and standard TMs (one tape and the head can move single cell right or left only). I only want to prove one side, meaning that for every standard TM M_1, there is a $2R-3L-TM, M_2, s.t L\left(M_1\right)=L(M_2)$. I started the proof on the right side but not sure how to prove the triple left side, my proof so far:
Let M2, a TM with 2R-3L, a set of states Q and transition function \delta. Let us define an equal standard machine, M2. We would do so by describing how TM M1 works in the implementation level:

If M1 moves to the right, do the same for M2 however mark the position with ‘ * ‘     transition to a new state at which the machine always moves to the right and then transitions to the original target of the RR transition
If M1 moves to the left...

How can I continue my proof and is my proof for the right side correct?

The main idea behind your proof is correct.
Note that (assuming the tape is infinitely sized on the right only) in the operator algebra of tape movements on the right-infinite tape we have identy $xR^kyL^kz = xyz$.
Using that we can prove:
$$R = R^4L^3 = (R^2)^2L^3$$
$$L = R^2L^3 $$
And since the right hand side consists only of unit moves in your model, you can do the effective moves on the left hand side. And you already know how, you replace every transition $T(x, S_i) = (y, S_o, m)$ where $m \in \{L,R\}$ with series
\begin{align}
&&T(x, S_i) &= (y, s_1(m), m'_1(m))\\
&\forall z\in \Sigma :\quad &T(z, s_1(m)) &= (z, s_2(m), m'_2(m))\\
&&&\cdots\\
&\forall z\in \Sigma :\quad &T(z, s_{k-1}(m)) &= (z, S_o, m'_k(m))
\end{align}
where $s_i$ are new temporary states and $m'_i$ are the appropriate series of moves from $\{R^2, L^3\}$.


Is "promoting a key" a part of deleting internal node key in B+ Tree? I was trying to learn B+ tree deletion operation and trying to contrast it with B tree deletion operation. However barely any book provided detailed step by step B+ tree deletion operation. So I was referring B+ tree key deletion from here.

The page says deleting 15 from this:

yields this:

Thus this somehow demotes key 13 to its right child and promotes key 11 to its parent. I do not find "promoting" any key specified in the B+ tree deletion algorithm given on the same page.

In step 4 of the B+ tree deletion algorithm on the same page, it says:

  If the node has too few keys to satisfy the invariant, and the next oldest or next youngest sibling is at the minimum for the invariant, then merge the node with its sibling; if the node is a non-leaf, we will need to incorporate the “split key” from the parent into our merging.

If I am not wrong, if we follow this step, it should yield something like this:

So is the example wrong? I am not able to confirm as I am not able to find precise step by step procedure. The steps given on this page sounds a bit fuzzy.

I'd not attach too much importance to such kind of boundary cases: both solutions here are valid according to the definition of B+-Tree and depending on the order of operations, it is very common that B-Trees have different shapes for the same data.  Here the difference between the two results is just the one between $<$ and $\leq$ in some condition and the choice is not imposed by an invariant of the data structure.

It seems to have a drastically different result because the tree is so close to be as sparse as possible and so close to be collapsible -- at most two more deletions will trigger that.  The reason is not that trees close to the boundary are typical, it is because making readable pictures is easier in that case, in practice the number of buckets per node is greater than 4 and fewer nodes are just half-full. Being able to steal one element from the neighbor is more typical than having to merge with it.

Obviously if you know something about the patterns of insertion and deletions, you may prefer one version over other, but it will be a second order effect.


Machine learning approach to auction game I am newbie with machine learning. In order to learn more I decided to try solving a specific problem/game that I have in mind. The problem is the following:

I have a list of $N$ items which are auctioned in a random sequence. There are $n$ participants to the auction. They have a fixed budget and $M$ items to buy. Each agent will decide whether to make a bid and how much to bid each time a new  item is auctioned; bids have to be integer numbers and the agent with the highest bid gets the item; correspondingly its budget is decreased of the amount of the bid. Items, once bought, cannot be released, so if an agent has already bought $M$ items, it cannot participate to other auctions. If nobody places a bid, the item is discarded and the auction continues with the next one. Thus, an agent ends its auction if it has bought $M$ items or the available budget has reached $0$.

At the end, the value of the final set $I$ of items items bought by each agent is evaluated by an external oracle function $f(I)$.  The function is not explicitly known and will in general be more complicated that the sum of values of each item, e.g. two items may be essential parts of a single object and are worthless one without the other. However, it is known that
$$ f(I \cup J) \geq f(I) + f(J).$$
Each agent is free to evaluate the function $f$ on any set of items.  Each agent's goal is to maximize the value of $f(I)$, where $I$ is the set of items successfully bought by that agent.

Which strategy would you suggest to approach this problem?
At each time, the agent has information about the list of items that have been auctioned, which participant has bought each of them and the costs, so that it knows the number of available slots and budget of each participant. According to these data, it must decide if and how much to bid for each item. Note that the list of items is fixed and the function $f$ are fixed.
I suppose this is a reinforcement learning question but I don't have a clear understanding of how the input would be structured in this case.

There probably is no solution that will be optimal for all possible situations.  So, you are left with heuristics: trying to find a technique that will often work well in the situations that arise for you in practice, but with no guarantees that it will work for everything.  Machine learning might be one possible such approach.

You might start by trying to learn the function $f$.  You said that the agent is free to invoke $f$ on any set of items.  Therefore, a possible starting point is to try to learn a model that predicts $f$: e.g., given a representation of the set $I$, outputs an estimate for $f(I)$.  You can easily collect a training set by querying $f$ on many sets and observing its output.

Reinforcement learning would be a plausible approach to the broader problem.  There are many approaches to reinforcement learning, but in one typical approach, we need to compute a function $V(a)$ that computes the anticipated value of being in state $a$ (i.e., if the agent is in state $a$ and then follows its policy/strategy, what do we expect the final value of $f(I)$ will be?).  Normally machine learning techniques are used to build a model that estimates the value of $V(a)$.  This then requires forming a representation of the state $a$, i.e., a feature vector that summarizes or extract relevant information about the current state.  The current state includes: (a) the set of items bought by this agent so far, (b) the budget and number of slots available to this agent, (c) the number and list of items remaining to be bought, and (d) information about the other agents, including what they've bought so far and the number of slots and budget remaining to them.  So, you can think about how to build a feature vector that represents them, then apply standard methods for reinforcement learning to learn the function $V(a)$.

I suggest reading a tutorial on reinforcement learning to learn more about how it works and see some examples in a simpler setting.


Is a set of TM deciding specific length of language reducible? For instance, if we know a language $L_1 =  \{ \langle M \rangle \mid ~ \lvert L(M) \rvert = n \} $ is decidable, can we prove that $ L_2 =  \{ \langle M \rangle \mid ~ \lvert L(M) \rvert = n-1 \}$ is also decidable? In other words, prove $L_2$ reduces to $L_1$.

Here is a similar example, to get you started. Let $L_n$ consist of all encodings of Turing machines that accept some string of length $n$.

Claim: $L_{n-1}$ reduces to $L_n$.
Proof: Let $M$ be an input to $L_{n-1}$. Construct a new machine $M'$ which on input $x$, if $x$ starts with a zero then $M'$ rejects, and if $x=1y$ then $M'$ simulates $M$ on $y$. Then $\langle M \rangle \in L_{n-1}$ iff $\langle M' \rangle \in L_n$ (exercise).

Your proof will be different, but the proof technique will be similar.


Method for finding Hyperrectangle that a coordinate is within I have a problem at work where I have set of hyperrectangles, in no particular order, that do not overlap and when unioned create a hyperrectangle with no gaps. At the moment I am looking for a way to efficiently figure out which hyperrectangle a given coordinate is within.

I do not always have too many hyperrectangles, so just iterating through the set of partitioned hyperrectangles is often fine to see which one a given coordinate is in. However, I sometimes have larger quantities of hyperrectangles and I want to write something that scales better than simply iterating through the set.

My first thought is to consider some hashing approach analogous to spatial hashing but am not sure the best way to go about formulating this since the hyperrectangles could be any dimension. Any thoughts?

The best algorithm will depend on the proportion of hyperrectangles to dimensions. If I understand correctly, what you want is to do a first-pass computation where you build a data structure in order to get a sublinear algorithm (in terms of the number of hyperrectangles) that will tell you which hyperrectangle a point is in.

I think a binary search tree would work well. At each branch of the tree you can split the set of hyperrectangles in half by performing a check to see if coordinate X_i is greater than or less than some value. You want to include in each set every rectangle that is at least partially inside the split region. For example, if you have a rectangle from (0,0) to (2,2) and you split on the first coordinate at 1, you would want to include this rectangle in both sets. Continue until you have only single hyperrectangles - these will be the leaves of the tree.

How and when you split is up to you. Each time the number of hyperrectangles on both sides should be roughly equal. An approach where you just cycle through the dimensions would probably work well. For example, first you split halfway along X_1, then halfway along X_2, ... eventually you split halfway along X_d, then you start over if necessary.

If n is the number of hyperrectangles, then the construction step should take about O(n*log(n)), and the lookup step should take about O(log(n)) each time.


Length of longest arithmetic progression in an array I was reading an article on Longest Arithmetic Progression. The solution given has S(n)=$O(n^2)$. Can't I solve it in $O(1)$ space? To find the three elements, we first fix an element as middle element and search for other two (one smaller and one greater). When we found them we still keep on decreasing left and right to find llap (length of longest arithmetic progression). The other cases left are those where llap is even.. for them I will select i and (i+1)$^{th}$ element as my center two elements of AP and find elements on their right and left satisfying ap. T(n) will still be $O(n^2)$.

Is my approach correct?

No, your approach is wrong. Consider the set of numbers $1, 3, 4, 6, 7, 8, 10$. The longest arithmetic progression(LAP) in it is $1, 4, 7, 10$, which is of even length. However, 4 and 7 are not adjacent items so your approach will not find that LAP.

Yes, your approach is correct, but to a different problem from the problem in the article you mentioned.


Equality testing of arrays and integers in a procedural language In terms of references and their implementation on the heap and the stack, how is
equality testing for arrays different from that for integers?

This is to do with Java programming, if you have a stack and a heap, would equality testing for example j == i be the same for arrays and for integers? I understand that arrays, are stored in the heap and the stack, as it holds bulks of data, but integers are only stored in the stack and referenced in the heap.

I understand for equality testing j==i (variables) the stack pointer will point to the same location.

I'm confused on how j==i would be different for array and integers.

Could someone explain?

Integers are stored in one word of memory and there is a primitive machine code instruction for testing their equality. Most programming languages lift this instruction to the syntax, as with i == j in Java (where i and j are of type int).

Arrays are stored in multiple contiguous words in memory. In order to test the equality of two arrays, the program needs to iterate through each pair of  memory locations and test the equality of the elements stored in them.

Some programming languages hide the distinction between these to operations by allowing the syntax == to be used for testing the equality of two arrays (one can do this in C++, for instance, or Ruby). Other programming languages, such as Java, do not.


Ordering the incident edges of each vertex to have a specified pre-order traversal Input: You are given a graph $G(V, E)$ undirected, loop-less, no parallel edges, etc. and a label function $L: V \to \mathbb{N}$. Also, a sequence of $|V|$ natural numbers is given.

Output: Is it possible to order the incident edges set of each vertex and choose a starting vertex $s \in V$ so that a pre-order DFS traversal starting from $s$ prints out a sequence of labels of visited vertices which matches the given sequence.

Any idea on this problem? It is solvable on trees by Dynamic Programming. But for general graph, it seems to be much harder.

We reduce from Hamiltonian cycle. Given a graph $G$, we construct new labelled graph as follows:

Label each vertex of $G$ by $\mathrm{A}$
To each vertex of $G$ connect it with a hanging vertex "above" it and label this vertex by $\mathrm{F}$
For each edge $e$ of $G$, add a "middle" vertex labelled by $\mathrm{K}$, and connect each "middle" vertex to the two $\mathrm{F}$ vertices above the two $\mathrm{A}$ end points of its corresponding edge.

The sequence will be $\mathrm{AFKAFK}\dots\mathrm{AFK}$$KKK..\dots KKK$ where we repeat the pattern $\mathrm{AFK}$ the number of times equal to the number of vertices of $G$, i.e. $|V(G)|$. And the number of trailing $\mathrm{K}$ (written in italic for clarity) equals $|E(G)|-|V(G)|$, i.e. after finishing the Hamiltonian cycle, the traversal needs to come back and collect the remaining "middle" vertices.

If $G$ is Hamiltonian, clearly we can order the neighborhood of each vertex so that the edge that will be taken at each vertex is in accordance with the Hamiltonian cycle.

Conversely, if we can order the neighborhood of each vertex and choosing a string vertex so that the preorder traversal prints out the required sequence then we can follow the path delineated by the traversal to figure out the Hamiltonian cycle. Indeed, if at some point you get stuck, then there would be the very FIRST time you get stuck somewhere. But clearly, if so, you need to produce a $\mathrm{KK}$ before the trailing "garbage" sequence begins. In short, you cannot get way back and branch (at least for the FIRST time) without printing out a $\mathrm{KK}$.


What is the fastest addition algorithm on a turing machine? What's the asymptotic running time of the fastest algorithm for adding two $n$-digit decimal numbers on a Turing machine? To specify, the input is of the form $a_1+a_2$ where $a_1$ and $a_2$ are written out in the usual decimal expansion, and the output on the tape is just the result, $a_1+a_2$ (there is no need to keep the inputs). The best I can do so far is $O(n^2)$ time using this program I made: http://morphett.info/turing/turing.html?185f35a035e386d2a927c15b869b422a

The way this algorithm works is by finding the rightmost "non-added" digit of the number to the right of the addition sign (henceforth No. 2), marks this with an "o", and moving left until it finds a "non-added" digit of the number to the left of the addition sign (henceforth No. 1) and marking the result with a letter so that the machine will know how many decimal places to go to the left when adding next time. If there are any carries, these places are marked with numbers rather than letters because they haven't been 'reached' yet other than by the carry. The machine ends when all the digits on the right-hand number have been turned into "o"s and the machine encounters the plus sign instead of a number. Then, it cleans up all the "o"s and transforms all the letters into numbers and deletes any 0's at the beginning of the number.

I won't provide a rigorous proof, but this algorithm can be seen to be $O((n_2)^2)$ time complexity intuitively by the fact that for each digit in No. 2, the turing machine has to move about $n_2$ (which I use to denote the length of $a_2$) steps to the left, and since there are $n_2$ digits in No. 2, this algorithm takes about $n_2\times n_2=(n_2)^2$ steps. (Thus it runs in $O(n^2)$ time, assuming both numbers are of the same length, $n_1=n_2=n$). This improves on the naïve exponential time implementation of just subtracting one from No. 2 and adding one to No. 1 until No. 2 is exhausted, but is there any faster algorithm?

EDIT: Just to clarify I want the fastest algorithm for adding two decimal numbers of equal length, $n$. I use $n_1$ and $n_2$ as the lengths of $a_1$ and $a_2$ respectively only to emphasize that the algorithm is technically only quadratic in $n_2$, which is where it gets the $O(n^2)$ runtime from. I tried calculating the exact number of steps the algorithm takes, which is $n_1+2(n_2)^2+5n_2+max(n_1,n_2)+5+2c+d$, where c is the number of carries (bounded by $n_1$) and d is the number of digits in the result. Thus, a more precise runtime would be $O((n_2)^2+n_1)$, but left this out for conciseness and because in the end I only cared about the case $n_1=n_2=n$.

(This should be a comment but I can't comment yet)

Just to clarify, when you have an integer $n$, it's represented on $\operatorname{size}(n)=\log_2 n$ bits.

So here, you are given $n_1$ and $n_2$ and you want to compute $n_1+n_2$. Let $f(n_1, n_2)$ be the number of steps needed to compute that. You seem to be claiming that $f(n_1, n_2)=O\left((n_2)^2\right)=O\left(\left(2^{\operatorname{size}(n_2)}\right)^2\right)$, which is obviously false. Now if you change it to $f(n_1, n_2)=O\left((\operatorname{size}(n_2))^2\right)=O\left((\log_2 n_2)^2\right)$, it becomes a little bit more plausible.

But that still can't be the complexity because if you have $n_1=2^{k}-1$ and $n_2=2^0$, your algorithm will at least read $n_1$, which takes $O\left(\operatorname{size}(n_1)\right)=O\left(\log_2 n_1\right)=O(k)$ while $O\left((\log_2 n_2)^2\right)=O(1)$ in these cases. The complexity should depend on the size of $n_1$ one way or another.


Context-free grammar for ${a^n b^n a^n}$ I am trying to figure out a formal grammar for the above language. This language describes palindromes, so it is context-free, if I am not wrong. I came up with a context-sensitive grammar, but I can not find a context-free one. Any ideas?

The languages of all palindromes  is context-free.

That does not implies that any language that contains only palindromes is context-free. For example, many language over the unary alphabet $\{a\}$ are not context-free. In fact, they can even be non-context-sensitive or undecidable. Note that any word over a unary alphabet is a palindrome.

In particular, the language of all words like $a^nb^na^n$ is not context-free. The rough intuition to understand why it is not context-free is that a PDA cannot remember two unbounded independent relations. You can either use the pumping lemma to prove that fact.

Exercise. Give an example of a unary language that is not context-free.


Model for diurnal nature of data I have a timeseries dataset of a quantity measured over the period of a week. I want to verify if the data is varying in a diurnal fashion with the help of some mathematical measure. Does any such measure exist?

If you want to find periodic behaviors of your data, you should use the Fourier transform, which decomposes your data into a linear combination of cyclic waveforms. If you have a guess on the actual period, as in your case, you can try something simpler. For each hour during the day, compute the mean $\mu$ and variance $\sigma^2$ of your data, and plot the intervals $[\mu-\sigma,\mu+\sigma]$ for each hour. That should give you an idea regarding your hunch. (More generally, you can try a sophisticated method like ANOVA.)

Perhaps you should ask your question over in stats.se.


Numerical Accuracy & Sorting Algorithms? Sedgewick and Wayne talk about how sorting algorithms and, specifically, priority queues are used in devising ways to improve accuracy in floating-point calculations: https://algs4.cs.princeton.edu/25applications/

  Scientific computing is often concerned with accuracy (how close are we to the true answer?). Accuracy is extremely important when we are performing millions of computations with estimated values such as the floating-point representation of real numbers that we commonly use on computers. Some numerical algorithms use priority queues and sorting to control accuracy in calculations.

What "numerical algorithms" use priority queues and sorting like this?

I'll give you a simple example.

Suppose you have some floating-point numbers to add together. We'll assume they're all non-negative so that cancellation isn't an issue.

For the purpose of this example, I'm going to use decimal with four significant digits of precision just to illustrate the point.

The numbers are:

1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e+0

That is, ten copies of 1e-4 and one copy of 1.

This sum can be perfectly represented in our toy floating-point format:

1.001e+0

But the answer that you get depends on what order you do the additions! If you start at the top of the list and work your way down, the partial sums are:

1.000e-4
2.000e-4
3.000e-4
4.000e-4
5.000e-4
6.000e-4
7.000e-4
8.000e-4
9.000e-4
1.000e-3
1.001e+0

But if you start at the bottom and work your way to the top, the partial sums are:

1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0

Clearly, you need to add the small numbers first. So here are two possible algorithms.

Sort the numbers into ascending order, then sum them in that order.
Insert the numbers into a priority queue. Remove the two smallest numbers, add them, and insert the sum back into the priority queue. Repeat until there is one number left.

Exercises:

Is there a set of numbers for which these two algorithms return different answers?
Is one of these algorithms better than the other, in the sense of always returning a more accurate final answer?
Can we do even better?


What exactly is execution-time address binding? According to these two definitions:

Logical address: every memory address generated by the CPU.

Physical address: address which identifies uniquely a (real) memory cell.

my textbook (Operating systems concepts - Silberschatz, Galvin, Gagne) says that address binding at compile-time and load-time both generate identical logical and physical addresses, while execution-time binding produces different logical and physical address.
I've googled a lot, but every article which tries to explain this concept is not that clear. I can't understand what happens in the practice. I'll give you an example to let you understand what I mean:
The source code (high-level language instructions) contains symbolic addresses (like count) that are replaced (by the compiler) by:

physical addresses (compile-time binding) if the location in memory of the process can be known in advance (non-multi-programmed systems);
relocatable addresses (load-time binding) in the opposite case (most common).

Once the loader puts the obj into memory it replaces relocatable addresses with physical addresses (if there are any) and the program can be finally executed. The CPU can read and refer to physical addresses, so logical and physical addresses are the same. In both previous cases the binding is static: once loaded, the process can't be moved from one segment of memory to another.
In order to manage the memory in an efficient way, the system should be able to move a process from a location of the memory to another: this means that the process physical addresses can change at run-time. In order to implement this mechanism logical addresses and physical addresses must be different: logical addresses can change in an interval [0, max] and physical ones between [r, r+max], where r is the relocation register.
Does this mean that, in execution-time binding, the obj file contains virtual addresses ([0, max]), which are converted time by time by the system into physical ones? In other words, is true that the obj file doesn't contain any physical address (but a data structure of the OS keeps the informations about the process address binding) so each time the CPU reads (for example) ADD 100 105 the addresses 100 and 105 are converted into physical ones by the system (using MMU and data structures)?
Please correct any mistake I made, the textbook is not so clear.

Until the program is running, physical addresses make little (or no) sense: The instructions make reference to logical addresses.
While the program runs, the CPU maps logical addresses to physical addresses (they could be just exactly the same, or change e.g. by paging or just by relocation --- add the contents of a special register to each logical address to give the pysical address, used in some early machines to be able to place several programs tightly in memory and be able to move them around). If you look e.g. at the intel 8088/8086 (infamous CPUs for the original PC), it sports segment registers, so you can move say the stack around in RAM and the program doesn't care where it is.


Counterexample to this modified Dijkstra's In class, we were given the following problem:

  We are given a directed graph G = (V, E) on which each edge (u, v) ∈ E has an associated
  value r(u, v) which is a real number in the range 0 ≤ r(u, v) ≤ 1 that represents the reliability
  of a communication channel from vertex u to vertex v. We interpret r(u, v) as the probability
  that the channel from u to v will not fail, and we assume that these probabilities are
  independent.
  Give an efficient algorithm to find the most reliable path between two given vertices.

My answer was to run Dijkstra's shortest path algorithm taking (1 / r(u,v) ) as the weight for each edge, which is wrong. The standard solution to this problem is to take the -log(r(u,v)) when running Dijkstra's algorithm. I understand why the standard solution is correct as it exploits the log's property where: log(a*b) = log(a) + log(b) to convert the problem from maximizing the product to minimizing the sum of the logs. However, what is an example of a graph where taking the inverse of the reliability would not produce the optimal result? My thinking was that any function that maps smaller fractions to bigger numbers could be used.

Your algorithm makes the wrong choice between the following two paths:

5 channels with a reliability of 50% (combined reliability 3.125%), weight $5 \cdot {1 \over 0.50} = 10$.
A single channel with a reliability of 8%, weight ${1 \over 0.08} = 12.5$.


What exactly is the semantic difference between set and type? EDIT: I've now asked a similar question about the difference between categories and sets.

Every time I read about type theory (which admittedly is rather informal), I can't really understand how it differs from set theory, concretely.

I understand that there is a conceptual difference between saying "x belongs to a set X" and "x is of type X", because intuitively, a set is just a collection of objects, while a type has certain "properties". Nevertheless, sets are often defined according to properties as well, and if they are, then I am having trouble understanding how this distinction matters in any way.

So in the most concrete way possible, what exactly does it imply about $x$ to say that it is of type $T$, compared to saying that it is an element in the set $S$?

(You may pick any type and set that makes the comparison most clarifying).

To understand the difference between sets and types, ones has to go back to pre-mathematical ideas of "collection" and "construction", and see how sets and types mathematize these.

There is a spectrum of possibilities on what mathematics is about. Two of these are:

We think of mathematics as an activity in which mathematical objects are constructed according to some rules (think of geometry as the activity of constructing points, lines and circles with a ruler and a compass).
Thus mathematical objects are organized according to how they are constructed, and there are different types of construction. A mathematical object is always constructed in some unique way, which determines its unique type.
We think of mathematics as a vast universe full of pre-existing mathematical objects (think of the geometric plane as given). We discover, analyze and think about these objects (we observe that there are points, lines and circles in the plane). We collect them into set. Usually we collect elements that have something in common (for instance, all lines passing through a given point), but in principle a set may hold together an arbitrary selection of objects. A set is specified by its elements, and only by its elements. A mathematical object may belong to many sets.

We are not saying that the above possibilities are the only two, or that any one of them completely describes what mathematics is. Nevertheless, each can view can serve as a useful starting point for a general mathematical theory that usefully describes a wide range of mathematical activities.

It is natural to take a type $T$ and imagine the collection of all things that we can construct using the rules of $T$. This is the extension of $T$, and it is not $T$ itself. For instance, here are two types that have different rules of construction, but they have the same extension:

The type of pairs $(n, p)$ where $n$ is constructed as a natural number, and $p$ is constructed as a proof demonstrating that $n$ is an even prime number larger than $3$.
The type of pairs $(m, q)$ where $m$ is constructed as a natural number, and $q$ is constructed as a proof demonstrating that $m$ is an odd prime smaller than $2$.

Yes, these are silly trivial examples, but the point stands: both types have nothing in their extension, but they have different rules of construction. In contrast, the sets
$$\{ n \in \mathbb{N} \mid \text{$n$ is an even prime larger than $3$} \}$$
and
$$\{ m \in \mathbb{N} \mid \text{$m$ is an odd prime smaller than $2$} \}$$
are equal because they have the same elements.

Note that type theory is not about syntax. It is a mathematical theory of constructions, just like set theory is a mathematical theory of collections. It just so happens that the usual presentations of type theory emphasize syntax, and consequently people end up thinking type theory is syntax. This is not the case. To confuse a mathematical object (construction) with a syntactic expression that represents it (a term former) is a basic category mistake that has puzzled logicians for a long time, but not anymore.


Can a regular expression be infinite? I know that  languages which can be defined using regular expressions and those recognisable by DFA/NFA ( finite automata ) are equivalent. Also no DFA exists for the language $\{0^n1^n|n \ge 0\}$. But  still it can be written using regular expressions ( for that matter any non-regular language can be ) as $\{ \epsilon \} \cup \{01\} \cup \{0011\}......$ . But we know that every language that has a regular expression has a DFA that recognises it ( contradiction to my earlier statement ).
I know this is a trivial thing, but does the definition of regular expression includes the condition that it should be finite ?

If regular expressions were allowed to be infinite, then any language would have been regular.

Given the language $L=\{w_1, w_2, \ldots\}$, we can always define the regular expression $R = w_1 + w_2 + \cdots$, which exactly defines $L$.
(Example: the regular expression $R_1 = \epsilon+0+1+00+01+10+11+\cdots$ defines $L_1=\{0,1\}^*$.)

We know that some languages are not regular, so this shows that infinite regular expressions describe a larger class of languages than finite regular expressions.


Are regular grammars always LR(1) The question is fairly straight forward. I just found a question on the internet that asks whether all regular grammars are

LL(1)
LR(1)

I guess they can't be LL(1) because of left recursion, but how do we prove that they are LR(1) if so.

No.

LR(k) grammars have to be unambiguous, that is there can be only one possible parse tree for every (valid) input. There are left- and right-regular grammars violating that, for example

$\displaystyle\qquad S \to aS \mid aaS \mid a$

or, if that one does not match your definition of right-regular,

$\qquad\displaystyle\begin{align}
  S &\to aS, S \to aA, \\
  A &\to aA, A \to a
\end{align}$

as reinierpost mentions in a comment.

Of course, every regular language does have an unambiguous (right-)regular grammar; get one from its minimal DFA using the standard construction.


Decision tree lower bound for finding two array elements summing to zero I have to solve this exercise:

  Given an unordered array $A[1], \ldots, A[n]$ of positive and negative integers,
  determine if there are two indices $i \neq j$ such that
  $A[i] + A[j] = 0$. Establish a lower limit to the problem using the
  decision tree technique.

The solution should be $Ω(\log s(n))$, where $s(n)$ is number of possible solutions, in this case $n^2$.

But, I don't understand why the number of possible solutions is $n^2$ rather than $\binom{n}{2}$.

You're right that there are only $\binom{n}{2}$ many inequivalent solutions. Fortunately, $\Omega(\log \binom{n}{2}) = \Omega(\log n)$, so there isn't much difference between $\binom{n}{2}$ and $n^2$, in this regard.

However, this is a pretty bad lower bound. You haven't specified which queries are allowed, but assuming you're allowed to compute signs of constant degree polynomials, then I would expect an $\Omega(n\log n)$ lower bound, since the similar problem Element Distinctness has such a lower bound. This also matches the upper bound obtained by sorting (assuming your model supports this).

Indeed, this is just 2SUM (a sibling of the more famous 3SUM problem), and an $\Omega(n\log n)$ lower bound was proved by Chan, Gasarch and Kruskal in their paper Refined Upper and Lower Bounds for 2-SUM.


Complexity of Monotone (+,2) SAT problem? To continue this post, let us define the Monotone$(+, 2^-)$-SAT problem:

Given a monotone CNF formula $F^+$, where each variable appears exactly once (as a positive literal), and a monotone 2-CNF formula $F_2^-$ defined on the same variables as $F^+$, where all variables are negated. Is $F^+ \land F_2^-$ satisfiable ?

Is this problem NP-complete?

This is NP-complete.  In fact, it remains NP-complete when $F^+$ is restricted to be in 3-CNF form (not just CNF).

The proof is by demonstrating that this problem is at least as hard as testing 3-colorability of a graph.  The correspondence is clean and elegant.  Let $G=(V,E)$ be an undirected graph.  Introduce variables $x_{v,c}$, for $v \in V$ and $c \in \{1,2,3\}$, to represent a 3-coloring of the graph.  Here $x_{v,c}$ means that we've given vertex $v$ the color $c$.

To represent that each vertex must receive at least one color, we will introduce clauses $x_{v,1} \lor x_{v,2} \lor x_{v,3}$ for each vertex $v$.  This gives us $F^+$, i.e.,

$$F^+ \equiv \bigwedge_{v \in V} (x_{v,1} \lor x_{v,2} \lor x_{v,3}).$$

To represent that no two endpoints of a single edge may receive the same color, we will introduce a clause $\neg x_{u,c} \lor \neg x_{v,c}$ for each edge $(u,v) \in E$.  And, to represent that no vertex may receive more than one color, we will introduce a clause $\neg x_{v,c} \lor \neg x_{v,c'}$ for each $c,c' \in \{1,2,3\}$ such that $c\ne c'.$  Let $F^-_2$ denote the corresponding formula.

$$F^-_2 \equiv \bigwedge_{(u,v) \in E} (\neg x_{u,c} \lor \neg x_{v,c}) \; \;  \land \bigwedge_{v \in V,c\ne c'} (\neg x_{v,c} \lor \neg x_{v,c'}).$$

Then it is easy to see that $F^+ \land F^-_2$ is satisfiable if and only if $G$ has a 3-coloring.  In fact, each satisfying assignment of $F^+ \land F^-_2$ corresponds immediately to a 3-coloring of $G$, and vice versa.  Therefore, testing the satisfiability of this class of formulae is at least as hard as testing 3-colorability of an undirected graph, so it is NP-hard.


Which number representation takes the largest amount of memory? Options are:

Signed magnitude
One's complement
Two's complement
Excess notation

This is the question from an 'example of a previous exam' I've been given at university. Answers were not provided.
As far as I understand only one answer must be chosen, but I'm not seeing which one.

My attempt at solution
As we see from Signed number representations  wikipedia article, both 1. Signed magnitude and 2. One's complement can be chosen as representations requiring the largest amount of memory, because they take up space for both negative and positive 0 (unlike 3. Two's complement and 4. Excess notation).
Is this reasonable, can we say that both 1. and 2. should be chosen as answers here despite question requiring only one answer?

The question seems rather bizarre.

Using n bits, each representation can represent $2^n$ different values. Two of them have different representations for +0 and -0. I would assume that signed-magnitude and one's complement are used if someone values the ability to distinguish +0 and -0.

If the question was "which representation takes the largest amount of memory", then that question is already nonsense because no matter what you think about +/- 0, one's complement and signed magnitude are the same. If the question was "which representations take the largest amount of memory", then I'd still say that claiming one (or two) take more than the others is very misguided.

(And the number $-2^{n-1}$ that can be represented with n bits two's complement or signed magnitude has its own problems where both negation and division can lead to overflow).


How to calculate the weight between neurons in ANN? I am currently learning Supervised ANN training using Backpropogation and I am stuck in this exercise. I calculated the δA using the equation at the bottom of the screenshot, however, I am unable to calculate δB because the weight of BD is not given. How do I find the weight of BD?

As far as I can tell, the information provided does not appear to be enough to answer your question, though I confess I am not familiar with what a "unipolar continuous threshold function" is, and it is not clear to me what $f(\text{net}_A$) represents nor what the loss function for this task is.  You might need to talk to your instructor or wherever you got that image from.  You might ask them what a "-" over an edge means.


recursive language and computable function Question: Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^{*}$ to $B^{*}$. We say $f$ is computable if there exists a Turing machine $M$ which given an input $x \in A^{*}$, always halts with $f(x)$ on its tape. Let $L_{f}$ denote the language $\Bigl \{x\# f(x) \mid x\in A^{*} \Bigr \}$. Which of the following statements is true:

(A) $f$ is computable if and only if $L_{f}$ is recursive.

(B) $f$ is computable if and only if $L_{f}$ is recursively enumerable.

(C) If $f$ is computable then $L_{f}$ is recursive, but not conversely.

(D) If $f$ is computable then $L_f$ is recursively enumerable, but not conversely.

My Attempt:

if $f$ is computable then given $x$ on tape of TM, it will always halt in $f(x)$ on Tape.

$L_f$ denote the language $\Bigl \{x\# f(x) \mid x\in A^{*} \Bigr \}$, which means $L_f$ strings of type which has image and pre image to left and right of $\#$.

Now consider a function $f(x)$ is computable and its corresponding language $L_f$, will $L_f$  be recursive ? (given that $f(x)$ is computable )

Yes, $L_f$ wil be recursive if $f(x)$ is computable. Because if $x\# f(x)$ is given then i will first convert $x$ in $f(x)$ (i can do it because $f(x)$ is computable ) this gives me $f(x)\# f(x)$ on table and i just left to match left strings to the right string of $\#$ .

Now consider a function $L_f$  is recursive, will $f(x)$ be computable ?
(i need exlanation of this part)

The question is about the relation between a computable function $f$ and its graph (here denoted by $L_f$).
Since the function is total, the function is computable if and only if its graph is recursive (in case $f$ is a partial computable function, $f$ is computable if and only if its graph is r.e.).

So, your guess is right, and the correct answer is A.
To compute $f$ from the characteristic function of the graph, you need to use a generate and test technique, progressively trying all possible outputs y for a given input x (using the characteristic function as tester), until you find the correct pair x#y. Since such a pair must exist, your algorithm is terminating.


Finding $c$ and $n_0$ for a big-O bound A book I am reading demonstrates how $5n^3 + 2n^2 + 22n + 6 = O(n^3)$, which I believe is true. After all, there exists a value $c$ for which $cn^3$ is always greater than $5n^3 + 2n^2 + 22n + 6$ for all $n$ greater than or equal to some value $n_0$.

However, the book then casually notes that $c = 5$ and $n_0 = 10$. Where did these values come from? What algebraic calculations were done (if any) to derive the $c$ and $n_0$ values?

$c=5$ is clearly the wrong answer, since for any $n$,
$$cn^3 < 5n^3 + \text{(positive terms)}$$

However, if we take $c>5$ then there will exists some $N_0$ such that for $n>N_0$
$$cn^3 \ge 5n^2+2n^2+22n+6$$

If we let  $g(n)=(c-5)n^3-2n^2-22n-6$, then Since $\lim_{n\to\infty} g(n)=\infty$,  by the limit definition there always exists $N_0$ such that for any $n>N_0$, $g(n) >0$. This implies the above claim.

To find that $N_0(c)$ you can try to find the roots of $g(n)$. $N_0$ will be the most positive root.


Encoding two 6-bit positive integers compactly Is it possible to encode two 6-bit wide positive integers a and b guaranteed to be in [0, 63] in a way that a and b are recoverable -- in fewer than 12 bits? We could obviously concatenate the binary representations (a << 6 | b). The scheme would have to allow any two arbitrary values within the given range. Can we do better than 12 bits?

Suppose that $H\colon \{0,1\}^6 \times \{0,1\}^6 \to \{0,1\}^n$ is such that $a,b \in \{0,1\}^6$ can be recovered from $H(a,b)$. In particular, $H(a,b) \neq H(c,d)$ whenever $(a,b) \neq (c,d)$. Since there are $2^{12}$ possible inputs, and the value of $H$ on each of them is different, it follows that the range of $H$ must consist of at least $2^{12}$ different points. Since $\{0,1\}^n$ has $2^n$ points, we conclude that $n \geq 12$.


Is there an algorithm to find out if a truthtable can be represented as 2-sat, and if so find its 2-cnf? I know that not all truthtables have a corresponding 2-cnf representation, but is there a way to find out if a given truthtable has a 2-cnf representation, and if so to find what that is?

This answer assumes that a 2CNF representation of a function is a 2CNF (on the same set of variables) that agrees with the function on all inputs.

Let's say that a clause $C$ is consistent with a function $f$ if $\lnot C \Rightarrow \lnot f$. Let $C_1,\ldots,C_m$ be the collection of 2-clauses consistent with your function $f$. Then $f$ has a 2CNF representation if and only if $f = C_1 \lor \cdots \lor C_m$. This gives a quasilinear time algorithm for deciding whether $f$, given as a truth table, has a 2CNF representation.


Does proofs are programs apply to any functional program? Does Curry howard correspondence, apply to all Functional Program, e.g. in Haskell. i.e. Is it possible to write Equivalent Haskell programs, to COQ proofs?

In Haskell there are more programs than there are Coq proofs because Haskell has general recursion whereas Coq does not. (In fact Coq allows you to extract proofs into Haskell code.)

The reason that Coq does not have general recursion is that with it we can "prove" anything, simply by saying "to prove $t$ just make a recursive call to itself":

proveAnything :: t
proveAnything = proveAnything

In some languages, for instance in OCaml, you can't do it this way so you have to go indirectly through a recursive function call:

let rec proveAnythingAux _ = proveAnythingAux ()
let proveAnything = proveAnythingAux ()

This shows that type theory can be used for many things, two of which are programming and logic. The difference between these two is general recursion: we want it in programming but it makes logic inconsistent.