title: how pseudo direct addressing works?

text:
# Question
Title: how pseudo direct addressing works?
In pseudo direct addressing mode (For the MIPS architecture) the 26 bit of the jump instruction are joined to the upper 4 bits of the PC .

* how could this help in jumping to relative positions suppose I want to jump backward instead of forward ( i.e. if i want to jump to the beginning of a loop after executing it's body ),
* What I get is this will limit the jump to be 2^28 from the following instruction but Is this applicable backward too ? I am really confused by this so excuse me for such a silly question...

# Answer
> 2 votes
Pseudo direct addressing is not intended for relative jumps. It is an absolute jump. If you want a relative jump, don't use pseudo direct addressing.

It's not correct that the limit is $2^{28}$ past the current address. Suppose the current address is 0x183020C0 (to give an example). Then pseudo direct addressing will allow jumping to any address in the range 0x10000000 - 0x1FFFFFFC. Notice that this is up to 0x083020C0 backwards and up to 0xF7CFDF3C forwards from where you currently are; but crucially, those values depend on the current PC. This is not a PC-relative jump. It is a jump to a fixed, absolute constant address.

Typically the code segment will fit within 256MB, so this is typically sufficient to jump to any (fixed) instruction within the code segment.

# Answer
> 2 votes
In MIPS-speak, these areas of memory of 28 (26+2; the +2 is because instructions are four bytes in size) bit address space (256MB) are referred to as "superblocks". Pseudo-direct addressing allows you to jump anywhere *within the same superblock*. It doesn't matter if it's forwards or backwards.

This was never a problem in practice because it's very rare for a single binary (whether it's an executable or a shared library) to have more than 256MB of code. IIRC, the MIPS linker could handle it if it ever occurred by generating a trampoline. Suppose that the compiler generated a `jal`, for example, where the linker discovered that the target was in a different superblock. Then the linker would generate a couple of instructions to do the full jump, and point the `jal` to that.

---
Tags: computer-architecture, mips
---


# Question
Title: Intersection of two generative neural networks
I have an input x (a word), and I have a neural network Y such that Y(x), which is an image always satisfies F(x), and another neural network Z such that Z(x), which is also an image, always satisfies G(x). Is there any way to turn this into a neural network Q where Q(x), which is also a image, satisfies "F(x) ∧ G(x)"?

Thanks!

# Answer
> 1 votes
No, not in general. It's possible that $G(x)=\neg F(x)$, for instance.

---
Tags: neural-networks, neural-computing
---


# Question
Title: What is the average time complexity, for a single linked list, for performing an insert?
I thought this would be a very simple `O(n)` b.c. you can do the insert any where with in the list.

The longer the list, the longer it will take on average to do the insert.

However according to bigocheatsheet it is `O(1)` or has no dependency on the size of the list.

What is wrong here?

# Answer
> 7 votes
Either if you want to insert at the end of the list or at the beginning of the list, you're going to have $O(1)$ Complexity for that and $O(1)$ space. If you want to insert at the beginning of the list, you just make the new list head the node you want to insert, and link it to the previous list head. If you want to insert at the end of the list, you can also hold the end of the list as a pointer and insert a new node after it. If you want to insert in an arbitrary place in the list, then linearly going there is going to be the best you can do ( to my knowledge ). Statistically you'll have to go through $(n+1)/2 $ nodes to get through yours.

# Answer
> 4 votes
If you have no additional requirements on the contents of the list, you can just insert the item at the head, which is O(1).

If you do (e.g. the list must be kept sorted or deduplicated), insertion is more expensive.

# Answer
> 2 votes
https://www.bigocheatsheet.com considering finding (Access) the position of the element before insert as separate operation.

**Array**:

* Access - O(1) // we can get the element by index directly
* Insertion - O(n) // in the worst case we need to resize the array to have a space for the new element

**Linked list**:

* Access - O(n) // we need to reach the element
* Insertion - O(1) // we need to just link the new element with the next and previous

---
Tags: data-structures, runtime-analysis, average-case, linked-lists
---


# Question
Title: Given a valid combination, how to get its index in the sequence of integer partition
This question is extended from this Algorithm to generate integer sets fulfills restrictions, in the answer I learned the formal term of this problem, and the recursive algorithm described in that answer also gives me the desired sequence - as much large numbers located in the front as possible, for example, we will get the following output for $F(7,3,4)$:

* 4\>2\>1
* 3\>3\>1
* 3\>2\>2

So here is the question, given a valid combination, is it possible to get its index in the result set without generating the whole result set and searching for it?

# Answer
> 1 votes
This is called **ranking combinatiorial objects**, in this case **combinations**. Ranking and unranking algorithms exist for various simple combinatorial objects and even a general ranking algorithm exists for arbitrary combinatorial objects given that computing the number of objects matching certain criteria is feasible and there is a total ordering (eg lexicographic ordering).

For combinations, a reference is Algorithms for Unranking Combinations and Other Related Choice Functions, Zbigniew Kokosinski 1995

Assuming a lexicographic ordering among combinations of $K$ from $N$ the following algorithm can be used (which runs in $O(K)$ time assuming binomial computations are cheap):

Assuming the combination is given as an array (`item`) of length $K$ and where

$$item\[0\]\<item\[1\]\<\dots\<item\[K-1\]$$

and each $0 \leq item\[i\] \leq N-1$

(If you want the combination in reverse order simply change the algorithm below to match in reverse order and skip last step. Also since your combinations take values between $1$ and $N$ you might want to subtract $1$ from below algorithms, where $item\[i\]$ is used)

$index = 0$

for $i=1$ to $K$:

\____ $c = N-1-item\[i-1\]$

\____ $j = K+1-i$

\____ if $j \leq c$ then $index \leftarrow index+\binom{c}{j}$

Finally: $index \leftarrow \binom{N}{K}-1-index$

**Note:** The algorithm above can be modified to rank combinations with repeated/duplicate elements. Ie

$$item\[0\] \leq item\[1\] \leq \dots \leq item\[K-1\]$$

One needs to replace the counts used to represent combinations with repeated elements instead of binomials which count combinations with unique elements.

$index = 0$

$N \leftarrow N+K-1$

for $i=1$ to $K$:

\____ $c = N-1-item\[i-1\]-i+1$

\____ $j = K+1-i$

\____ if $j \leq c$ then $index \leftarrow index+\binom{c}{j}$

Finally: $index \leftarrow \binom{N}{K}-1-index$

In essense ranking combinations is a bijection from $N,K$ combinations to natural numbers $0 \dots \binom{N}{K}-1$. This defines a combinatorial number system.

Algorithms above are modified to match my use case (for my combinatorics library Abacus) where combinations take values $0 \dots N-1$ and are non-decreasing. For your use case you can modify them to match wikipedia article.

---
Tags: combinatorics, integer-partitions
---


# Question
Title: Does the word "efficient" usually refer to polynomial time or polylogarithmic time?
This question is strictly about terminology.

I'm not an expert in CS, but I've almost always seen the word "efficient" applied to an algorithm to mean "of polynomial runtime". E.g. this question and the Wikipedia article on computational complexity theory use the word in that way.

However, other sources (e.g. the Wikipedia articles on NC and P-complete) reserve the word "efficient" for algorithms with polylogarithmic runtimes and use "tractable" for algorithms with polynomial runtimes.

This conflicting terminology is obviously confusing. Of course, any (good) formal discussion of algorithmic complexity will precisely define its terminology, but in general, are either of the two usages above clearly more conventional than the other? If someone uses the term "efficient" in an informal discussion of computational complexity without defining it, is it more likely that they mean "polynomial time" or "polylogarithmic time"?

# Answer
> 3 votes
There is no one true answer. It depends on context. The most common context is one where polynomial-time is taken as more or less synonymous with efficient, so if you had no further context, I would certainly guess "polynomial time". Polylogarithmic time is used only in very narrow contexts.

In general, if you think your audience might not be sure about the meaning, then I recommend you to define your terms.

# Answer
> -1 votes
Perhaps this is a reference to Cobham's thesis https://en.wikipedia.org/wiki/Cobham%27s\_thesis?wprov=sfla1. Usually the word used is "feasible" though.

---
Tags: complexity-theory, terminology, runtime-analysis, efficiency
---


# Question
Title: Can all types of computational problems be modeled as decision problems?
Can all types of computational problems (search, counting, optimization...) be modeled as (sets of) decision problems? Rephrased: For every type of computational problem is there a set of decision problems that if you solve those problems you get the result of the original problem?

colloquially: can all types of questions you can ask a string be answered by (a series of) results from YES NO questions? So the game is: you are given a question about a string, you are allowed to ask the string only YES NO questions. The string responds with answers to your YES NO questions that are computable. Can you compose all the answers you receive to narrow in on THE SINGLE answer to the original question (not a spread of answers / not some result but with a probability attached)?

Decision problems can be modeled as word to language membership. On the surface, this only models the functions that go from f:{0,1} * --\>1 not all the other types of functions. Some g: {0,1} * --\>{0,1} * for example. But I have a feeling the answer could be yes...

# Answer
Yes. Every computation problem can be viewed as computing a function $f:\\{0,1\\}^ \to \\{0,1\\}^\*$: on input $x$, the algorithm outputs $f(x)$.

Here is a corresponding decision problem: given $x$ and $i$, determine whether the $i$th bit of $f(x)$ is 1. If you can solve that decision problem, you can solve the original computation problem.

(Strictly speaking, you also need a way to decide whether the length of $f(x)$ is $i$; that can be addressed by defining the decision problem as taking inputs $x,i,b$; if $b=0$, then the problem is to determine whether the $i$th bit of $f(x)$ is 1; if $b=1$, the problem is to determine whether the length of $f(x)$ is $i$.)
> 2 votes

---
Tags: optimization, decision-problem, counting, search
---


title: Reductions to and from PRIME

text:
# Question
Title: Reductions to and from PRIME
I think PRIME (is the given number a prime number?) is a good example a decision problem. Therefore, when I'm trying to explain reduction, I'd like to give an example of a problem that is related to PRIME.

What are decision problems that can be reduced to PRIME, and how do these reductions look like?

What are decision problems that PRIME can reduce to, and how do these reductions look like?

# Answer
Assuming you're talking about polynomial-time reductions, since PRIME is in $P$, you can reduce it to any non-trivial decision problem (for which there is at least one instance with answer YES and at least one instance with answer NO). Moreover, any problem in $P$ can be reduced to PRIME.

To reduce an instance $I$ of PRIME to an instance $I\_Q$ of non trivial decision problem $Q$, let $Y\_Q$ and $N\_Q$ be a YES and a NO instance for $Q$, respectively. The reduction is as follows: solve $I$ using a polynomial-time algorithm for PRIME. Then, let

$$I\_Q = \begin{cases}Y\_Q & \mbox{if $I$ is a YES instance}, \\ N\_Q & \mbox{if $I$ is a NO instance}.\end{cases}$$

To reduce an instance $I\_Q$ of a problem $Q \in P$ to an instance $I$ of PRIME, solve $I\_Q$ using a polynomial-time algorithm for $Q$ and define

$$I = \begin{cases}2 & \mbox{if $I\_Q$ is a YES instance}, \\ 1 & \mbox{if $I\_Q$ is a NO instance.}\end{cases}$$
> 1 votes

---
Tags: reductions
---


# Question
Title: Why does MergeSort have O(n) space complexity if it splits the array log(n) times?
I know this is a common algorithm with plenty of analysis, but when I searched for an answer the only one I found was "Merge Sorting has O(n) auxiliary space because it copies the array into L and R".

I don't understand this because as it is called recursively, before performing any operations, the entire array is still split log(n) times. When following the binary tree diagram representing the recursion, we see (if n=16) it splits into 2x8, 4x4, 8x2, 16x1.

Since all of these splits occur prior to any merging, why is the auxiliary space O(n) and not O(nlog(n))?

# Answer
> 0 votes
The $i$-th time the array is split, it is split into into two arrays of size $2^{-i} n$ elements each (assuming, for simplicity, that $n$ was a power of $2$).

At the ($\log n$)-th recursive call, the total space occupied by all these arrays is $$ 2n \sum\_{i=1}^{\log n} 2^{-i} \le 2n \sum\_{i=1}^{\infty} 2^{-i} = 2n. $$

# Answer
> 0 votes
Yes, you can implement merge sort inefficiently, but you don’t have to.

If you sort an array, notice that you don’t need to create any copies while splitting into subarrays. You only need two integers to identify each of them. Combined with the fact that the number of nodes in the recursion tree is $O(n)$, this gives you $O(n)$ bound on space.

---
Tags: algorithms, algorithm-analysis, sorting, mergesort
---


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

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

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

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

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

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

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

hence amortized time is O(1)

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

Thank you!!

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

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

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

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

---
Tags: algorithm-analysis, time-complexity, runtime-analysis, amortized-analysis, big-o-notation
---


title: Urgent Flag of TCP, Computer Networks

text:
# Question
Title: Urgent Flag of TCP, Computer Networks
The **Urgent Flag(URG)** is set whenever the sender's **Application Layer** wants to send some urgent data to the receiver. In this case, the **Transport Layer** does not wait for enough data to achieve maximum segment size. Now, my question is **how do the routers in between recognize that the packet needs to be forwarded urgently**(they do not have the transport layer)?

# Answer
> 1 votes
They don't. The urgent flag doesn't affect the handling of the packet by routers. The urgent flag is an instruction to the TCP stack on the destination host, not an instruction to routers along the path.

---
Tags: computer-networks, tcp
---


title: Is there a complexity class QPP?

text:
# Question
Title: Is there a complexity class QPP?
The complexity class PP is not considered tractable, because the probability of success can get arbitrarily close to 50% from above as the problem instances get larger, so that (e.g. if this approach is exponentially fast) an infeasible number of repetitions may be required before we have a *significant* probability of confidently distinguishing satisfying inputs from non-satisfying ones. Nevertheless, PP is an interesting complexity class to study in its own right.

Is there a similar well-defined complexity class "QPP" of problems which a quantum computer has a greater than 50% chance of correctly solving in polynomial time? I understand that if so, this class of problems would not be feasible on a quantum computer, but are any nontrivial inclusions with the more "traditional" complexity classes either proven or suspected? How "big" do we think the class QPP is?

# Answer
Yamakami showed in their paper Analysis of Quantum Functions that the quantum analog of PP is the same as classical PP. This is mentioned in the Wikipedia article on PP.
> 5 votes

---
Tags: complexity-theory, time-complexity, complexity-classes, quantum-computing, probabilistic-algorithms
---


# Question
Title: Is a DTM with k-tapes not the same thing as a NDTM with k-branches?
In the definition of a complexity class like P, where they reference Deterministic Turing machines (DTMs), I don't see any restriction on # of tapes these DTMs are allowed to use.

If a language L is in P do all its words have to be decidable in polynomial time by a 1-tape, 2-tape,....k-tape Turing machine in polynomial time?

# Answer
Let $\mathsf{P^k}$ be the class of problems solvable in polynomial time on deterministic Turing machines with $k$ tapes. Then $$ \mathsf{P^1} = \mathsf{P^2} = \mathsf{P^3} = \mathsf{P^4} = \mathsf{P^5} = \cdots $$ Let $\mathsf{PD^{d}}$ be the class of problems solvable in polynomial time on deterministic Turing machines with access to a $d$-dimensional infinite tape. Then $$ \mathsf{P^1} = \mathsf{PD^1} = \mathsf{PD^2} = \mathsf{PD^3} = \mathsf{PD^4} = \mathsf{PD^5} = \cdots $$ Similarly, $\mathsf{P}$ is also the class of problems solvable in polynomial time on RAM machines, which have a random-access memory (i.e. you can implement indexing $A\[i\]$ without needing the head to scan to the $i$th position of the tape).

The definition of $\mathsf{P}$ is very robust to the particular machine model used, and this makes $\mathsf{P}$ a very natural complexity class. This is similar to the class of all decidable languages, which can be defined in countless ways. The exact way you define $\mathsf{P}$ is arbitrary, since all definitions amount to the same complexity class.

The story gets a bit more complicated when we consider computation models other than deterministic machines (of any kind). For example, are probabilistic polytime algorithms stronger than deterministic ones? The answer might depend on the error. Probabilistic polytime algorithms with constant error probability define the complexity class $\mathsf{BPP}$, which is believed (by most) to be the same as $\mathsf{P}$. If we allow unbounded error we get $\mathsf{PP}$, which contains $\mathsf{NP}$, and so such algorithms are probably more powerful than deterministic ones. Similarly, quantum algorithms with bounded errors form the complexity class $\mathsf{BQP}$, which contains problems such as factoring which are not believed (by most) to be solvable in classical polynomial time.
> 1 votes

---
Tags: turing-machines, np, polynomial-time
---


# Question
Title: The best approach to search for closest object in hash map holding arraylist without changing data structure
Imagine the game handled server sided, don't think of a visual problem.

Given a game 2D map, with size of n * n. The game contains objects (such as door, wall, a table).

Each tile position (x,y) can contain multiple objects, but this is not the catch of the question, it can even be limited to one.

The data structure for the game objects linked to the map is designed like this:

```
HashMap<Integer, ArrayList<GameObject>>

```

Where the **Key** integer represents X position of the object, and the value represents a list of all objects with the same X position, different Y position.

Now, I have a player location, I want to fetch a list of all 10 closest object to the player's position, within 100 tiles distance of the player.

**My way of doing so:**

Starting from player's position, and simply going x - 1 and x + 1 grabbing the objects lists limited to Z or until you have 10 closest objects collected, and then performing a position distance comparing search on each object. (Note, the objects lists are not sorted)

But this way is not stable, in my opinion, but I am not sure how can you solve this without changing the data stucture?

# Answer
> 1 votes
If it is for some reason important to use hashing, there is a concept called locality sensitive hashing, however it is somewhat complicated. Typically, nearest neighbor search is done with tree indexes, such as quadtrees, R-Trees or kd-trees.

# Answer
> 0 votes
You probably can't. The principled solution is to use a data structure that supports nearest neighbor search.

---
Tags: data-structures, search
---


# Question
Title: Proving undecidability of HALT_tm by reduction
Sipser in his book `introduction to the theory of computation` provided a proof of undecidability of $HALT\_{TM}$. He uses a contradiction, he assumed that $HALT\_{TM}$ is decidable, and built a decider for $A\_{TM}$, and since $A\_{TM}$ is already proved by digonalization method to be undecidable, thus the contradiction occurs and $HALT\_{TM}$ is undecidable. The Turing Machine is simple and straightforward and I'm not going to talk about its details.

What makes me confused is this sentence

> We prove the undecidability of $HALT\_{TM}$ by a reduction from $A\_{TM}$ to $HALT\_{TM}$

and I would like to know in which part of the proof reduction actually occurs?

From what we know of the concept of reduction, reducing $A$ to $B$ means: we have two problems $A$ and $B$ and we know how to solve $B$ but we stuck in $A$, then if we reduce $A$ to $B$, it means solving an instance of $B$ will cause solving an instance of $A$.

let's get back to the proof, Sipser says

> We prove the undecidability of $HALT\_{TM}$ by a reduction from $A\_{TM}$ to $HALT\_{TM}$

thus $A = A\_{TM}$ and $B = HALT\_{TM}$. We don't know how to solve $HALT\_{TM}$ and actually this is the problem in hand, furthermore the strategy of the proof is based on contradiction, something that is completely irrelevant to the concept of reduction. Then why Sipser uses the term ***reduction*** in this proof?

# Answer
Sipser reduces $A\_{\mathit{TM}}$ to $\mathit{HALT}\_{\mathit{TM}}$. Since $A\_{\mathit{TM}}$ is uncomputable, it follows that $\mathit{HALT}\_{\mathit{TM}}$ has to be uncomputable. He is using the following general statement:

> If $A$ reduces to $B$ and $B$ is uncomputable, then so is $A$.

You are right that this general statement itself is proved by contradiction. A proof which uses this general statement to prove that a particular problem is undecidable is a proof by reduction – in your case, you prove the undecidability $\mathit{HALT}\_{\mathit{TM}}$ by reducing a problem you already know is undecidable to $\mathit{HALT}\_{\mathit{TM}}$. In contrast, Sipser's proof that $A\_{\mathit{TM}}$ uses a different technique, diagonalization.
> 2 votes

---
Tags: complexity-theory, turing-machines, reductions, halting-problem
---


# Question
Title: How should we interpret a transition rule $\epsilon,b\to c$ in a Pushdown Automata as Sipser defined in his book?
After defining pushdown automaton in Sipser's book at p. 113:

at the bottom of p.114, he tries to describe a way to make a diagram for pushdown automaton as following:

My question is about the part "**If $a$ is $\epsilon$, the machine may make this transition without reading any symbol from the input.**" But in many examples in the book, it seems some $\epsilon$s which are in place of $a$ must be interpreted as an empty string to show that the pointer is reached to the end of input. For example in the following diagram, we must interpret the first $\epsilon$ in the label of the transition between $q\_3$ and $q\_4$ to an empty string which shows the end of input string:

Otherwise, it can accept $01^2$. Since, if we interpret $\epsilon,\\$\to\epsilon$ as to make this transition from $q\_3$ to $q\_4$ without reading the second 1, then $01^2$ would be accepted.

Now my question is how a PDA decides if that $\epsilon$ is for moving without reading any symbol from input or that $\epsilon$ is an empty string?

# Answer
> 1 votes
Suppose that your PDA is reading $011$.

At the beginning, the PDA is at state $q\_1$, and the stack is empty. The only move the PDA can make is to put $\\$$ on the stack and to transition to state $q\_2$.

Since the next symbol to be read is $0$, the only move the PDA can make now is the self-loop on $q\_2$ which puts $0$ on the stack. The input is now $11$, and the stack is $0\\$$ (top of stack first).

Since the next symbol to be read is $1$, the only move the PDA can make is to transition to $q\_3$, erasing $0$ from the top of the stack. The input is now $1$, and the stack is $\\$$.

Since the next symbol to be read is $1$, the PDA must move to $q\_4$, erasing $\\$$ from the stack. The input is still $1$, and the stack is empty.

At this point, the PDA is stuck. It cannot make any move. However, it hasn't read all the input yet. We conclude that there is no accepting computation for this input, and so the PDA doesn't accept $011$.

---
Tags: computability, pushdown-automata
---


# Question
Title: Why the Call instruction in the x86 architecture saves the return address as EIP+5 instead of 4?
In 'The Computer Organization and design book' it illustrates the call instruction as

1. Decrementing the stack pointer by 4.
2. saving the **EIP+5** into the stack.
3. Jumps to the new address specified.

What I know already is the instructions in this architecture are not typically all 4 byte in length, Hence.

How do we standardize the **EIP** to be added by **5** to the next instruction ?

normally in the MIPS architecture throughout the rest of the book the EIP is incremented by 4 which is intuitive as all the instructions are 32 bits.

# Answer
Not sure which book you are referring to (isn't that book talks only about MIPS and not on x86?)

In any case, I think that the answer is the following: EIP+5 is the address of **the next instruction**. That is, in x86 the next instruction after a (near32) call is 5 bytes away. This is because the call takes 5 bytes:
1byte = the call opcode (E8, for a (near)rel32 call)
4bytes = the 32bit offset to the call target from current EIP.

That is, the new EIP (after the call) is computed by taking the current EIP and adding to it the 4bytes relative offset.

So, if the call instruction itself takes 5 bytes, then the next instruction (the *return address*) is at EIP+5.

See also https://c9x.me/x86/html/file\_module\_x86\_id\_26.html for all possible calls (I described the rel32 one).
> 3 votes

---
Tags: computer-architecture
---


# Question
Title: Allocation of many students to many schools based on capacity
Say I have a set of schools coordinates (S). I also have a set of neighborhoods centroid coordinates (N).

I know how many kids are in each neighborhood, and they are categorized as either primary, middle or high school. So, in other words,

```
N = [(locationN1, primary:3, middle:10, high:4), (locationN2, primary:10, middle:17, high:7), ...]

```

I know how many spots are available in each school, the format being:

```
S = [(locationS1, primary:20, middle:5, high:2), (locationS2, primary:12, middle:7, high:8), ...]

```

My goal is to match as many students as possible to a school within a certain radius. It is possible (extremely likely) that in my calculations, some students will be school-less.

What I want: identify which neighborhood have school-less children and how many.

My current plan:

* List all the pairings and corresponding distances between schools and neighborhood, within a given radius
* Order by distance from lowest to highest
* Give priority based on distance
* Loop over the neighborhood in order of appearance (each neighborhood can appear several times linked to a given school within defined radius)
* Fill corresponding school with children from neighborhood
* Remove taken spots from the school capacity
* Move to the next neighborhood-school pairing, ...

As an example:

* Say you obtain the following ordering:

Order = \[(neighborhood\_2, school\_7, distance1), (neighborhood\_5, school\_2, distance2), (neighborhood\_2, school\_2, distance3), (neighborhood\_2, school\_3, distance4) ...\]

Then, school\_7 receives children from neighborhood\_2. Not all children from neighborhood\_2 can be taken in at school\_7.

Then, school\_2 receives students from neighborhood\_5. Now, assume that school\_2 is full for middle school capacity.

Then, neighborhood\_2 still has students to dispatch, and so tries to send them to school\_2. Primary and high school, no problem, they are now all dispatched. But middle school is full.

Then we move on to the next pairing, and school\_3 gets the remaining middle school students from neighborhood\_2. Note that if distance4 had been higher than the limit radius, these middle school students would have been classified as school-less since no other pairings are available.

Additionally, if neighborhood\_4 is oit of the limit radius for any school, all its children are considered school-less.

1) Is my algorithm correct?

2) What is the name of this exact problem? I've come across many to many point matching, capacitated allocation problems, or the "validation" part of facility location problem, but not this particular variant for some reason (likely poor searching skills)

3) How can I make this efficient, or is it pretty reasonable this way? (efficiency is not my primary concern, but easy fixes are welcome)

4) Do I have other options besides distance sorting? Technically, in my case, distance doesn't matter much to give priority, it's more of a random (or should I say fair) allocation based on for example time of received application (unknown data). So my method will show likely 100% allocation for a neighborhood very close to a school amd a bunch of school-less kids in farrher neighborhoods, yet that may not be (is not) true in real life.

# Answer
This can be expressed as the problem of finding a maximum matching in a bipartite graph: each kid is one left-vertex, each slot in a school is a right-vertex, and there is an edge between two vertices if they can be matched.

In your case, you can solve it more efficiently using max flow. I'll let work out the details.
> 1 votes

---
Tags: algorithms, optimal-strategy
---


# Question
Title: Finding a hamiltonianISH path in a graph
### Problem statement

Given a graph of all the blue squares in the following image where each blue square is connected to other blue squares in all 4 cardinal directions.

Given any starting node.

What algorithm will allow for finding the longest(ish) path.

Considering that each node can only be visited once.

Considering that we don't care where the path ends.

Considering that speed is more important than necessarily visiting each node.

### Example

I have traced an example of the desired result in the image below. As you can see, the path does not visit each node and that is fine. I'm looking for a fast algorithm that will give me one of the longest possible path on this graph. 80% coverage or more is what I'm shooting for.

# Answer
I ended up using the UCT (MCTS with UCB1) algorithm but with a twist.

Normally, in UCT, the simulation phase is a simulated play-through of a game with moves chosen at random. If the simulated game ends in a win, the node's score, from where the simulation was played out, and all it's parents' scores all the way back to the root, are incremented by 1.

In my implementation, the simulated "play-through" is actually just a random walk down the tree of neighboring tiles that haven't been visited yet. Once the simulation reaches a terminal-node (dead-end) it assigns a score of s = d / m where d is the terminal node's depth in the tree and m is the maximum possible depth.

On a 15 x 15 grid with no obstacles, you would set m to 225 as the longest path would visit every tile. I've set mine slightly lower than that as I need the algorithm to be generalized and work on randomly generated maps that usually have 10-30 tiles occupied by obstacles.

Instead of incrementing the parents' score, the backtracking algorithm sets each parent's score to the newly computed score, if it is higher than their current score. In other words, a node's score always represents the length of the longest path reached so far from this node.

UCT uses UCB1 in order to select which node to exploit or explore once every children of the current node have been expanded and I have largely kept with that. The only modification I have made is to the exploitation term. In UCB1, the exploitation term is w / v where w is the node's accumulated score and v is the number of time the node was visited. This works great in a game where you want to select the move that maximizes your chances of winning. In my case, since the score reflects not a binary function of win = 1 and lose = 0 but rather a scale of 0 = super short path vs 1 = the longest path possible and I want to go down the longest path found by the algorithm, I have simply set the exploitation term to s = score = longest path reachable from this node.

The context in which I'm using this algorithm allows me about 40 ms of compute time in a NodeJS environment before I have to select a move. This usually affords around 785 tree traversals on my machine. On average, in that time, and on the map showed in OP, this algorithm will find a path that is 70 nodes deep. Which is more than enough for my purposes seeing as I get to run the algorithm again the next turn. In practice, when using this algorithm to select next moves, I end up travelling a path that is 100-110 steps long before hitting a dead-end and I cover a very large portion of the blue tiles.

For fun I have ran the algorithm for much longer and at around 300 000 traversals (30 secs on my machine), on average, again on the map shown in OP, it finds a path that is 125 nodes deep which is pretty close to the max depth on this map.
> 1 votes

# Answer
This is the longest path problem. It's NP-hard to find the longest path in a general graph. You can try applying any standard algorithm for finding longest paths. Search on this site for "longest path" and "Hamiltonian path" to find many references. Since you're willing to accept suboptimal solutions, you might look for a heuristic or approximation algorithm (e.g., using a local search algorithm).
> 2 votes

---
Tags: np-complete, graph-traversal, hamiltonian-path, square-grid
---


# Question
Title: Programming in Propositional Logic article notation question
I was reading this article about propositional logic and transforming problems to SAT. The author often uses the following notation (taken from *Dominating set* section):

I don't understand what $\[v,i\]$ and $\[w,i\]$ stand for in $at\\\_most\\\_one$ and $at\\\_least\\\_one$ parts. I checked the paper twice and didn't find the part where he defines this notation. Has anyone already seen this notation and knows what it means? Why is $i$ needed? Can anybody provide example for a simple graph and for some K (2 or 3).

# Answer
The set $X$ is a collection of ordered pairs $\[v,i\]$ (this is just a strange notation for an ordered pair), in which $v$ is a vertex and $i$ is an index from $1$ to $k$. Informally, $\[v,i\] \in X$ means that $v$ is the $i$th vertex in the dominating set. The formula $F$ states two things:

* There is at most one $i$th vertex (i.e., $X$ doesn't contain $\[v,i\],\[u,i\]$ for $v \neq u$).
* The vertices in $X$ form a dominating set.

The reason we want the index $i$ is that the logic isn't strong enough to count the size of $X$. It is strong enough to express "at most one" and "at least one", so we use this particular encoding to be able to express "the dominating set has size at most $k$".
> 2 votes

---
Tags: satisfiability, propositional-logic
---


title: Find specific position in matrix

text:
# Question
Title: Find specific position in matrix
Consider a binary (i.e. over $\\{0, 1\\}$) matrix $A = (a\_{ij})$ of size $n \times n$. It is known that there is *exactly one* $r \in \[1; n\]$ such that $a\_{rj} = 0$ for all $j \in \[1; n\]$ and $a\_{ir} = 1$ for all $i \in \[1; n\] \setminus \\{r\\}$. How to find $r$ asymptotically in $O(n)$ in terms of time?

# Answer
Let $i \neq j$.

* If $a\_{ij} = 0$ then $j \neq r$ (why?).
* If $a\_{ij} = 1$ then $i \neq r$ (why?).

You take it from here.
> 0 votes

---
Tags: algorithms, matrix
---


# Question
Title: finding all cyclic substrings of a string
I have been stuck on this problem for a while now; any help would be appreciated.

Given a string S, find the number of **distinct** substrings which are composed of **2 or more consecutive strings**. For example, "abbccbbadad" has **3** because "bb" is composed of 2 "b"s, "cc" is composed of 3 "c"s, and "adad" is composed of 2 "ad"s.

My solution uses hashing and currently runs in n^2 time, which is fine because the length of the string is \<= 5000. However, my program uses n^3 space. I am confident that a solution requiring n^2 space and n^2 time will pass. Is there a more efficient solution?

# Answer
> 0 votes
Any algorithm that runs in $O(n^2)$ time can access at most $O(n^2)$ different memory locations during the course of its execution. Thus, if you replace memory with a hashtable (instead of accessing address $a$, access the hashtable at key $a$), you obtain an algorithm with expected running time $O(n^2)$ and space $O(n^2)$. If you care about theoretical proofs, you can use a balanced binary search tree instead of a hashtable and obtain a worst-case time bound of $O(n^2 \log n)$ time and $O(n^2)$ space.

---
Tags: strings, substrings, rolling-hash
---


# Question
Title: Piecewise linear approximation for set of points
If we have a set of points $A$ and a known algorithm $Bestfit(A)$ to find the best-fit straight line-segment through $A$, what would be a good algorithm to construct piece-wise linear segments (with at most $k$ segments) to give a better approximate of the set of points and reduce the error $E$?

# Answer
This can be solved with a straightforward dynamic programming algorithm. If you have $n$ data points, it can be solved in $O(n^2)$ calls to BestFit plus $O(n^2 k)$ time. See https://cs.stackexchange.com/tags/dynamic-programming/info for our resources on how to construct dynamic programming algorithms.
> 1 votes

---
Tags: algorithms, approximation
---


# Question
Title: Learning a specific functional form with machine learning
Suppose I have only three independent features `(x, y, z)` as the input to some machine learning routine (e.g. neural network). From some domain knowledge, I know that the output `o(x, y, z)` must have the specific functional form

`o(x, y, z) = f(x)*g(y)*g(z)`

where the `g(.)` are the same function. The details of `f(.)` and `g(.)` are not known beforehand (except that `f(.)` is a decaying function with respect to `x`). Given that there is no upper limit on the sample size, is it possible to incorporate such a functional form (or in general, any specific functional form) into the machine learning routine?

# Answer
Yup. You define two neural nets (or other models) $f,g$ with weights $\theta,\psi$, define

$$o\_{\theta,\psi}(x,y,z) = f\_\theta(x) g\_\psi(y) g\_\psi(z),$$

define a loss function (which compares the predicted output $o\_{\theta,\psi}(x,y,z)$ to the desired output), and then use stochastic gradient descent to find weights $\theta,\psi$ that minimize the aggregate loss on the training set.
> 0 votes

---
Tags: machine-learning, neural-networks
---


title: taking school courses efficiently

text:
# Question
Title: taking school courses efficiently
I want design algorithm that allows a student to take important courses quickly up until graduation. no time, room number, professors needed here. just my selected courses I know will allow me to graduate but how best to take them based on prerequisites. the student can decide how many courses to take a semester. And, you cant take a course's prerequisite and itself eg cs101 cs102 201 but cs201 cant be taken in the first semester because i have to take its prerequisites first. Additionally prequisites can be such that 101 and 102 or 101 and 104 are possible choices to take as prerequisites to a course 201. We could also have 101 or 106 and 102 or 105 ossible choices to take as prerequisites to a course 202.

any suggestions and how to go about it. Trees, graph adjacency list

I was thinking topological sort will give a valid ordering but i think i would ran into trouble when placing them in across semesters because topological sort order them linearly eg cs101 cs102 201 but cs201 cant be taken in the first semester because i have to take its prerequisites first. And what about if we have cs 103 cs104 cs202. cs103 and 104 have nothing to do with cs101 102

# Answer
Form a directed graph of dependencies, with an edge $x\to y$ if course $x$ is a prerequisite for course $y$. Use Kahn's algorithm to topologically sort the graph. In particular, in each semester, you take all courses with indegree 0 (i.e., all courses where you've satisfied all prerequisites), then delete those courses from the graph.

This assumes there is no limit on the number of courses you can take in each semester. Under that condition, it will let you complete your degree in the minimum number of semesters, in an order that respects the prerequisites.

If there is a limit on the number of courses you can take in a semester, the problem is more challenging. This algorithm will find an order you can take your courses to get your degree, in an order that respects the prerequisites, but it is not necessarily the minimal number of semesters. If you're in that situation, the best solution may depend on the number of courses you have and whether this is a practical problem you want to solve in real life or a theoretical problem where you care about worst-case asymptotic running time.
> 2 votes

---
Tags: optimization, scheduling
---


# Question
Title: Algorithm for optimal spacing in intervals
Is there an algorithm to optimally space points within multiple intervals? Optimal in this case means maximizing the smallest distance between any two points so that each pair of points has at least distance X. For example, in the intervals (1,3) and (5,7) you can space out three points with a distance of at least 2 (at 1,5, and 7). But you can't space out three points with a distance of at least 3. Is there an easy way to do this with a program?

# Answer
Sure. A simple approach is to use binary search on the separation distance $d$: given $d$, it is easy test whether there is a way to space out $k$ points so that all are at least $d$ apart (I'll let you figure out how; if you can do it for one interval, you should be be able to do it for multiple intervals). Then use binary search on $d$.
> 2 votes

---
Tags: algorithms
---


# Question
Title: What's an efficient algorithm to calculate line breaks (word wrap) for balanced widths (minimum raggedness)?
*This is a real-world application, not a student assignment.*

* Suppose we have some numbered boxes which are to be laid out, **in order**, from left to right, top to bottom, with no space between them, into a column of fixed width and infinite height.
* The boxes have the same height, but variable width.
* When a box doesn't fit, it should wrap to the next line (just like text).
* After that, we **fix the number of lines**, and then lay out the boxes again so that the lines have a more *balanced* width, which means they try to be the same width, as much as possible.

The input is, simply:

```
double colWidth = …;
List<double> boxWidths = [ … ];

```

And the output could be:

```
List<int> result = [ … ]; // Number of boxes in each line.
double minWidth = …;

```

An example: Suppose the column has width = 11, and 5 boxes have widths \[2, 3, 5, 2, 1\], then the layout is this:

```
| ** *** ***** |
| ** *         |

```

This means we can fit the boxes into 2 lines, and line widths differ a lot. One is 10 and the other is only 3 (difference is 7).

Now we have to lay them out again in 2 lines, to achieve balanced width:

```
| ** ***       |
| ***** ** *   |

```

The result is 2 boxes in the first line, and 3 boxes in the second line: `List<int> result = [2, 3]`. Widths are now 5 and 8. Difference is 3, and `minWidth` is 8.

Please note, we **cannot change their order**. If we could, then the difference would be 1 and `minWidth` would be 7:

```
| ** *** *     |
| ***** **     |

```

---

**My question:**

**What's the most efficient algorithm to solve this? I am interested in speed, and I don't care about memory usage.**

# Answer
> 12 votes
Have you considered using the total-fit line breaking algorithm(a) used by TeX(b) and developed by Donald Knuth and Michael Plass?

Edit:

The total-fit line breaking algorithm has already been implemented in many languages, including Java:

# Answer
> 3 votes
This can be solved with dynamic programming; see https://en.wikipedia.org/wiki/Line\_wrap\_and\_word\_wrap#Minimum\_raggedness or https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-20-dynamic-programming-ii-text-justification-blackjack/ for resources.

---
Tags: algorithms, optimization, performance
---


# Question
Title: How were weights chosen in Runge-Kutta (4) method?
Consider an ODE $\dot y = f(t, y)$. We will approximate the value of $y$ using the 4th-Order Runge-Kutta method. Let $\Delta$ be the step size, then in step $i+1$ we have $~y\_{i+1} = y\_i + deriv\cdot\Delta~$, where: \begin{eqnarray\*} deriv &=& \frac{1}{6}(d\_1 + 2d\_2 +2d\_3 + d\_4) \\ d\_1 &=& f(t\_i, y\_i) \\ d\_2 &=& f(t\_i + \frac{\Delta}{2}, y\_i + d\_1 \frac{\Delta}{2}) \\ d\_3 &=& f(t\_i + \frac{\Delta}{2}, y\_i + d\_2 \frac{\Delta}{2}) \\ d\_4 &=& f(t\_i + \Delta, y\_i + d\_3 \Delta) \end{eqnarray\*} Why those particular weights were chosen: 2 for $d\_2$ and $d\_3$, and 1 for $d\_1$ and $d\_4$? Why not $deriv = \frac{1}{4}(d\_1 + d\_2 + d\_3 + d\_4)$? (or any other weights)

# Answer
> 1 votes
You can enter a known function that is the solution of a known differential equation, write down the Taylor series up to say 6 terms, and then substitute it into the Range-Kutta formula or any other formula.

Once you calculate it, you will find that with the Runge-Kutta formula, you add up lots of different constants which magically add up to zero. If you change the constants to what you proposed, most likely these constants add up to something that isn't zero, introducing huge errors into your solutions.

---
Tags: numerical-algorithms
---


# Question
Title: DP recurrence relations: Coin change vs Knapsack
Take:

1. KP recurrence relation

$ max { \[v + f(k-1,g-w ), f(k-1,g)\] } $ if w \<= g and k\>0

2. CCP recurrence relation

$ min {\[1 + f(r,c-v), f(r-1,c)\]} $ if v \<= c and r\>0

I don't understand (much as I've researched) exactly what the reasoning is behind KP comparing in both cases (take the element/don't take it) to the above row $('k-1')$ while CCP only does this when it doesn't take the coin (the same number that's a row above in the same column persists).

To evaluate the case where the coin is taken, CCP says to go back on the same row as much columns as you get when subtracting the coin value of that row from the column you're in . Then it says to add 1 (because you'd be taking the coin).

Supposing I understood this well enough, the latter logic makes perfect sense to me. I don't see the need for KP to go up a row when taking the element (I see why it adds 'v' and goes back a number of columns, it's just the $'k-1'$ that baffles me)

What's the logic behind this?

_

EDIT:

Underlined in red you'll find what I'm referring to, more especifically.

> Knapsack 0-1 Problem:

Take the **24** : it's the result of comparing the **15** directly above it (not taking the element) to the **15** up and to the left (taking the element) . This last 15 is not on the same row as 24 is.

**See source:** http://www.mafy.lut.fi/study/DiscreteOpt/DYNKNAP.pdf

> Coin Change Problem:

Goes back on the same row where our starting point is(case where coin is taken).

**See source:** (page 2): http://condor.depaul.edu/rjohnson/algorithm/coins.pdf

# Answer
The knapsack problem only allows you to add each item once. Subtracting from $k$ is, in a sense, iterating through the items and resolving a different one each recursion.

Put another way, if you didn't subtract 1 from $k$, you'd be able to add the same element multiple times.
> 3 votes

# Answer
In CC you can use **same coin INFINITE times**. But in KP you can use **the same weight, not more than once**. Check http://www.ccs.neu.edu/home/jaa/CSG713.04F/Information/Handouts/dyn\_prog.pdf

To consider all the subsets of items, there can be two cases for every item: (1) the item is included in the optimal subset (2) not included in the optimal set.

Therefore, the maximum value that can be obtained from n items is the max of the following two values.

1) Maximum value obtained by n-1 items and W weight (excluding nth item).

2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).

If the weight of the nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.
> 1 votes

---
Tags: dynamic-programming, recurrence-relation, knapsack-problems, coin-change
---


# Question
Title: Amortized value of dequeue with potential function
A deque is implemented with 3 stacks. one for the head, one for the tail and one is always empty. Pushing is therefor O(1), light popping (in case the head/tail respectively aren't empty) is also O(1). A 'heavy pop' is in a scenario when we have k elements, only in 1 stack and we wish to pop the other stack. For example, n elements in head and we want to pop the tail. In this case, we push all elements from head stack to the empty stack, than push n/2 elements to the tail and the remaining n/2 back to the head.

I'm having troubles finding the potential function for this solution, or the amortized value for that case. If I define the potential function to be the number of current elements in the deque, I get linear time. I don't know if this is true but I feel like it's not.

# Answer
The intuition is following: the "bad" case when you have to do expensive operation is when one of the stacks is empty, and the other one is big. You need to compensate its real cost with a potential decrease. Thus, you can define potential function as $2 \lvert \operatorname{size}(head) - \operatorname{size}(tail) \rvert$.

(For simplicity I represent hard pop as combination of two operations - rearrangement of elements using the third stack and a light pop)

Before the rearrangement, one of the stacks is empty, and other one contains $k$ elements, and right after both contains $\frac{k}{2}$. Therefore, the potential decreases on $2k$ and amortized cost of rearrangement is

$(k + \frac{k}{2} + \frac{k}{2}) + (-2k) = 0 = O(1)$

The amortized costs of light pop and push are clearly $O(1)$ as well as potential increases on $2$ at most.
> 0 votes

---
Tags: time-complexity, data-structures, amortized-analysis
---


# Question
Title: If L is not regular and is a proper subset of L1, does it follow that L1 is not regular?
If $L$ is not regular and $ L \subset L\_1$, does it follow that $L\_1$ is not regular also? Can you please provide an explanation? Thanks in advance.

# Answer
> 18 votes
@Vladislav's answer is probably more interesting, but observe that *every* language over an alphabet $\Sigma$ is a subset of $\Sigma^\*$, which is certainly a regular language.

# Answer
> 8 votes
No. Let $L$ be the language of balanced bracket sequences, and $L\_1$ be the language of arbitrary bracket sequences. Then $L \subset L\_1$, $L$ is not regular (you can prove it using pumping lemma), but $L\_1$ is clearly regular.

---
Tags: formal-languages, regular-languages
---


title: CLRS closest-pair $L_m$ distances

text:
# Question
Title: CLRS closest-pair $L_m$ distances
I am studying algorithms and datastructures, and in CLRS chapter 33.4, the exercise 33.4-4 states the following:

*We can define the distance between two points in ways other than euclidean. In the plan, the **$L\_m$ distance** between points $p\_1$ and $p\_2$ are given by the expression $(|x\_1-x\_2|^m+|y\_1-y\_2|^m)^{1/m}$. euclidean distance, there, is $L\_2$-distance. Modify the closest pair algorithm to use the $L\_1$-distance, which is also known as the **Manhattan distance**.*

I understand its an easy modification, however when I've been comparing my intuition with that of solutions provided online (e.g. https://sites.math.rutgers.edu/~ajl213/CLRS/CLRS.html), all I can find is that they all point to the number of points in the $\delta$ x $2\delta$ is increased to 10 (from 8), adding one point to the middle of both squares formed by the rectangle (*here marked with red below*):

Can anyone explain to my why this is the case? Intuitively I cannot see why it should be the case that the number of points in the rectange should increase, when switching to another **$L\_m$-distance**?

The **Manhatten distance** $\geq$ **Euclidean distance** from what I can see in all instances, but why should this infer, an increase in points found in the $\delta$ x $2\delta$ space.

What am I missing?

# Answer
One approach to see what is going on here is via the notion of an *open ball* under a given distance. Given a distance $d$, the open ball of radius $r$ around a point $p$ is given by $B\_r(p):=\\{q\mid d(p,q)\<r\\}$, i.e. the set of all points with distance less than $r$ to the center of the ball, $p$. In the plane and under the Euclidean distance, a ball is an open disk (a disk with the boundary removed) of radius $r$.

Since $\delta$ is the minimum distance between any pair of points in the left half, any pair of points in the left $\delta\times\delta$ square has a distance of at least $\delta$. This is equivalent to saying that the open ball of radius $r$ centered at a point $p\in P\_L$ contains no other point $q\in P\_L$. So, the maximum number of points from $P\_L$ that can be in the $\delta\times \delta$ square is the largest number of points you can 'fit' into the square such that the ball surrounding each of those points contains no other point from $P\_L$.

An open ball under the Euclidean distance is an open disk. If you place four points at the corners of the $\delta\times \delta$ square, the open disks of radius $\delta$ centered at those points together cover the entire square, so there is no position in the square to place for a fifth point.

However, under the Manhattan distance, an open ball of radius $\delta$ is an open square with diagonal length $\delta$, rotated by $45$ degrees (an "open diamond"). If we place such an open diamond at each corner of the $\delta\times \delta$ square, then there is exactly one position in the square not covered by an open diamond: the center of the square. This is the location where you can place a fifth point under the Manhattan distance.

---

As for the $L\_m$-distance with $m\>2$, note that the balls under these metrics all strictly contain the ball under the $L\_2$-distance. I'll leave it up to you to use this fact to determine the maximum amount of points that can be in the $\delta\times\delta$-square.
> 1 votes

---
Tags: algorithms, computational-geometry, divide-and-conquer
---


# Question
Title: Transitive reduction with vertex additions?
The transitive reduction of a (finite) directed graph is a graph with the same vertex set and reachability relation and a minimum number of edges. However, what if vertex additions are allowed? In some cases, the addition of vertices can considerably reduce the number of edges required. For example, a complete bipartite digraph $K\_{a,b}$ has $a + b$ veritices and $ab$ edges, but the addition of a single vertex in the middle results in a digraph with the same reachability relation that has $a + b + 1$ vertices and only $a + b$ edges.

More formally, given a directed graph $G = (V, E)$, the challenge is to find $G' = (V', E')$ and injective function $f: V \rightarrow V'$ such that $f(b)$ is reachable from $f(a)$ in $G'$ if and only if $b$ is reachable from $a$ in $G$ and such that $|E'|$ is minimized.

Are there any known results or algorithms related to this problem?

# Answer
> 1 votes
I don't think that any such "small" graph can exist in general.

Let $n$ be a multiple of $4$ and pick your favorite binary string $s = \langle s\_0, \dots, s\_{\ell-1} \rangle$ of length $ \ell = \frac{n^2}{4}$.

Build a directed bipartite graph $G\_s = (A \cup B, E)$ on $n$ vertices where $A = \\{a\_0, \dots, a\_{\frac{n}{2}-1}\\}$ and $B = \\{b\_0, \dots, b\_{\frac{n}{2}-1}\\}$. $E$ contains the edge $(a\_i,b\_j) \in A \times B$ iff $s\_{\frac{in}{2} + j}$ is $1$.

Let $G'\_s$ be the smallest graph obtainable from $G\_s$ that preserves connectivity relations. Notice that, from $G'\_s$, it is possible to recover the whole string $s$.

There are $2^\ell$ choices for $s$, which means that, for at least one graph $G\_s$, the minimum number of bits needed to encode $G'\_s$ must be at least $\ell = \Omega(n^2)$.

Notice that $O(m \log n)$ bits suffice to encode any graph with $m$ edges and $n$ vertices. This means that $G'\_s = (V', E')$ must be such that $|E'| \cdot \log |V'| \cdot \log n = \Omega(n^2)$.

---
Tags: algorithms, graphs, dag
---


title: Making sense out of byte-order in text

text:
# Question
Title: Making sense out of byte-order in text
I have stumbled about the way a text file is saved by the OS. I have typed:

```
printf "ab" | hexdump

```

and the output was:

> 6261

which are the letters in reversed order. My first intent was endianess, but this cannot be true, since at this level, such abstractions must be transparent to the programmer and user. Also endian would be:

$$ab \mapsto 6162 \mapsto 2616$$

So I wondered, why would someone save a file like that?

Greetings, Niclas

# Answer
> 1 votes
I'm not sure this is the right place for this question. Anyway, `hexdump` is interpreting your input as a 16-bit little-endian number, therefore the bytes 0x61 and 0x62 (which leave the pipe in the "correct" order) appear reversed. Try `printf "ab" | hexdump -C` .

```
00000000  61 62                                             |ab|
00000002

```

---
Tags: operating-systems, memory-management
---


# Question
Title: How to perform matrix multiplication in Mixing Columns step of AES?
I am studying AES and trying to implement it. But I am having difficulty understanding the Mixing Column step. In that step we have to perform matrix multiplication between the state matrix and another fixed matrix. Here is the example given in the material I am studying from:

I am not getting the `03*2F` part. How did it turn into `(02*2F)xor2F`? Is the material correct or does it have some mistake?

**Edit:** I got that `3 = 2 xor 1` hence `3 x 2F = (2 xor 1) x 2F = (2 x 2F) xor 2F` but what in case if 4 x 2F? `4 = 2 xor 6` so `(2 xor 6) x 2F` then what?

# Answer
If you want to implement it, I suggest you read the spec. The material you were given is probably not enough to implement it.

The reason that looks confusing is that it is not ordinary multiplication; it is multiplication in a finite field. There are lots of resources where you can learn about finite fields.
> 1 votes

---
Tags: cryptography, encryption
---


title: sliding window maximum

text:
# Question
Title: sliding window maximum
I have a stream of tuples arriving in the following form: (timestamp,price). There is no pattern in the arrival of these data points (number of data points per minute is random). I need to be able to return the maximum price in the last hour at any point of time. What is the most efficient algorithm in terms of time complexity and space complexity separately to do this ? I thought of the following:

1. create 1 min candles of prices, which will reduce the storage but then wont be exactly correct
2. store the top K elements with their price and timestamps and update this list according to the current timestamp

# Answer
In the worst case, there is no algorithm with better space complexity than storing all data points from the past hour. So, I think you should focus on optimizing time complexity. A reasonable data structure would be to store them in a balanced binary tree, keyed on timestamp, where each node is augmented with the maximum price over all descendants of that node. This achieves $O(n)$ space, if there are $n$ data points within the past hour, and $O(\log n)$ time per data point that you receive.
> 1 votes

# Answer
You will have to store one hour's worth of tuples. You can see this in the worst case of a series of descending prices over an hour. Say they were to come in one a minute starting at a price of 60. Then the first maximum would expire in one minute, then the second in the second minute and so on.

You should store the data in time order and only keep one hour's worth of tuples (using a FIFO queue). You haven't specified if timestamps are strictly in order as they come in. If not, then they will have to be kept sorted O(nlogn) - in which case its more efficient to store the tuples in order of price, then reading off the maximum is a case of reading the tuple at the end of the list.

However the data is sorted, you will have to do a linear scan either to find the maximum price (time ordered) or to remove tuples over one hour old (price ordered).

If time ordered you could keep scans of the data down by keeping track of the current maximum price and its position in the list. You compare each new tuple's price with the current maximum and if it's higher then this becomes the new maximum.

When the current maximum falls off the list (its age is greater than an hour), you do a linear scan to find the new maximum. This means doing a linear scan once an hour in the worst case.

If price ordered you can keep scans down by keeping track of the oldest timestamp and doing a linear scan for the next oldest when it expires.
> 0 votes

# Answer
For time complexity, it partly depends on where you want to improve the time. You could consider a FIFO where each record has the price and the timestamp and also something else: the largest price over every item that is as/more recent. This would mean an $O(n)$ operation for each batch of items that is inserted, but it would improve the time for fetching the maximum price, since you could peek at the front of the line, and pull off a few obsolete items (older than an hour) until you find an item no more than an hour old, and then the max price in that item is the value you want.

Or you could make each record contain the max price over all that is at least as old. In this case, to retrieve the max price over hour, it is an $O(1)$ operation if no old items need to be removed from the FIFO, but otherwise all the old items need to be purged and the max prices recomputed in $O(n)$.

But maybe what you want is a specialized B tree, in which each node contains as an extra field the largest price in the whole subtree. Whenever the B tree is restructured, all subtrees that are altered will require those fields to be recomputed. In the worst case, all deletions are happening at one end of the tree and all insertions at another... so I don't know if some of the extra balancing work of the tree is significant. After deleting an obsolete item, it would take $O(\log n)$ operations to update the nodes above it. Once a tree is purged of data more than an hour old (and all new data is added), only the tree root needs to be consulted to determine the maximum price in this case.

In all these instances, the best scheme with respect to time might depend on how frequently that price question needs to be answered compared to how frequently new data needs to be input.

I think the space complexities for these approaches are $O(n)$. With regard to space-saving you might think of having a data structure for each period of 10 minutes like so: 1:00-1:09; 1:10-1:19; etc. Then each price record only needs to contain a timestamp relative to the 10 minute threshold. If you precision is 1 sec, then each record only needs to distinguish which of 600 seconds the price is mamixum over. If it takes a second or more to compute the maximum anyway, then it should be precise enough to eliminate data that is 3600 +/- 1 second old.

The time precision is important. Is it close enough to count things minute by minute? If so, then you only need one record for each minute, and you can update the last minute's record with any new data if there are multiple data coming in for that minute. This will affect your storage by a significant factor, but this factor would only be $O(1)$.
> 0 votes

# Answer
I believe you can solve this in $O(\log n)$ time per lookup by casting it as the Manhattan skyline problem where each "building" begins at the timestamp when a data point (timestamp, price) arrives, the height of the building is the price, and the width of each building is 1 hour. Here, n is also the space complexity, equal to the maximum number of events in any 1 hour window.

**EDIT**: Imagine sweeping a line of buildings left to right. The skyline is the outline of the roofs of the buildings. So, during the sweep, we want to output the height of the tallest building at the current point of the sweep.

Equivalently, we are streaming the input points in order of increasing timestamp. Whenever a point $(h, t)$ is encountered, that marks the beginning of a "building" whose time extent is $\[t, t+1h\]$. We want to output the height of the tallest building during the sweep, which corresponds to the maximum value in the previous 1 hour.

One algorithm for Manhattan skyline is to maintain the height of all "active" buildings in a data structure for which fetching and updating the maximum on each insertion and deletion is efficient. A MaxHeap should do the trick. The building corresponding to $(h, t)$ is inserted with value=$h$ at time $t$ and deleted at time $t+1$.
> 0 votes

# Answer
The usual way to do this as a streaming algorithm is to store the entire window, but implement "add" and "evict" operations that are both fast (e.g. $O(1)$). Such operations are a common way to specify sliding window algorithms:

* The *add* function is called whenever an item enters the window;
* The *evict* function is called whenever an item leaves the window.

If we can implement both operations in $O(f(n))$, this implies a streaming algorithm that uses *amortized*$^1$ $O(f(n))$ time to process each element, and $O(n)$ space where $n$ is the maximum size of a window. As others have pointed out, there is no better streaming space complexity than storing all items, in the worst case.

$^1$The reason it is *amortized* constant instead of constant is that it's possible we get a large window built up, and then a single item (say, with a much larger timestamp) requires us to evict the entire window. So in the worst case, one addition to the window operation could take $O(n f(n))$. However, in total, each item is only added and evicted once from the window total, over time, so amortized time is constant.

So, the question that remains is: how do we implement *add* and *evict* efficiently? We can get $O(\log n)$ (maybe $O(1)$ is possible, I'm not sure). There are different data structures that could be used, but one possibility is a priority queue. Specifically, keep track of the priority queue $Q$ and the max $m$.

* To *add* an item with value $v$, add $v$ to $Q$; and if $v \> m$, then set $m$ to $v$.
* To *remove* an item with value $v$, remove $v$ from $Q$. Then, inspect the largest element in the queue, and set $m$ to be that value.

Because priority queues can be implemented with $O(\log n)$ insertion and deletion and $O(1)$ inspection, and $n$ is both the size of the window and the size of the priority queue, this results in an $O(\log n)$ time complexity for both add and evict.
> 0 votes

---
Tags: algorithms, streaming-algorithm
---


# Question
Title: Does it make sense to say Big Theta of 1? Or should we just use Big O?
Does saying $f(x) = \Theta(1)$ provide any extra information over saying $f(x) = O(1)$?

Intuitively, nothing grows more slowly than a constant, so there should be no extra information in specifying Big Theta over Big O in this case.

# Answer
> 16 votes
Remember your definitions! As $n \to \infty$ (the use in CS, almost always) $O(\cdot)$ is an upper bound (within a constant multiple, for large $n$), $\Omega(\cdot)$ is a lower bound (within a constant multiple, for large $n$), and $\Theta(\cdot)$ both of the previous. To see the difference, as $n \to \infty$ you have:

$\begin{align\*} 1 + \lvert \sin n \rvert &= O(1) \\ 1 + \lvert \sin n \rvert &= \Omega(1) \\ 1 + \lvert \sin n \rvert &= \Theta(1) \\ e^{-n} &= O(1) \\ e^{-n} &\ne \Omega(1) \\ e^{-n} &\ne \Theta(1) \end{align\*}$

For the first three, as $\sin x$ moves between -1 and 1, the expression fluctuates between 1 and 2.

To see why $e^{-n} \ne \Omega(1)$ (and so $e^{-n} \ne \Theta(1)$), note that we are looking for a constant $c \> 0$ and an $N\_0$ so that for all $n \ge N\_0$ we have $e^{-n} \ge c \cdot 1$. For any $c$ you pick, you'll find that taking $n \> \ln 1 / c$ makes this false. So no $c$ works.

# Answer
> 14 votes
vonbrand's answer is correct in general, but let me add that **if $\boldsymbol{f(n)}$ is the running time of an algorithm, then you are correct, $\boldsymbol{O(1)}$ and $\boldsymbol{\Theta(1)}$ are the same.** This is because running times of algorithms are positive integers, so the example $f(n) = e^{-n}$ is impossible. As you said, intuitively, nothing grows slower than a constant.

In particular, if $f$ is the running time of an algorithm, then $f(n) \ge 1$ for all $n$, because it takes at least one step for the machine to halt and return its output. From this we can deduce that $f(n) = \Omega(1)$, that is, every function grows at least as fast as a constant.

This assumes that an algorithm's running time can't be zero. If we allow that (i.e., halting doesn't count as a step), then there is exactly one algorithm that is $O(1)$ but not $\Theta(n)$ -- the "do nothing and halt" algorithm. This has running time $0$, which is $\Theta(0)$, not $\Theta(1)$.

# Answer
> 4 votes
The Big O notation is not only used to express algorithm complexity. It is also commonly used to express precision of approximations in mathematics. See for example the Stirling's approximation, which uses $O(1/n)$ as a term explaining how good the approximation is. Then you are not necessarily dealing only with functions that *grow*.

Obviously an $f(n) \in O(1/n)$ is also $O(1)$, and any $f(n) \in \Theta(1)$ is also $O(1)$, but if $f(n) \in O(1/n)$, then it's not in $\Theta(1)$.

If in your context it is clear that $f$ has a positive lower bound (e.g. $1$), then whether you use $O(1)$ or $\Theta(1)$ doesn't matter. But in general, there is a difference.

# Answer
> 1 votes
# Yes, it has additional information.

Consider the following algorithm: "If input N is odd, do something that takes a constant time. If N is even, do nothing." In the odd case, this means that Big O is on the order of 1. In the even case, this means that Big Omega is on the order of 0. This, in turn, means that there is no Big Theta, because there is no function that describes both its upper and lower bounds.

This sort of situation is easier to see when you're dealing with Big O factors larger than 1: for instance, an algorithm that said "If N is odd, add all numbers between 1 and N together and return the result; if N is even, return N" would have a Big O of N and a Big Omega of 1 - and it wouldn't have a Big Theta.

# Answer
> -5 votes
I went and looked it up for this question. "Big Theta" and "Big O" are defined slightly differently, but then found that "Big O" has different definitions depending on where you look.

Depending on who you ask, you can have an amortized "Big O" resulting in O(1) where every n operations, it would have to run a linear step rather than a constant and still label it O(1). We did it this way when I was in college. More information here: https://stackoverflow.com/questions/200384/constant-amortized-time

"Big Theta" is more *precise* in that everybody agrees on its definition in that such steps are not allowed.

---
Tags: asymptotics, big-o-notation
---


# Question
Title: Can we use Big O notation to predict actual running time of the algorithm on machine?
As per my understanding, a program can take a different amount of time to run on different machines because it is dependent on hardware. So we use big O notation which is independent of hardware to compare the performance of two algorithms as the input grows.

I am working on an algorithm which has a complexity of $O( X + Y )$ and it takes a number as an input. My advisor has asked me to collect actual runtime(on the same machine) of the algorithm with different numbers as an input. Then determine coefficients a, b and c such that

$runtime=a.X + b.Y + c$

and use this equation to predict runtime for other inputs. (for instance, consider BFS, in which case $X$ and $Y$ could be replaced by $V$ and $E$ and it takes a source vertex as an input. Now I am asked to record runtimes of the BFS execution using different source vertices as an input and determine the coefficients. The claim is, using the same hardware and same graph but different source vertex I should be able to get a good approximation of the runtime.)

As per my understanding, this approach is incorrect as big O notations are meant for comparison, as the input grows. But my advisor argued that big o notation captures all the operations in the code and therefore there must exist coefficients a,b,c such that the above equation gives a good approximation.

Is the claim made in the above argument is correct?

# Answer
> 2 votes
I'll give you an example where it unexpectedly goes totally wrong:

Write a program that calculates the product of two square matrices with real values, stored as double precision numbers. Use the straightforward algorithm where c \[i, j\] = sum of a \[i,k\] * b \[k,j\]. Measure and print the time for say n = 1 to n = 1000 (this will take a while). The time is $\Theta(n^3)$, so if r (n) is the measured time, you are interested in $c\_n$ where $c\_n$ is defined by $r (n) = c\_n·n^3$.

You will find several interesting effects. You might expect that $c\_n$ is quite large for n = 1, 2, 3 etc. because all the overheads are quite large compared to $n^3$, and at some point $c\_n$ stays quite unchanged.

If you learned about cache memory, you will realise that a modern processor may have say 64KByte of very fast L1 cache, maybe 256KByte of fast L2 cache, say 4M of not so fast L3 cache, and uncached memory is quite slow. So as n grows, $c\_n$ will jump up every time the memory used exceeds one of those cache limits.

But there are worse problems: The naive algorithm uses a really bad pattern to access memory, but how bad it is depends on particular values of n. Worst case is n = multiple of a large power of 2. You can expect the runtime for n = 128 to be massively larger than for n = 127 or n = 129.

So I'd say your advisor is completely wrong.

# Answer
> 0 votes
Big O is for worst case, but here it seems like you are more interested in average case? It is not really clear how the worst case complexity relates to your measurement, not only for the type of reasons gnasher729 described (caching, branch prediction(!)).

For example:

Quicksort is worstcase O(n^2), but the average case is O(n\*log(n)). When you sample the input space and try to fit parameters for `a*n^2 + b` with measured parameters from a function `a*n*log(n) + b` (because what you are doing is more likely to get you average case results), I would not expect sensible predictions.

If worst case vs. average case is no issue, then maybe it is sensible, but only for

1. large inputs, to avoid the technical issues gnasher729 mentions, which will mostly go away once you are big enough that everything is bad and slow. Also, since Big O talks about the limit, it makes sense that the approximated function will only work well for big inputs.
2. many, diverse, examples. To fit anything well you need many examples.

---
Tags: asymptotics
---


# Question
Title: "Visited" vs "Seen" Positions in Breadth-First Search
I'm struggling to understand why there is such a radical difference in the execution time and number of steps required by two seemingly similar algorithms for Breadth-First Search in a 2d grid.

In the Python program below, uncommenting the indicated lines switches between versions.

As well as help with understanding the difference, I would like to know if there is a "canonical" version which is considered best practice. Clearly here the second version performs best, but it is a also different to most of the statements of the algorithm I have found, which add the current node to a "visited" list straight after dequeuing.

## BFS Algorithm

These versions store the whole path at each stage in the queue.

### Version 1

Enqueue a list containing the start position, as the initial path.
while the queue has elements in it:
dequeue the next path
name the last element `frontier`
**add the frontier to a set of visited positions**
check if the frontier is the goal position
if so, return the path
otherwise, check neighbouring cells:
if the cell is legal and is not in the set of visited positions,
enqueue a new path consisting of the current path + this new cell
if no successful path was found, return None

### Version 2

Enqueue a list containing the start position, as the initial path.
while the queue has elements in it:
dequeue the next path
name the last element `frontier`
check if the frontier is the goal position
if so, return the path
otherwise, check neighbouring cells:
if the cell is legal and is not in the set of previously seen cells,
enqueue a new path consisting of the current path + this new cell
**add the current cell to a set of previously seen cells.**
if no successful path was found, return None

import collections

offsets = {
    "up": (-1, 0),
    "right": (0, 1),
    "down": (1, 0),
    "left": (0, -1)
}

def is_legal_position(maze, pos):
    i, j = pos
    num_rows = len(maze)
    num_cols = len(maze[0])
    return 0 <= i < num_rows and 0 <= j < num_cols

def bfs(grid, start, end):
    """
    Bread-First Search in a 2d list. Stores whole paths in queue.
    """
    queue = collections.deque([[start]])
    seen_or_visited = set()

    while queue:
        print("####### While queue is not empty #########")
        path = queue.popleft()
        print("Path", path)
        frontier = path[-1]
        print("Frontier:", frontier)
        seen_or_visited.add(frontier) # Uncomment for version (1)
        if frontier == end:
            return path
        enqueued_this_round = []
        for direction in ["up", "right", "down", "left"]:
            print("### Direction: ", direction)
            row_offset, col_offset = offsets[direction]
            next_pos = (frontier[0] + row_offset, frontier[1] + col_offset)
            if is_legal_position(grid, next_pos) and next_pos not in seen_or_visited:
                print("Enqueueing", next_pos)
                queue.append(path + [next_pos])
                # seen_or_visited.add(next_pos) # Uncomment for version (2)
                enqueued_this_round.append(next_pos)
        print("seen_or_visited:", seen_or_visited, "\n")
        print("Enqueued this round", enqueued_this_round, "\n")

maze = [[0] * 5 for row in range(5)]
start_pos = (4, 4)
end_pos = (0, 0)
print(bfs(maze, start_pos, end_pos))
```
</code></pre>

# Answer
I recommend you to take the same approach as I did to draw my conclusions: take a graphical approach to see the differences and drawbacks.

For that, do the following:

1. Comment out all `print` lines except `print("Frontier:", frontier)`
2. Then do `python program.py > version1.txt`, modify your program such that it represents verison 2, and then do `python program.py > version2.txt`.
3. Get pen & paper and draw a 4 × 4 table.

Here is a comparison of the first lines of both log files:

```
    Version 1           Version 2

Frontier: (4, 4)     Frontier: (4, 4)
Frontier: (3, 4)     Frontier: (3, 4)
Frontier: (4, 3)     Frontier: (3, 4)
Frontier: (2, 4)     Frontier: (4, 3)
Frontier: (3, 3)     Frontier: (2, 4)
Frontier: (3, 3)     Frontier: (4, 4)
Frontier: (4, 2)     Frontier: (3, 3)

```

I leave it as an exercise for you to draw this with pen & paper. Can you take it from here?

Note that the duplicate `(3, 4)` is version 2 is suspicious. Can you guess where it comes from?

> I would like to know if there is a "canonical" version which is considered best practice.

You typically want the invariant that everything in the queue is already put in the seen queue. As a formula, this amounts to saying $$\text{work queue}\ \subseteq\ \text{seen queue}.$$

Otherwise, you could pick the tip of the work queue, say item $i\_1$, go through its neighbors to then add its neighbor $i\_2$ to the work queue. However, $i\_2$ was already part of the work queue before (perhaps just after $i\_1$!), but you couldn't know since you didn't keep the seen queue synchronized.

Hence, implementing this invariant amounts in your code to

* putting start onto the seen queue

```
queue = collections.deque([[start]])
seen_or_visited = set([start])

```
* choosing version 2, i.e.

```
seen_or_visited.add(next_pos) # Uncomment for version (2)

```

You may also want to comment out version 1, i.e.

```
#seen_or_visited.add(frontier) # Uncomment for version (1)

```

since the invariant, fulfilled by the two points above, guarantees that whatever you pick from the queue (here, `frontier`) has already been added to the seen queue.

By the way, your function is missing a `return None` in case it doesn't find the target position.
> 1 votes

---
Tags: algorithms, python, breadth-first-search, maze
---


title: Closure on regular languages

text:
# Question
Title: Closure on regular languages
A) Let $L$ be a regular language. according to the theorem there is an DFA which accepts the language.

Describe shortly how to change the DFA to NFA which Accepts $L^R$, where R is reverse.

There is no need to write how to build formally or proof or correctness.

B) True or False: if $L$ is not regular then $L^R$ is not regular

My solution:

A) First of all because we want Reverse the accepting state would become the start and the rejecting states will become accepting, also change the direction of the edges to the oppositse side. but when it comes to changing it to NFA im a bit stuck.

B) I think its true since it doesnt matter if it reversed if its regular then of course $L^R$ will be regular as well.

Is this the way for A and B?

# Answer
> 1 votes
**A)**

> First of all because we want Reverse the accepting state would become the start and the rejecting states will become accepting, also change the direction of the edges to the oppositse side.

You're almost there. What happens if you have multiple accepting states in the original DFA? That's where you need NFA capabilities to convert them.

Here is a spoiler in case you want to check your answer: Designing a DFA and the reverse of it on ComputerScience.SE.

**B)**

Your answer is true although you might want to phrase it a bit more carefully. We want to prove "if $L$ is not regular, $L^R$ is not regular". So let $L$ be not regular. If $L^R$ were regular, so were $(L^R)^R = L$, which is a contradiction. Hence, $L^R$ is not regular.

---
Tags: automata, computation-models
---


# Question
Title: Minimum number of clues to fully specify any sudoku?
We know from this paper that there does not exist a puzzle that can be solved starting with 16 or fewer clues, but it implies that there does exist a puzzle that can be solved from 17 clues. Can all valid sudoku puzzles be specified in 17 clues? If not, what is the minimum number of clues that can completely specify every valid puzzle? More formally, does there exist a valid sudoku puzzle (or, I guess it would be a set of puzzles) that cannot be uniquely solved from only 17 clues? If so, then what is the minimum number of clues, $C$, such that every valid sudoku puzzle can be uniquely specified in $C$ or fewer clues?

# Answer
> 5 votes
The **fewest** clues required for a **proper** Sudoku is 17, but not all completed grids can be reduced to a proper 17 clue Sudoku. About 49,000 unique (non-equivalent) Sudokus with 17 clues have been found. (A proper Sudoku has only one solution).

The **most** clues in a **minimal** Sudoku is believed to be 40 (two are known to exist), but it has not been proven if this is the maximum. (minimal means that if any clue is removed, the Sudoku would have more than one solution, and therefore not be a proper Sudoku)

(This information is from Wikipedia, of which these statements are well referenced).

# Answer
> 2 votes
Since permuting two rows within a single block of a valid, completed sudoku produces another valid, completed sudoku, you can take any completed board (81 clues) and remove the first two rows (81-18=63 clues), which will give you an incomplete sudoku with two solutions. Note that even if you remove all but one of the 18 numbers there, the solution is immediately uniquely determined (since there can be no number repeated in the same column).

Another operation that produces another completed sudoku is applying a permutation of $\\{1,\ldots,9\\}$. If you take a permutation that is a transposition (permutes two elements, keeping the other fixed), again, as before, you can remove all appearances of those two elements and you have an incomplete sudoku with two possible solutions and 63 clues. Again, if you don't remove all 18 numbers, the solution will be unique.

Of the six elemental operations that produce a completed sudoku (see here), these two are the ones that can involve the least number of elements, so I'd say $C=63$ is an upper bound for what you're looking for. I know this does not exactly answers your question, but the general idea of removing sets of positions which produce two different solutions might be a good starting point.

# Answer
> 0 votes
This Sudoku has 77 clues and yet it has multiple solutions (2). You can use 7-4 on the top row and 4-7 on the other one or using 4-7 on the top and 7-4 on the bottom. This particular Sudoku puzzle needs 78 clues to have a unique solution.

---
Tags: sudoku, combinatorics
---


# Question
Title: Growth of exponential functions according to the big O notation
I'm preparing for an exam and trying to make some sense of the growth of the different exponential functions. I picked the trickiest functions for myself and tried to sort them according to the big O notation. Since it's hard to use L' Hospital's rule on exponential functions I at least want to get a feeling for the order of growth.

$$ n^2 = O(ln(n) ^ {ln(n)}) = O(n^{ln(n)}) = O(2^{\sqrt{n}})=O(2^{(n/2)}) = O(n ^{\sqrt(n)}) = O(n!) = O(n ^n) $$

I'm particularly unsure about the right place of fac(n). Can anyone verify if that is correct?

# Answer
> 3 votes
You swapped two functions. Notice that: $$n^{\sqrt{n}} = 2^{\sqrt{n} \log n } = o(2^{\frac{n}{2}})$$.

Once this is fixed, the factorial is in the correct order since very rough inequalities show that $$n! = n \cdot (n-1) \cdot \ldots \cdot 2 \ge \underbrace{2 \cdot 2 \cdot \ldots \cdot 2}\_{n-1 \text{ times}} = 2^{n-1} = \omega(2^{\frac{n}{2}}),$$ and $$n = n \cdot (n-1) \cdot \ldots \cdot 2 \le \underbrace{n \cdot n \cdot \ldots \cdot n}\_{n-1 \text{ times}} = n^{n-1} = o(n^n).$$

In general, from Stirling's approximation you know that $n! = \Theta( \sqrt{n} \cdot (n/e)^n )$.

---
Tags: asymptotics, big-o-notation
---


title: What kind of Grammar could this be

text:
# Question
Title: What kind of Grammar could this be
I am trying to sort Grammar into the Chomsky Hierarchy and I can do so for most of my examples but I am stumped by the following one:

`bX -> abY`

which Type of Grammar would this be, unrestricted grammar, context-sensitive grammar context-free grammar or regular grammar

Thank you for your help

# Answer
The definition of context-sensitive grammar requires that every production be of the form

$$\alpha A \beta \to \alpha \gamma \beta$$ where $A \in N, \alpha,\beta,\gamma\in (\Sigma\cup N)^\* \text{ and } |\gamma| \ge 1$.

Assuming $\Sigma=\\{a,b\\}$ and $N=\\{X,Y\\}$, the production $bX\to abY$ does not satisfy this criterion. The only possible decomposition of the left-hand side is $\alpha=b,\beta=\epsilon$, and that doesn't match the right-hand side. So it's not a context-sensitive grammar.

However, that doesn't stop the language generated by that production from being context-sensitive. There is an alternative characterisation of grammars (which is, in fact, often used instead of Chomsky's original context-sensitive criterion), which are the *non-contracting* grammars. A non-contracting grammar consists only of productions of the form $\alpha\to\beta$ where $\alpha,\beta\in(\Sigma\cup N)^+\text{ and }|\alpha|\le|\beta|$. These grammars are *weakly equivalent* to context-sensitive grammars; in other words, for any context-sensitive grammar, there exists at least one non-contracting grammar which generates the same language, and vice versa. (This is a weak equivalence because the grammars don't produce the same derivations.) Furthermore, there is a mechanical procedure which can convert a non-contracting grammar into a context-sensitive grammar.

The production you ask about is certainly non-contracting, so (unless other productions in the grammar are contracting) the language is context-sensitive.

If this question appears on a test or class assignment, you should verify which definition of "context-sensitive grammar" your professor uses. Because of they generate exactly the same languages, and because non-contracting grammars are often easier to write, some people use the non-contracting criterion as a definition of "context-free grammar".
> 1 votes

---
Tags: formal-grammars, functional-programming, chomsky-hierarchy
---


title: Recognizing a trajectory from a set

text:
# Question
Title: Recognizing a trajectory from a set
Given a set of 2d trajectories/paths, where a trajectory is a list of \[x,y,time\] coordinates, and a new trajectory, how can I recognize which one in the set is most similar to it? The lists may not be of the same length, the time differences not the same.

I've tried using perceptual image hashes of the resulting lines, but this approach seems unreliable.

The measure of similarity should be scale and translation, but not rotation invariant.

I'm trying to recognize 2d gestures that are input with a mouse or touchpad in order to execute commands\[0\]. For this application, the velocity/acceleration of the movement will not matter.

I found this library that contains a few algorithms: https://github.com/bguillouet/traj-dist

\[0\] https://github.com/void4/termagic

# Answer
The Fréchet distance is a similarity measure for trajectories that often works well for curves that we consider visually similar. However, it is not scale or translation invariant, because it compares the distances between the points of the trajectories.

You can try the Direction-Based Fréchet Distance, introduced in this paper by de Berg and Cook. This is a variant of the Fréchet distance that is based on the directions of movement instead of the points directly. This means that it is both scale invariant and translation invariant, but not rotation invariant.

---

Another possible approach that may be easier to implement if you have a library that can compute Fréchet distance and DTW1 distance between a pair of trajectories, is to first translate the pair of trajectories such that the first points have the same position, and then scale the trajectories such that the distance between the first and last point of the trajectories is the same in both trajectories. If you compute either the Fréchet distance or DTW-distance after these transformations, the total measure will be scale and translation invariant.

1: DTW (Dynamic time warping) is similar to the Fréchet distance, the main difference is that the Fréchet distance is a bottleneck measure, while DTW is not. In other words, only the 'most dissimilar parts' of the trajectories determine the Fréchet distance, while DTW takes the entire trajectory into account.
> 2 votes

---
Tags: algorithms, computational-geometry, pattern-recognition
---


# Question
Title: Complexity of finding factors of factors of N number
```
for (int i = 1; i <= N; i++)
    for (int j = i; j <= N; j+=i)
        for(int k = j; k <= N; k+=j)

```

How to express this mathematically to calculate the complexity of the above code. I guess, its complexity is $O(N\log\log N)$ but couldn't prove it mathematically!

# Answer
For each value of $j$, the inner loop runs for $O(N/j)$ iterations. Fixing $i$ and varying over all $j$ in the middle loop, the total number of iterations in the inner loop is $$ O(N/i + N/(2i) + N/(3i) + N/(ki)) = O(N\log k/i), $$ where $ki$ is the maximal multiple of $i$ which is at most $N$. We can bound $k$ by $N/i$, and so the expression above equals $O(N\log (N/i)/i) = O(N\log N/i)$. Summing over all $i$ from 1 to $N$, we get $O(N\log^2 N)$.

Using rudimentary calculus (approximating the sum by an integral), you can show that if you sum $N\log (N/i)/i$ over $i$ from 1 to $N$ then you still get $\Theta(N\log^2 N)$, and so the bound above should be tight.
> 0 votes

---
Tags: time-complexity
---


# Question
Title: Covering maximal number of sets using fixed number of elements
I've encountered some problem which seems general enough to have already been solved.

There is a set of objects $O=\\{o\_1, o\_2,\dots,o\_k\\}$ and a family of sets $A\_1,A\_2,\dots,A\_t \subseteq O$.

For every $1 \leq j \< k$ we need to find a subset $O' \subset O$ of size $j$ maximizing the number of sets $A\_i$ contained in it.

What is the best algorithm to solve this? I've been thinking about reducing it to a problem in graphs or flow networks but still haven't arrived at a solution.

# Answer
Your problem is essentially Minimum $k$-Union. In this problem (switching from $k$ to $\ell$), you want to find $\ell$ sets out of $A\_1,\ldots,A\_t$ which together cover the least number of elements. Denoting by $f(\ell)$ the solution of this problem and by $g(j)$ the solution of your problem, we have $$ f(\ell) \leq j \Longleftrightarrow \ell \leq g(j). $$ In other words, $g(j)$ is the maximal $\ell$ such that $f(\ell) \leq j$.

Unfortunately, Minimum $k$-Union is NP-hard. You can find some links in this question on StackOverflow.
> 0 votes

---
Tags: algorithms, graphs, optimization, reductions, network-flow
---


# Question
Title: Allocating tasks among two people equitably
Given that we have 2 people, and 2n tasks, find the minimum time to complete the tasks. Both persons should solve exactly n tasks each and any task j has to be solved before task j+1. Required time complexity is O(nlogn). E.g- given this input:

A B

5 3

2 1

3 2

1 2

the intended output is 8, because A solves the second and fourth task, and B solves the first and second.

# Answer
> 1 votes
Suppose that the time for completing task $i$ is $a\_i$ for $A$ and $b\_i$ for $B$. Let $S$ be the set of tasks performed by $B$. The total time required is $$ \sum\_i a\_i + \sum\_{i \in S} (b\_i-a\_i). $$ Your goal is then to find a subset $S \subseteq \[2n\]$ of size $n$ which maximizes $\sum\_{i \in S} (b\_i - a\_i)$. You take it from here.

---
Tags: algorithms, greedy-algorithms
---