title: Combining fork() and algorithms

text:
# Question
Title: Combining fork() and algorithms
Today in my algorithms class, my professor explained how in divide and conquer algorithms we do things in "parallel" although I felt it was not exactly in parallel. Then I remembered from OS the fork() system call that creates literally another child process and computes in parallel with the parent process. Can we combine these two to give an algorithm that betters the usual Time complexity?

Although I just realized we have to wait for the child process to complete before the parent, still, some amount of computation can be done in parallel or is there something I am missing?

PS: I am new to this platform so sorry if this isn't the type of questions to be asked here

# Answer
> Can we combine these two to give an algorithm that betters the usual Time complexity?

The key to your question is "what do you mean by time complexity?" Often it is quite clear, and we don't have to state it, but other times we do need to be careful.

Sometimes the thing you are interested in is the complexity class measured in number of operations. In these cases, forking does not help. You still have to do the operations. Other times, you are really-truly interested in the run time of the algorithm with respect to "wallclock" time. In these cases, you can reduce the run time by *up to* a factor of $n$, where $n$ is the number of processes.

Not all algorithms can be reduced by a full factor of $n$. In fact, in cryptography, there is a great interest in algorithms that are so mind-numbingly serial that no amount of parallelization can speed them up (such algorithms offer protection against giant clusters of GPUs pounding away at them). On the other hand, we have the class that can be reduced by $n$, for any $n$ you choose. These are known as "trivially parallelizable" problems, and we stop talking about how long the algorithm takes and start talking about how large your wallet is. One doesn't always have infinite computing capacity handy! Computing resources cost money!
> 4 votes

# Answer
Many divide-and-conquer algorithms are actually implemented sequentially, and the idea of working on each half "in parallel" is more to help with conceptual understanding than an actual implementation practice.

That said: yes, you are quite right, often it is possible to implement these steps concurrently / in parallel. The details can be tricky, because they require coordination and synchronization between the concurrent threads, consideration of the effect on the memory hierarchy, and there is some performance overhead associated with these issues. Working through those details requires understanding the processor architecture and memory hierarchy at a low level of detail. Introductory algorithms courses usually work at a higher level of abstraction, and so do not consider these issues.
> 2 votes

---
Tags: algorithms, time-complexity, algorithm-analysis, optimization, operating-systems
---


# Question
Title: How does GHC insert type abstraction/application under the RankNTypes extension
I'm developing a functional programming language that offers Rank-n polymorphism. Like Haskell I don't want types to appear at the term level, but I have no idea to insert type abstraction and type application in a term afterward.

For example, identity function is defined like below in Haskell.

```
id :: forall a. a -> a
id = \x -> x

```

But in lambda calculus which is adopted as Haskell's core language, this represents `id = ΛT. λx:T. x` (`ΛT` is a type abstraction). And following function

```
foo :: Int
foo = id 3

```

is translated into `foo = id @Int 3` in the core language (`@Int` is a type application)

Inserting type abstraction looks simple (just inserting `ΛT` in the place corresponding to `forall a.`), but type application is complicated because you have to decide not only where to apply the type but also what type to apply.

Although visualization of type application is discussed on this web page, I have not been able to find any document that describes an implicit insertion algorithm of type abstraction/application. It would be great if you could just give me a hint of the algorothm.

# Answer
The one key thing that you need to do differently to support GHC-style rank-N types is use the user-supplied type signatures to guide the process of translation to System F. In ordinary Hindley-Milner type inference, that's optional: you can instead infer your own type and then unify it with the user-supplied type after the fact. With rank-N type signatures it's mandatory, as you'll generally end up inferring an incompatible type otherwise.

The specific cases largely write themselves, but here are some key examples:

* If you have a term $e$ with the known (user-supplied) type $\forall α. T(α)$, then the System F translation is $Λτ.$ prepended to the result of translating $e$ with the known type $T(τ)$, where $τ$ is a fresh rigid type variable.
* If you have a term $λx.e$ with the known type $S\to T$, then the translation is $λx{:}S.$ prepended to the result of translating $e$ with the known type $T$. Note that $S$ may contain $\forall$, so variables without type signatures can end up with higher-rank types inherited from a type signature on a containing term.
* If you have a term $x$ (an identifier), and $x$ in the environment has the type $\forall α\_1\cdots α\_k. T(α\_1,\ldots,α\_k)$, then translate to $x@τ\_1@\cdots@τ\_k$, where $τ\_1,\ldots,τ\_k$ are fresh flexible type variables, and return the type $T(τ\_1,\ldots,τ\_k)$ for that term. The actual types to be applied are determined by unification.

For instance:

* Type checking $λx.x$ with the type $\forall α. α\to α$ results in $Λτ. λx{:}τ. x$ by the first two rules.
* Type checking $\text{id}$ with $\text{id}:\forall α. α\to α$ in the environment results in $\text{id}@τ$ by the third rule, and $τ$ will at some point be unified with $\text{Int}$, so you will end up with $\text{foo} = \text{id}@\text{Int}\\, 3$.
* For an actual higher-rank example, type-checking $λx.x$ with the type $(\forall α. α) \to (\forall β. β)$ results in $λx{:}(\forall α. α). Λτ. x@τ$.

The ugliest case is actually in standard H-M inference when you have mutually recursive functions with no type signatures. Since you haven't yet generalized them, you can't know whether type applications will need to be inserted at the recursive call sites, so you have to do a second pass after generalization, or extend your intermediate language in some way to avoid it. You don't have that problem with rank-N inference because the signature tells you where the type applications go.
> 2 votes

---
Tags: lambda-calculus, type-theory, type-checking, haskell
---


title: search with inadmissible heuristics

text:
# Question
Title: search with inadmissible heuristics
I was told that search algorithm such as IDA\* or Beam Search with any inadmissible heuristic is not guaranteed to find a solution. Can someone explain why that is the case? I was thinking sure the solution may not be optimal as the agent is too pessimistic to try out a potentially optimal path, but as least it will try some path and which could be a sub-optimal solution (i.e. the search algorithm is at least sound and complete)?

# Answer
Beam Search can fail to find any solution even with an admissible heuristic. (Suppose the beam has width $k=1$ and the root node has two children, $a$ and $b$, with $b$ being a solution and there is no solution reachable from $a$. Let $C(v)$ be the true cost of an optimal solution via vertex $v$ and $\infty$ if no solution via $v$ exists, and $H(\cdot)$ be an admissible heuristic for $C(\cdot)$. Then it could be that $C(a) = \infty$ but $H(a) \< H(b) \le C(b) \< \infty$, in which case the only solution, $b$, is discarded immediately.)

IDA\* will find a (possibly suboptimal) solution if an inadmissible heuristic is used.
> 2 votes

---
Tags: search-algorithms, heuristics
---


# Question
Title: I need help finding the complexity of an algorithm
i have the following algorithm :

j = 1 while j ≤ n do j = 2^j

where n is our input and is a non negative integer

I found the complexity of the algorithm to be O(1) . Can someone tell me if this is correct and if not can you tell me the right answer and explain the way you found it? Thank you.

# Answer
The base-2 iterated logarithm function $\log^\*(n)$ is the number of times you need to apply the logarithm function to obtain a value that is at most $1$. It is a very slowly growing function. The answer seems to be $O(\log^\* n)$.

See \[CLRS, Section 3.2, p. 58-59\], which states that the number of atoms in the observable universe is about $10^{80}$, which is much smaller than $2^{65536}$ (whose iterated logarithm is $5$). Hence, for any practical input size $n$, your algorithm would have at most $5$ iterations, and so it is ok to take the running time of the algorithm to be $O(1)$.
> 3 votes

# Answer
No, the complexity cannot be constant, because the iterations $j = 2^j$ always yield a finite integer, and there is always a larger $n$. So the number of iterations is unbounded.

Anyway, as the required n grow astronomically fast (see below), the number of iterations grows extremely slowly.

The iterates are

$$1, 2, 4, 16, 65536, 2.0035299304\cdots\cdot 10^{19728},$$ and there is no way to write down the next value.
> 2 votes

---
Tags: time-complexity
---


# Question
Title: Does this DFA prove closure under Perfect Shuffle?
I'm self studying Introduction to Theory of computation and I'm a bit confused about a problem definition. I'm trying to understand and verify whether my proof is correct or not.

**Question**: Prove that the regular language is closed under perfect shuffle

The perfect shuffle between two languages $A$ and $B$ is defined as:

$$\\{w | w = a\_ib\_i\cdots a\_kb\_k\\}, \text{ where } a\_1\cdots a\_k \in A \text{ and } b\_1\cdots b\_k \in B \text{ and each } a\_i, b\_i \in \Sigma\\}$$

**Proof**:

If $A = (Q\_A, \Sigma\_A, \delta\_A, l\_0, F\_A)$ and $B = (Q\_B, \Sigma\_B, \delta\_B, m\_0, F\_B)$

Let $M = (Q, \Sigma, \delta, q, F )$ be the machine recognizing the closure of the language.

where,

1. $$Q = Q\_A \cup Q\_B$$
2. $$\Sigma = \Sigma\_A \cup \Sigma\_B$$
3. $$q = l\_0$$
4. $$F = F\_B$$
5. And

$$ \delta = \begin{cases} \delta\_1(q\_i, r), & \forall r \in A \\ \delta\_2(q\_i, r), & \forall r \in B \end{cases}$$

where, $\delta\_1(q\_i, r) = l\_i, \text{ where } l\_i \in B$ and $\delta\_2(q\_i, r) = m\_{i+1}, \text{ where } m\_{i} \in A$.

The confusion about the correctness of proof primarily stems from $F = F\_B$ is this something that is true in my DFA of perfect shuffle?

# Answer
This does not work, I am afraid. Your state space is the union $Q\_A\cup Q\_B$ of the individual spaces, it should be the direct product $Q\_A\times Q\_B$ instead. See for example this answer: Zigzag concatenation of two languages. The reason is that one should also remember the state of the other automaton when switching between the two.
> 3 votes

---
Tags: finite-automata, closure-properties
---


# Question
Title: Finding the runtime out of a recursion formula when using divide-and-conquer
In divide-and-conquer, one uses the following formula to find the runtime:

$$T(n) = aT(n/b) + f(n).$$

I am confused with the meaning of the constants $a$ and $b$, as well as by the question of how to find $f(n)$. The textbooks could not help me. In exercises, one usually gives this data and asks about the runtime. The master theorem then provides the cases based on these values.

Let's take the following example. Given a square of length $n = 2^k, k \in \mathbb{N}$, I need to divide it into 4 equal squares by a horizontal and vertical line crossing each other in the center. I will proceed like this in each smaller square until I get a square of length 2. How do I get $a$, $b$, $f(n)$, and eventually the runtime?

# Answer
Your example is a bit weird, because you are not describing a problem you are trying to solve for a given length $n$… For the explaination, suppose you want to count the number of ships (like in battleship game) present in the square. Suppose, for simplicity purposes, that no two battleships touch each other.

* $a$ is the number of subproblems, aka the number of times you have to make a recursive call. Here, since there are $4$ smaller squares, that would mean $a = 4$ ;
* $b$ is the factor by which the size is divided. Since you consider the length of the square, the $4$ smaller squares are of length $\frac{n}2$. That means that $b = 2$ ;
* $f(n)$ is the additionnal time needed to reconstruct a solution of size $n$ given all solutions of size $\frac{n}b$. Here, you have to add all solutions, but there could be some duplicates, for example if a ship has parts of it in two adjacent squares. To substract those, you would need to go over all four borders and verify if there is a ship across the border. You would need $\mathcal{O}(n)$ time to make this verification.

Overall, the complexity would verify : $T(n) = 4T\left(\frac{n}2\right) + \mathcal{O}(n)$.

To solve it, you can use the master theorem. You get $T(n) = \mathcal{O}(n^2)$.
> 1 votes

# Answer
**Hints:**

You can guess this information from the equation itself.

In $T(n)$, $n$ denotes the size of the problems. So in $T\left(\dfrac nb\right)$, $\dfrac nb$ must be the size of the subproblems.

Now the $a$ in $aT\left(\dfrac nb\right)$ must be the number of subproblems that are effectively solved.

Finally, $f(n)$ is an extra cost attributed to the divide and the conquer operations.
> 0 votes

---
Tags: time-complexity, runtime-analysis, recurrence-relation, recursion
---


# Question
Title: How can information be updated in blockchain?
I am learning about blockchain and I've read that blockchains are immutable. Suppose my health information is stored on a block and I have gotten diagnosed with a disease and now my information needs to be updated. I have read online (here) that to do this we have to create a new block with the updated data and the previous block is marked invalid. But now isn't it possible that someone could add a new block with my incorrect data and claim that it is the updated one and then my original data block would be invalid?

# Answer
Yes, absolutely. You are right. You can think of a block-chain like an "append-only log": anyone can append a log entry saying anything. That will give you a reasonable intuition.

If you want to use it for something useful, you'll probably need to introduce extra checks. For instance, perhaps you can sign your health record with your private key. To update it, you append a new block that has new information, also signed. If we agree to only use the most recent (last) block and ignore all previous ones, this lets you update prior information by appending a new block. Also, because of the digital signature, someone else who doesn't know your private key then can't append something with the correct signature. Exactly what extra stuff you need will depend on the particular application.

Blockchain is not magic. Contrary to what some might have you believe, it doesn't somehow solve all the security problems in these various applications. It is just a technical tool that can be used in combination with many other techniques as part of a larger system.
> 0 votes

---
Tags: blockchain
---


title: Title matching against human input

text:
# Question
Title: Title matching against human input
I am attempting to match human input of titles to a list of titles, and also show likely candidates when a human enters a title not known. Ideally I'd also have some way to suggest the human input of a truly novel title matches no known title as well.

As an example, I have a list of titles like this:

```
The Conspirators
The Count of Monte Cristo
The Three Musketeers
The Fencing Master

```

Only, my real list of titles is on the order of tens of millions long, and includes titles in different languages, including non Latin based languages.

And, as a human enters titles like these, I am attempt to find the proper name, here are examples of what humans might enter for `The Three Musketeers`:

```
The Three Musketeers
The 3 Musketeers
Three Musketeers, The
The.Three.Musketeers
the-three-musketeers
thethreemusketeers
The Three Musketeers-1844
Three Musketeers
THE THREE MUSKETEERS

```

For lack of a better term, at present, I'm attempting to "normalize" the titles. For instance, that means I:

* Convert input to a known case
* Remove why whitespace (or characters acting like whitespace, like the `-` and `.` above)
* Remove extraneous information (like `1844` above)
* Fix up common issues, like replace `and` with `&`
* Other domain specific fix-ups

This is done once on the known good titles, and whenever a user enters a title, a simple database lookup is done. In the case of multiple titles matching, domain specific guesses are made (for instance, a book with more reviews wins over other options).

This works, but it requires a lot of custom logic in the string normalization, and what's worse, it requires knowledge of multiple languages. And if users suddenly start following a new trend, like as a made up example, use `=` instead of spaces, then there needs to be a feedback loop where someone reviews common "misses" in the search and updates the string normalization logic.

Some other options I've briefly looked into:

* Phonetic matching algorithms, like Soundex. These sometimes work, but some of the human input doesn't sound like the target word, and these systems tend to require I know the target language, which I don't always know.
* Machine Learning. I'm at a loss here, most of the systems I've read about require cleaning of human input, which if I can do, I can match without any ML systems.
* n-gram based fuzzy matching. Much like the phonetic matching systems, this requires knowing the language, and cleaning up the text to some degree beforehand. Also, most of the systems seem to require a lot of compute power to perform the lookup, which is a concern.

Are there better techniques to apply to this problem to find the real title from the human input?

# Answer
First preprocess the string to normalize it (casing, no digits, unique separators...). You do this for the database of known titles, and for the input string to be matched. It might also be of interest to discard the articles/prepositions/connectors as they convey little semantic information.

Now you can use the string edit distance on two levels:

* word level, to deal with spelling variants or mistakes; an input word can result in several matching candidates;
* sentence level: you only need to accept the very short edit distances; but you should try with all candidates found at the word level.
> 1 votes

# Answer
One plausible approach is to use edit distance to measure the similarity of two titles. You might want to adjust it to reduce the penalty for capitalization (e.g., changing x to X might cost 0, or some very small amount).

Then, given a human-entered title, you need a way to find the closest match in the database. There are various data structures and techniques for this. See, e.g., shingling, BK trees, metric trees, Efficient map data structure supporting approximate lookup, Efficient data structures for building a fast spell checker, https://cstheory.stackexchange.com/q/4165/5038, http://norvig.com/spell-correct.html.

Another heuristic might be to extract each word from the human-entered title, canonicalize it (e.g., spelling correction, lower-case it, etc.), then look it up to find the first 1000 titles in the database that contain this word. Take the union of those titles from the database, compare each to the human-entered title using edit distance, and keep the closest match.
> 0 votes

---
Tags: algorithms, string-matching, fuzzy-logic
---


# Question
Title: Determine the number of elements that is divisible by a prime number in an array
I have an array (|A|≤10^6) of numbers (not guaranteed to be distinct) and a set of prime numbers. For each of the prime numbers, I want to know how many numbers in the first array are divisible by this prime number. For example:

> Array = {5 5 7 10 14 15}
>
> Set = {2 3 5 7 11}
>
> result:2:2; 3:1; 5:4; 7: 2; 11:0

Brute force by using nested loops works, but is there a faster way?

# Answer
> 0 votes
Yes if the number of integers and primes is large. Sort the primes in ascending order. Count the number of divisible numbers and remove prime factors until the numbers are all larger than the square of the smallest remaining primes. Now the remaining numbers are all primes. Sort them and check which ones are in the list of primes, in linear order.

This works as long as most primes are greater than the square root of the largest number.

# Answer
> 0 votes
If both lists, let's call them A,P, are sorted as it appears to be:

* Whenever you find A\[i\] divisible by P\[j\] replace it by A\[i\]/P\[j\]
* If a number A\[i\] reaches 1 or become smaller than P\[j\] exclude it from further checks
* A draft Pseudo code would be:

i=j=0;

Repeat
{
While (A didn't finish) {
If (A\[i\] mod P\[j\] == 0) {
C\[j\]++;
A\[i\]=A\[i\]/P\[j\];
If(A\[i\]≤P\[j\]) remove A\[i\];
//endif}
i++;
//endwhile}
j++;
i=0; //or startup mark
//endRepeat
} Until ( A or P ends)

# Answer
> 0 votes
If the equal values are dense (say if the number of distinct values is less than a quarter of the array size), it could be worth to sort and determine the multiplicities. If they are sparse, sorting could be counterproductive.

This said, counting the divisors for a value does not help counting those of other values. So for every value, there is not much better than trying all divisors in turn and stop when the quotient gets too small.

Depending on the distribution of numbers, it could be advantageous to try the divisors in some order rather than another. This needs to be tested experimentally.

If you know that some divisors are rarely met, it could be useful to try the GCD with the product of the rare factors to eliminate them quickly.

# Answer
> -1 votes
OP asked: Given numbers $A\_i$, and a prime $P$, determine for each $p \leqslant P$ how many of the numbers $A\_i$ are divisible by $p$.

> set counter for each $p$ to $0$.
> remove all $A\_i ≤ 1$
> for $p = 2, 3, 5, 7, \ldots$ as long as $p \leqslant P$
> iterate through values $A\_i$.
> if $A\_i \< p^2$
> $A\_i$ is prime
> if $A\_i ≤ P$ increase counter for $A\_i$
> remove $A\_i$
> if $A\_i$ is divisible by $p$
> increase counter for $p$
> divide $A\_i$ by $p$ until it is not divisible by $p$
> if $A\_i = 1$ then remove $A\_i$

Some time will be saved compared to brute force because we eliminate all entries $A\_i \< p^2$ quite quickly.

We can save more time if there are many entries $A\_i \geqslant p^2$: If we have removed all factors 2, then the numbers divisible by $p$ are $p^2$, $p^2 + 2p$, $p^2 + 4p$ etc. If the number of $A\_i$ where $p^2 \leqslant A\_i \leqslant p^2 + 2kp$ is much larger than $k$, then we can put all the $A\_i$ into a hash table and look up the multiples of $p$ in the hash table, which will be faster than division if there are **many** numbers in that range.

---
Tags: algorithms, primes
---


# Question
Title: Are linked lists homogenious or heterogenious containers?
I have always assumed that "Linked List" is something in the lines of

```
struct Node
{
    SomeClass payload;
    Node * next = nullptr;
    Node * prev = nullptr;
}

```

This implies the restriction of working with objects of only one type. Considering lists are horrible in access time I doubt anyone really constructs them on the **stack**. Arrive the conclusion that each node could be of different size. This probably possible with std::any. But in pure `C` one would need an additional redirect `void * payload`; or to loose type safety by converting the whole `Node *` to `void *`. In other words: possible but difficult.

Is there some inherent characteristic of lists which mandates they be as restricted as arrays or am I observing pure coincidence?

# Answer
> 3 votes
You say "linked list" without mentioning a computer language.

First, a "Node" is not a linked list. It is a helper struct that may be useful to create a linked list, but it is just a wrapper around some thing with additions so it can be made part of a linked list.

In Objective C or in Swift, you'd declare Node as something based on SomeClass, say in Swift struct Node { ... }. An important change that you would make: You'd put the two Node\* first. That's because this means the Node\* are always at the same offset; there will be many situations where the generated code will be identical for different classes, and Swift guarantees that code is not duplicated in such a situation.

In both languages, you can also declare the payload to be of type "id" in Objective-C, or "kindof whatEverClass" in Objective-C, or "Any" in Swift. In that case the payload can be anything (including different types) in Swift, and any object pointer, or any subclass of whatEverClass in Objective C.

In general, if you want a class "linked list", you just make sure it implements what is needed, like first, last, next, previous, insert, remove, lookup. The implementation is up to you. If I had to implement it for general use, I'd probably implement it using a series of arrays. So if you start with an empty list, one array would be allocated if you only add elements and remove items at the start or the end of the list. Operations in the middle of the list could allocate a second array. For the user, it would behave like a linked list, just more efficient then a naive linked list.

---
Tags: data-structures, type-checking, linked-lists
---


# Question
Title: Algorithmic challenge: generate a list of random non overlapping squares
For an undisclosed reason, I need a list of $n$ squares in a two dimensions space where each square does not overlap.

So the challenge is simply: given a two dimensional area $a$ (`topLeft: int, topRight: int, width: int, height:int`), a number of squares required $n$ and a size for each square $s$: generate a list $L$ of $|L|=n$ squares in $a$ where the following condition holds. $$\forall q,r \in L , q \neq r \implies \textrm{no\_overlap}(q,r) \land \textrm{inside}(q,a) $$ where `no_overlap` is a function that checks if square $q$ and $r$ do not overlap given the size $s$ and `inside(q,a)` checks if square $q$ is completely inside the area $a$.

I tried coming up with a solution myself but the only thing I can find is to brute force generating a square, check if there is overlap and if not ,add it to $L$. But as one might see, this algorithm could theoretically run forever. I would need something which is guaranteed to work in a finite time and preferably be of a complexity of at most $\mathcal{O}(n^2)$. So I thought to myself, maybe I could share this with other people around the world and see what clever ideas they have in mind. I most certainly find it an interesing theoretical question to ask. The practical reason is for a Unity 3D (game) project I am making.

EDIT: This would be a possible solution graphically illustrated for $n=7$

# Answer
> 1 votes
Factor $n$ as the product of two numbers roughly proportional to the rectangle sides, adding a few units if necessary. Let $n+r=n\_xn\_y$.

Now fill $n\_x$ columns one square large, that occupy the whole width, with free space to the right. You can space them randomly in the vertical direction. Then for every square, scanning by columns from the left, apply a random horizontal displacement that is limited to the next column. This guarantees no collision and takes linear time in $n$.

This is not "maximally random", because the columns remain separable by a vertical line.

# Answer
> 0 votes
You could perhaps use a 2 dimensional k-d tree to store the set of free positions $(x, y)$ where the left upper corner of a new square could be chosen without overlapping the existing squares. Each node of the tree covers a region in the area $a$ and you can decorate this node with this region's coordinate and the number of free positions that it contains. At the top of the tree, you can read the total number of available slots and simply choose a random number to get the index of that slot. By walking downwards in the tree, you can find which slot corresponds to this random number, then update the tree accordingly to add a new square.

My intuition is that the amount of data contained in the tree is approximately proportional to the number $k$ of squares already chosen and that the addition of a new square should be proportional to $\log k$ on average.

Edit: I wrote a working implementation in python 3 by using a tree structure. I'm not sure about the performance for large $n$ but it could already be measured experimentally. I didn't make any effort to balance the tree but as new squares are chosen randomly, this randomness should balance the tree on average.

Here is a link to the program. I don't know if I can paste it in this post. It chooses randomly at most 10 squares that don't touch each other. Here is an example output

---
Tags: algorithms, search-algorithms, randomized-algorithms, randomness
---


# Question
Title: Reference request: Time and proofs of a shared past
*(Short discaimer: I'm a mathematician by education (category theory, algebraic geometry) and so mostly unaware of how different fields in CS relate to each other. I'd be very happy to just get some directions. Also I'm not sure if the tags I added to the question are all correct.)*

My question is concerned with information in distributed systems in relation to time. And I guess it also goes into the direction of blockchains.

**Question:** Is there research that deals with something along the lines of the following class of structures?

* The core items are triples `(i, t, p)` where `i` is a piece of information (think string, JSON blob, etc.), `t` is a *"point in time"* and `p` is a proof that we interpret as *"`i` existed after `t`"*.
* A relation `~<` on all `t` where `t1 ~< t2` is interpreted as *`t1` was before `t2`*. (I'm not requiring that this relation is a linear order at this point. Not even that it's transitive or antisymmetric. But I guess it should at least be reflexive).
* Some check `is_legit(i, t, p)` that tells us if `p` actually is a correct proof of "`i` existed after `t`".
* Additionally, some form of algebraic structure: Given two such triples `(i1, t1, p1)` and `(i2, t2, p2)` we'd want to build a new triple
```
( i1, shared_past(t1, t2), combined_proof(p1, p2, i2))

```
with the property that firstly `t1 ~< shared_past(t1, t2)` and `t2 ~< shared_past(t1, t2)` and secondly that the new triple `is_legit` if and only if the two inputs are legit.

Clearification: I don't expect the definition above to be *the correct one*. Rather, I hope it outlines the flavour of things I'm interested in.

# Answer
> 1 votes
The happened-before relation is a standard mathematical tool for reasoning about time ordering of events in distributed systems. You can find a lot of development on foundations of it, tools for tracking it, and systems built on this concept.

Timestamping is one way to prove that information existed at a certain period of time. You can trawl through https://crypto.stackexchange.com/questions/tagged/timestamping and https://security.stackexchange.com/questions/tagged/timestamp to find some research on that. This might be one way to implement the "proof" notion you are looking for.

Lastly, you might be interested in "timeline entanglement" - that might be exactly what you are looking for, in merging two different timelines/events/histories.

Combining those two might give a starting point towards what you are hoping for; or a foundation and a language for expressing what properties you want from a scheme.

---
Tags: distributed-systems, information-theory, blockchain
---


# Question
Title: Solving an ambiguity concerning unsigned and signed integers
I am taking a class in computer science and I am not sure about the following. When one transforms $247\_{10}$ into its binary counterpart one gets $11110111\_2$. However, the same binary number corresponds also to$-9$ when the 2-complement representation is considered. How does the computer know which of the two numbers we mean, or eventually how one can know which of the two numbers is meant ? If we provide to the machine $-9$ it is then clear how to proceed to get the binary, but after a certain number of arithmetic if the computer gets as a result $11110111$ how it will make it to provide the correct decimal number, i.e. 247 versus -9 ? Thanks.

# Answer
> 1 votes
As far as a CPU is concerned, everything is bits/bytes/words in memory. It doesn't "know" what the contents of a memory location means.

CPUs do have instructions that operate differently on (say) signed and unsigned integers. For example, it might have separate instructions for:

* Signed vs unsigned multiplication.
* Sign extension vs zero extension, when loading (say) a byte into a register.
* Signed vs unsigned *trapping* addition/subtraction. Trapping arithmetic causes a trap/exception if the operation overflows or underflows. For integer addition and subtraction, if trapping is not desired, then there is no reason to distinguish between signed and unsigned arithmetic, which, as you probably know, is the main advantage of two's complement.

It's up to the programmer to decide which instruction to use on which memory location.

If you're not programming in assembly, this is handled by your language's type system, where instead of programming with memory locations and registers, you program with variables and types. Different languages have different variable semantics, but either way, the language implementation knows whether a variable is signed or unsigned, and issues the appropriate CPU instruction accordingly.

---
Tags: computer-architecture, binary
---


# Question
Title: Dynamic Data Structure for Sliding Window of varying size with Predecessor queries
I was wondering if anyone can point me to a data structure that supports the following operations. Goal is to create a data structure $D$ that stores 64-bit integers and provides the following operations:

* min() in $O(1)$ worst-case time
* max() in $O(1)$ worst-case time
* predecessor($x$) find the greatest element $y \in D$ such that $y \leq x $ in $O(\log \\|D\\|)$ worst-case time
* add($x$) in $O(1)$ worst-case time under the variant that $x \geq \max()$. When $x = \max()$, this can just be a no-op, so can effectively be ignored since max() can be done in $O(1)$ time. In other words, $D$ is essentially a set.
* splice($x$) remove from $D$ all of the elements $y$ such that $y \leq x$. This should take worst-case time proportional to the number of elements removed (i.e. amortized $O(1)$ per element removed).

I don't have explicit space constraints, but I would prefer a linear space data structure.

A doubly-linked list can provide all of these requirements except for the predecessor query in the desired time. On the other hand, tree structures can provide the predecessor query with the desired time, but don't take advantage of the fact that the data inserted is non-decreasing. So insertions and deletions fall short. A circular-array seems like a close bet, but my window does not have a fixed size, and insertions really should take $O(1)$ worst-case time.

Is this doable? If insertions were arbitrary, then this would clearly reduce to sorting... but in my case, the data inserted appears in sorted order.

I also noticed that a predecessor query can be reformulated in terms of a rank query followed by a select query, but I haven't been able to exploit existing dynamic rank-and-select data structures for this purpose.

# Answer
> 0 votes
One pragmatic approach is to use a dynamic array $A$. Store the integers in sorted order in this array. Augment this data structure with two additional indices: $i\_\min$ (the index of the smallest element in the set), and $i\_\max$ (the index of the largest element in the set, plus one).

Then, the predecessor operation can be implemented through binary search in $A\[i\_\min \dots i\_\max-1\]$. The min and max operations are trivial. The add operation involves potentially appending to the end of the array. Splice involves finding the index of $x$ in the array, then updating $i\_\min$ to point to that index.

This gets close to your desired running times. Min and max run in $O(1)$ worst-case time. Predecessor runs in $O(\log \\|D\\|)$ time, worst-case. Add takes $O(1)$ amortized time, assuming you use standard implementations of dynamic arrays. Splice can be implemented so its running time is linear in the number of elements deleted (if you use a linear scan starting from $i\_\min$); in fact, you can implement it in time logarithmic in the number of elements deleted (by using exponential search followed by binary search to find $x$). I suspect this might be good enough for practical purposes.

The exact running time will depend on what you assume about the API to the memory allocator and virtual memory subsystem and what you assume about their running time. For instance, do you assume that you can use sbrk and it runs in constant time? Also, basic memory operations like malloc() probably actually take logarithmic time (because of the need to manipulate page tables, which are a tree data structure with log-time access), even though in algorithm analysis we typically treat them as taking constant time. So it gets tricky, if you care about practical use of these data structures.

A pragmatic comment: once you get into data structures where you are comparing between constant time and logarithmic time, the memory hierarchy (L1 cache, L2 cache, etc.) starts to have a big impact and a logarithmic-time data structure that is memory hierarchy friendly can potentially perform better than a constant-time data structure that interacts poorly with the memory hierarchy. Given that you seem to care a lot about the difference between constant time and log-time, if this is a practical problem, you might be in a situation where it's worth expanding your scope to consider multiple data structures, even if some operations take log-time, and benchmark how efficient each one is on the types of workloads that arise for you in practice.

---
Tags: data-structures
---


# Question
Title: Asymptotics of $F(n) = n \times n^{\log_32}$
Is the complexity of $F(n) = n \cdot n^{\log\_3 2}$ allowed to be written as $O(n)$, or must you specify and say $O(n^{1.63})$, or even must you write $O(n^2)$ since it is an upper bound?

# Answer
> 1 votes
If $f(n)=O(n^\alpha)$ (your exponent, $\approx1.63$), then certainly $f(n)=O(n^2)$. But you may not conclude $f(n)=O(n)$. If you want to keep the available information, stick to $O(n^\alpha)$. The exponent needs not be integer.

# Answer
> 2 votes
It definitely isn't $O(n)$, it's rather $\Omega (n)$. $O(n^2)$, $O(n^{1+\log\_3{2}})$ (and not $O(n^{1.63})$, thanks to the comments) are both correct, with $O(n^{1 + \log\_32})$ being the tighter upper bound of the two, and the tightest upper bound in this particular example.

---
Tags: big-o-notation
---


# Question
Title: Estimate which components to replace, to not only save electric energy but also improve the computer's performance
Faster CPUs solve the same computational problems in shorter time frames. The same applies to faster GPUs.

Therefore, replacing with faster components can reduce the computer's power consumption.

On the other hand do some components need more electrical power for instance for ventilation.

How do you estimate which components to replace by which, find the bottlenecks, to not only save electric energy but also improve the computer's performance?

# Answer
> 2 votes
Replacing components in an existing computer with different ones is often hard to impossible.

CPUs usually don't have fixed performance at fixed use of electricity, but there is a curve where you change the voltage of the CPU, and it increases both performance (linear) and power usage (quadratic). The limits are at the low end where the CPU stops working, and at the high end where the CPU self destroys through heat. If you compare an M1 and M2 processor which are practically identical, M2 can produce better performance at higher power usage, slightly better performance at same power usage, same performance at lower power usage (improving battery life), and lower performance at much lower power usage. Chosen at runtime.

Big savers are turning brightness of the screen down, smaller screens, and replacing spinning hard drives with SSD drives (at much higher cost, and AFAIK higher energy cost to build the drives).

# Answer
> 1 votes
It's really hard. As a first approximation, my sense is that you basically can't, in any reliable, scientific way, in most cases. Modern computers are complex, and it's hard for an average consumer to predict exactly what the impact on performance or energy usage will be of any particular change to one component. In general, if you want to look at how you reduce memory consumption, you can start by looking at what laptops do; they are engineered to trade off performance for lower energy consumption.

Of course if cost is no object then you can just replace everything. But in practice cost is always a consideration, and it's hard to predict exactly how much benefit you'll get from any particular change.

Let me give you some ideas of some of the challenges. First, there are many factors that affect overall performance and memory consumption. Let me give you a simplified example. Suppose that:

* Task T runs entirely on the CPU and doesn't use memory much (e.g., cryptographic processing),
* Task U is entirely bottlenecked by random access to main memory, and
* Task V spends 33% of its time running entirely on the CPU, 34% of its time bottlenecked by memory, and 33% of its time bottlenecked by access to your hard disk.

Now suppose you are considering replacing your RAM with the newest, latest technology that is 2x faster and uses 2x less energy. What will the impact be on these tasks?

* Task T will experience no benefit;
* task U will be 2x faster and use 2x less energy;
* task V will about 1.2x faster and use 1.2x less energy.

See Amdahl's law and Gustafson's law.

In practice, most tasks look more like task V and depend on many factors, so replacing any one component is likely to yield only small benefits on most tasks, because those tasks rapidly become bottlenecked by the other components you haven't replaced. A few tasks will see a big benefit and some tasks will see no benefit. Moreover, because workload varies from person to person (you might run a different mix of applications than I do), experience from one person doesn't necessarily translate to others.

To predict the impact on performance or energy, you need to be able to measure all of the factors that affect a particular task's performance and how they affect it (this is usually hard), measure the effect on those factors of replacing a single component (this may be hard, or may be feasible using public benchmarks; it depends), measure the workload and mix of tasks (this is tedious at best), and then simulate all of those. This is beyond the capabilities of most consumers, and is very challenging even for those who are deeply experienced in the field.

If you look online, you'll find a lot of heuristic advice, opinions, and personal experiences. Some of them may be valuable. You may find statements that replacing a HDD with a SDD will really speed up boot times; if you have 8GB of RAM or less, memory is cheap and upgrading to 32GB might give you a big boost because some tasks might have been thrashing (e.g., a browser with lots of tabs open); that replacing your CPU with a mobile CPU or underclocking it can save a lot of energy; that buying the highest-end GPU you can afford will best improve performance of games, but will cost more in energy; and so on. You may also find advice that, if you're an average consumer, it's often best to (wait a few years and) upgrade your entire computer to a new computer, rather than replacing a single component, because a new computer will have new components that are better in every respect and in a balanced way, whereas replacing a single component may just leave you bottlenecked on the other components, reducing the benefit. Those are fine as far as they go, but they fall a bit short of a quantitative prediction of exactly how much performance and energy consumption will improve from a specific replacement on your particular computer.

---
Tags: optimization, power-consumption
---


# Question
Title: IS SUBSET-SUM in P if b(the sum) is given in unary and a1,...,an is in binary?
The SUBSET SUM decision problem consists of poitive integers a1,...,an; b.
We wish to know if for some subset S of the indices, $\sum\_{i \in S}a\_i = b$
I want to prove that if b is given in unary(and the ai's are gives in binary), that this decision problem is in P

# Answer
> 0 votes
Start by initializing a boolean array $T$ with indices from $0$ to $b$, inclusive. $T\_0$ starts as true (because you can always achieve a sum of 0) and the rest of the array starts as false.

For each value $a\_i$, we update the array by going though each value $x$ where $x+a\_i\leq b$, and setting $T\_{x+a\_i}$ to true only if $T\_x$ is true.

Essentially, at any point, the array describes which sums are possible using only the values of $a$ which have already been looked at. When a new $a\_i$ is looked it, any value that can be made by adding $a\_i$ to a currently possible sum becomes possible.

The final decision simply involves checking if $T\_b$ is true.

The bulk of the program involves iterating over all $n$ values of $a$ and all $b$ elements of the array, for a total runtime of $O(nb)$. The size of the input is at least $n+b$, because it describes each value of a $a$, and $b$ is written in unary.

Because $O(nb)$ is polynomial with respect to $n+b$, the described problem can be decided in polynomial time.

# Answer
> 0 votes
You have a problem with multiple numbers involved. You want an algorithm that is polynomial in one of the numbers, and the logarithm of the other numbers.

In this case, since the $a\_i$ are all positive, they must all be \<= b, otherwise there is no solution. So the values of all the numbers are severely restricted, and an obvious pseudo-polynomial algorithm turns out to be polynomial because b is written in unary.

If we allowed the $a\_i$ to be negative, then they wouldn’t be limited to the size of b. Actually if we allow just one negative $a\_1$ then we can subtract b from $a\_1$ and set b to 0, and change b to binary (since the sizes of 0 in unary and binary are both 1). Then add b to $a\_1$ and set b to its original value, in binary, and get an NP-complete problem.

---
Tags: complexity-theory, computability, np, decision-problem, polynomial-time
---


# Question
Title: Help with understanding a stipulation in pumping lemma
I have an example problem we are doing where we have xy. The special string I picked for the specific question was 0^p 1 1 0^p. My question is that when we "pump" Y, only part of y gets pumped so that the string results in 0^p+k 1 | 1 0^p. Why do we only pump the first half of Y if the whole special string is equal to Y? I tried to ask for help but the only explanation I got was because of the stipulation |xy| \<= p

# Answer
> 1 votes
If $p$ is the pumping length of your language $L$, the pumping lemma guarantees that $w = 0^p 1 1 0^p$ can be decomposed as $xyz$ with $|xy| \le p$, $|y| \ge 1$, and $xy^iz \in L$ for all integers $i \ge 0$.

Since $|xy| \le p$ and the first $p$ symbols of $w$ are $0$s, it must be that both $x$ and $y$ contain only $0$s. Therefore any decomposition of $w$ must be of the form $x=0^h$, $y=0^k$, $z = 0^{p-h-k} 1 1 0^p$, for some choice of $k$ and $h$ that satisfies $k + h \le p$ and $k \ge 1$.

From what you write it seems that you choose to repeat $y$ once, which corresponds to picking $i=2$. The resulting word is: $$x y^2 z = \underbrace{0^h}\_x \\; \underbrace{0^{2k}}\_{y^2} \\;\underbrace{0^{p-h-k} 1 1 0^p}\_z = 0^{p+k} 1 1 0^p.$$

# Answer
> 0 votes
Go back to how the pumping lemma is created: If L is regular then there is a state machine recognising L with p states. If you process the first n characters of a string, you must visit at least one state twice. If you moved from state X to state X while processing k \>= 1 characters, then leaving these characters out, or duplicating them, or repeating them a billion times would all go to the same state X. And if you started by processing a string in L, then processing the missing characters will end in an accepting state.

And if you write that down formally you have the pumping lemma.

---
Tags: automata, pumping-lemma
---


# Question
Title: Is it possible to decode an array stored in strings with constraint satisfaction?
I am currently experimenting on compression algorithms, I am using proven algorithms and I am just trying to see if I can make some things more efficient, so I am very sorry if this is a stupid question. I am trying to decode an array from a string for example I have `[123, 4, 12, 7, 51]` so if I turn this into a string it would be "123412751" are there ways to decode this without bloating the array? like you can keep the length of this by doing something like `31231421217251` so you'd know how to decode this but the problem is you'd bloat the data needed so instead I would like to know if this is solvable with constraint satisfaction and how would I go about that?

What I did with constraint satisfaction is I'd get the sum of `[123, 4, 12, 7, 51]` which is 197 and the length needed which is 5 so now I'd look for combinations from "123412751" with a length of 5 and a sum of 197 however with larger arrays it gives me different values not really the exact one I needed, is this something that is possible?

# Answer
> 1 votes
I’d look first at Huffman coding and arithmetic coding, which will handle th commas and spaces quite efficiently. Or Lempel-Ziv which munches these separators away at practically no cost.

Or encode the integers as UTF-8, extended to 5 or 6 byte codes in case you have some huge integers.

---
Tags: algorithms, data-structures, data-compression
---


# Question
Title: Time complexity analysis for Searching in a Hash table
I want to analyse the time complexity for Unsuccesful search using probabilistic method in a Hash table where collisions are resolved by chaining through a doubly linked list. And the doubly linked list is kept in sorted order (Ascending).

I proceeded in the following way: We will stop if the element in the linked list is greater than the element to be searched, otherwise continue the search. I can understand that this will be better than the normal Unsuccesful search in Hashing i.e. $O(\alpha + 1)$. But how do I do exact analysis of average case time complexity in this case using Expectations in Probability.

Edit: The Keys are randomly distributed from 1 to n and the number of slots in Hash table are m.

# Answer
> 0 votes
Let $\alpha = \frac{n}{m}\ $ where $n$ = total no. of elements in hashtable ,$m$ = number of slots in hashtable, be the *load factor* or *Average number of elements in a chain*.

Given that each chain is sorted, an unsuccessful attempt at search would require $1$ comparison in the best case and $\alpha$ comparisons in the worst case. The expected no. of comparisons for the same is

$\frac{1}{\alpha }(1+2+3+....+\alpha) = \frac{\alpha (\alpha +1)}{2\alpha } = \frac{\alpha +1}{2}$

yielding an average case complexity of $O(\frac{\alpha +1}{2}+1)$.

P.S. If your chains are sorted then you can lower the complexity to $O(\log\_{2}\alpha+1)$ by using binary search(depending on your implementation of linked list)

---
Tags: algorithms, time-complexity, data-structures, probabilistic-algorithms, hashing
---


# Question
Title: All the keys in a binary search tree should be greater than or equal to the root of the tree, is my understanding correct?
A post claims 5 of the trees shown in the following figure are all binary search trees

I guess the author's making a mistake, since the 2 trees on the right ARE NOT binary search trees.

As an example, in the last tree pointed out by red rectangle, the key `1` is in `2`'s right subtree, which doesn't satisfy the binary-search-tree property.

Besides the figure above, the post also says

> the BST is an ordered data structure that allows no duplicate values

which, I guess, is another mistake.

Correcting the bugs above, I'd like to make the following conclusion,

**all the keys in a binary search tree should be greater than or equal to the root of the tree**,

or more precisely, **in a binary search tree, all the keys of a subtree should be greater than or equal to the root of the subtree**,

is my understanding correct?

one of my references:

https://en.wikipedia.org/wiki/Binary\_search\_tree

# Answer
You are right that both trees on the right are not binary trees but you are wrong that all keys of a subtree are greater than the key at the root. It is true only for the **right** subtree. The keys of the **left** subtree are all lesser than the keys of the root. That is the very definition of a BST.

Concerning duplicated values, depending on whether you want to use your BST for representing sets or multisets, you can allow them or not, that will not change much the complexity of the underlying operations. In the textbook *Introduction to Algorithms* by Cormen, Leiserson, Rivest and Stein, duplicated values are allowed (see definition in Chapter 12).
> 3 votes

---
Tags: trees
---


# Question
Title: Average runtime random search without replacement
Consider an algorithm that is tasked with searching the array A. Let *n* be the size of the array, let *i* be a random number between 1 and *n*. Finally, *k* is the target object we are searching for. If A\[*i*\] = k, we have a match. If A\[*i*\] != k, we pick a new random *i*. The algorithm terminates when we have established a match or we have checked all the elements in the array (k does not exist in A).

I am trying to figure out the Average Runtime of this, but am at a loss.

# Answer
> 1 votes
**Hint:**

If the key is present, the probability to find it at the first attempt is $p\_1=\dfrac1n$. Then the probability to find it at the second attempt is $p\_2=\dfrac{1-p\_1}{n-1}$ (because the first attempt must have failed and there are $n-1$ equiprobable choices left). The probability to find it at the third attempt is $p\_3=\dfrac{1-p\_1-p\_2}{n-2}$. And so on.

After having computed all probabilities, obtain the expectation. *Note that there is a nice simplification.*

If the key is not present, the expectation is $n$. Finally, combine the two expectations.

# Answer
> 0 votes
My answer is similar to @Yves Daoust, But I want to calculate the expected runtime easily.

**If key is present:**

Let $T$ be the runtime, what we want to calculate is $E\[T\]$.

**when $1\leq T \leq n $:**

$Pr(T\geq i)=\dfrac{n-1}{n}\dfrac{n-2}{n-1}...\dfrac{n-i+1}{n-i}=\dfrac{n-i+1}{n}$.

**when $ T \geq n $:**

$Pr(T\> i)=0$

Because $T$ is **non-negative integer:**

$E\[T\]=\sum\_{i \in N^+}Pr(T \geq i)=\dfrac{\sum\_{i}i}{n}=\dfrac{n-1}{2}$

**If key is not present:**

The algorithm has to select $n$ times.

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: How to check if an positive integer can be represented as a sum of integers
How to determine if an integer x \> 0 can be represented as 20n + 50m + 100k, where n,m,k \>= 0 and are integers.

# Answer
> 1 votes
The linear combinations of $20$ and $50$ with non-negative coefficients are

$$0,20,40,50,60,70,80,90,100,110,\cdots$$

Hence all $x$ multiples of $10$ will work, except $10$ and $30$.

# Answer
> 0 votes
The greatest common divisor of 20, 50 and 100 is gcd(20, 50, 100) = 10. All multiples of 10 can be found as the sum of (positive or negative) multiples of 20, 50, or 100, and no other integers can. However, some numbers might require negative multiples, for example 10 = 1 * 50 - 2 * 20.

If x and x+10 are a sum with positive integers, then so are x + k\*10 for all k ≥ 0, because you add x + (k/2) * 20 if k is even, and (x + 10) + ((k-1) / 2) * 20 if k is odd.

You find easily that 10 and 30 are not sums with positive integers, but 20, 40 and 50 are, and we saw that with 40 and 50 all other numbers created by adding a multiple of 10. The solution is

```
{ k * 10: k ≥ 2 and k ≠ 3 }.

```

In general, you would calculate the gcd g of the numbers (in this case gcd (20, 50, 100) = 10). You state that only integers of the form k * g (in this case k * 10) can be solutions, then divide everything by g.

Now the problem is for example "Which integers k \> 0 are the sum of 2a + 5b + 10c, a, b, c ≥ 0", and since these numbers have a gcd of 1, there is always a solution in (possible negative) integers. Let m be the smallest of these numbers, in this case m = 2. If we find integers k to k + m - 1 with non-negative coefficients, then we can increase a by 1, 2, 3 etc. to find solutions for all the larger k. So we try to find solutions for k = 1, 2, 3 etc. until we find m consecutive k with solutions, and then we know all solutions.

---
Tags: algorithms, integers
---


# Question
Title: The modularity difference in Louvain algorithm for community detection in graphs
---

*I am interested in the formula of modularity difference between two partitions considered in the Louvain algorithm for community detection in graphs. I give a formal expression of this question below.*

---

Consider an undirected graph $G$ with vertex set $V$. If $G$ is weighted, $\omega(u,v)$ denotes the weight of the edge between $u$ and $v$ if it exists, otherwise it is $0$. If $G$ is unweighted, then it is seen as a weighted graph with each edge weight equal to $1$.

Let us denote by $m$ the half of $2m = \sum\_{u\in V}\sum\_{v\in V} \omega(u,v)$; it is the number of edges in $G$ if it is unweighted.

A partition $P$ of $V$ is a set of $k$ sets $P = \\{C\_1, C\_2, \dots, C\_k\\}$ with $\cup\_i C\_i = V$ and $C\_i \cap C\_j = \emptyset$ if $i\neq j$.

The modularity of partition $P$ is: $$ Q(P) = \sum\_{C\in P} Q(C) = \sum\_{C\in P} \frac{e\_C}{2m} - \left(\frac{a\_C}{2m}\right)^2 $$ where $ e\_C = \sum\_{u\in C}\sum\_{v\in C} \omega(u,v) $ and $a\_C = \sum\_{u\in C}\sum\_{v\in V} \omega(u,v)$.

Modularity is widely used in the context of community detection in graphs, where one seeks partitions with high modularity. Then, $C\_1$, $C\_2$, $\dots$, $C\_k$ are called *communities*.

The Louvain algorithm is one of the main community detection methods. It relies on the fact that one may easily compute the modularity difference between two partitions if one of them is obtained from the other by moving only one vertex from a community to another one.

Partial expressions of this modularity difference are available in the literature, including the original Louvain paper (with a typo) and in the wikipedia page on Louvain method, but I cannot find a full expression and its derivation in any published paper. All I could find is a Quora discussion on the topic, that I find quite obscure, sorry.

Finding this expression is not very challenging, but not completely trivial either, it seems, since there are many incomplete and/or flawed versions online. Given its great importance in network science, I guess I missed something.

**Question: where may I find a full, clear and correct derivation of the modularity difference between two such partitions?**

There are many implementations of Louvain method, and their source code certainly contains the correct formula; but it is quite technical to get it from code, and I am interested in the detailed derivation too.

# Answer
> 0 votes
There is a derivation of the modularity difference in this book chapter: Multilevel Local Optimization of Modularity by Thomas Aynaud, Vincent D. Blondel, Jean-Loup Guillaume, and Renaud Lambiotte. It is also available in French.

I provide my own version below, with the notations introduced in the question.

Let us consider a node $u$ in a community $i$ of $P$, and let us consider the partition $P'$ obtained by moving $u$ from community $i$ to another community $j$ of $P$: for all $k\neq i$ and $k\ne j$ in $P$, $k$ is in $P'$; in addition, $P'$ contains $i'=i\setminus\\{i\\}$ and $j'=j\cup\\{u\\}$, and nothing else.

We then have $e\_{i'} = e\_i - 2 d(u,i)$ and $e\_{j'} = e\_j + 2 d(u,j)$. Also, $a\_{i'} = a\_i - d(u)$ and $a\_{j'} = a\_j + d(u)$.

Therefore: $$ Q(i') = \frac{e\_i-2\cdot d(u,i)}{2m}-\left(\frac{a\_i-d(u)}{2m}\right)^2 $$ $$ = \frac{e\_i}{2m}-\frac{d(u,i)}{m}- \left(\frac{a\_i}{2m}\right)^2 - \left(\frac{d(u)}{2m}\right)^2 + \frac{a\_i\cdot d(u)}{2\cdot m^2} $$ and, similarly: $$ Q(j') = \frac{e\_j+2\cdot d(u,j)}{2m}-\left(\frac{a\_j+d(u)}{2m}\right)^2 $$ $$ = \frac{e\_j}{2m} + \frac{d(u,j)}{m} - \left(\frac{a\_j}{2m}\right)^2 - \left(\frac{d(u)}{2m}\right)^2 - \frac{a\_j\cdot d\_u}{2\cdot m^2} $$

We finally obtain: $$ Q(P') - Q(P) = Q(i')-Q(i) + Q(j')-Q(j) $$ $$ = \left( -\frac{d(u,i)}{m} - \left(\frac{d(u)}{2m}\right)^2 + \frac{a\_i\cdot d(u)}{2\cdot m^2} \right) \+ \left( \frac{d(u,j)}{m} - \left(\frac{d(u)}{2m}\right)^2 - \frac{a\_j\cdot d\_u}{2\cdot m^2} \right) $$ $$ = \frac{d(u,j)-d(u,i) + d(u)\cdot\frac{a\_i-a\_j-d(u)}{2m}}{m} $$

---
Tags: algorithms, graphs, partitions, network-analysis, social-networks
---


# Question
Title: Find a key in a BBST for which sum of values of keys smaller then it - is maximal
I'm required to describe an implementation of a data structure that holds key,value pairs, which can be **signed integers**.

We need to be able to init() in O(1), insert(x) in O(logn), delete(x) in O(logn) and sumPrevious(x), which returns sum of **values** of the keys that are smaller than key 'x', in O(logn). An AVL rank tree, which rank is sum of values in sub-tree, should do the trick. So far so good.

Now I need to also implement maxSumPrevious(), which returns the key 'k' for which 'sumPrevious(k)' is maximal, in O(1). This is where I got stuck. Since inserting or deleting an element changes the 'sumPrevious' of ALL the elements bigger than it. I tried going in the direction of a different rank that updates in insertion/deletion, but it lead to nowhere.

Thank you in advance

# Answer
> 2 votes
You just need to add some additional data in each node, namely:

* the maximum sum of values of previous nodes **in the subtree**;
* the key **in the subtree** that reach this maximum sum.

It is clear that with this data, you can get `maxSumPrevious()` in $\mathcal{O}(1)$ time, but you would need to update the insertion and deletion of a node.

I will try to give details for insertion, deletion is done in similar ways. Suppose then that you want to insert $(k, v)$ in a tree $T$:

* if $T$ is empty, create a single node `x` such that `x.MSPV = 0` (MSPV stands for "max sum previous values") and `x.keyMSPV = k`;
* otherwise, make an usual insertion in BBST, and for each modified node `x` (by insertion in one child of `x` or after a rotation):
    + `x.MSPV` is the largest among the following:
        - `x.left.MSPV` if the corresponding key is in the left child;
        - `x.left.sumValues` if the corresponding key is in the root `x`;
        - `x.left.sumValues + v + x.right.MSPV` if the corresponding key is in the right child.
    + `x.keyMSPV` can be updated depending on the key that defines `x.MSPV`.

Those additional operations are done in $\mathcal{O}(1)$ time for each node, so the total complexity stays $\mathcal{O}(\log n)$.

---
Tags: avl-trees, rank
---


# Question
Title: What is the connection between the Mersenne-Twister and Linear Congruential Generator?
This video claims that the Mersenne-Twister is based on the Linear Congruential Generator. The math in the Mersenne-Twister original paper is a bit too much for me. I have not seen that claim explicitly made in the wikipedia article for Mersenne-Twister or in some of the other sources I consulted. Is the Mersenne-Twister based on the Linear Congruential Generator? High level, how so?

# Answer
No it is not.

MT is based on a twisted generalized feedback shift register. It is defined on vector spaces over finite fields, specifically $GF(2)$.

The LCG is based on integer arithmetic over the integers modulo $n,$ say $\mathbb{Z}\_n.$

The two algebraic structures are quite different so this statement is false.
> 2 votes

---
Tags: pseudo-random-generators
---


# Question
Title: swapping numbers in a list is equivalent to remove & reinsert?
Given some ordered list of $n$ items, I obviously have $n!$ possible arrangements. However, as a heuristic in some larger algorithm that needs to find the optimal order, I want to do some quick local exploration. One option is to walk through all possible removal & insert operations at $O(n(n-1))$. A similar option is to run through all possible 2-swaps (e.g 2-opts), also at a cost of $O(n(n-1))$. The question: do those two heuristic approaches cover the same solution set? Are they equivalent?

# Answer
No, simply because $\[1,2,3\]$ can be transformed to $\[3,1,2\]$ using one insertion but not using one swap. Just check all possible swaps to prove this.
> 2 votes

---
Tags: optimization, combinatorics, local-search
---


# Question
Title: Does exist a tree where the inequality with MST edges are strict?
We know that if $T\_1 = \\{e\_1, \dots, e\_n\\}$ and $T\_2=\\{f\_1, \dots, f\_n\\}$ are MST then if we order the edges such as $$w(e\_1) \le w(e\_2) \le \dots \le w(e\_n)$$ $$w(f\_1) \le w(f\_2) \le \dots \le w(f\_n)$$

then $w(e\_i)=w(f\_i)$ for all $i\in \[n\]$

This also (trivially) implies that $w(e\_1) \le w(f\_i)$ for all $i\in \[n\]$

Does this equality also holds when $T\_2$ is a spanning tree but not minimal? I have been trying to prove it for a while and are not succeeding.

Assume that it is not and let $k$ be the first index where $w(f\_i) \< w(e\_i)$ and denote $f=(u,v)$. Let us look at the unique path connecting $f=(u,v)$ in $T\_1$ if that path contains any of the $\\{e\_{k}, \dots, e\_n\\}$ edges then we can replace that edge with $f\_i$ and we get that $T\_1$ is not a MST, otherwise that path contains at-least one of the edges $\\{e\_1, \dots, e\_k\\}$.

There is where I am stuck, I am trying to say that $\\{f\_1, \dots, f\_{k}\\}$ must contain an edge that is safe to add to $T\_1$, my idea is that one of the edges in $\\{f\_1, \dots, f\_{k}\\}$ must close a loop in the edges $e\_{k}, \dots, e\_n$ and therefore it is safe to replace it but I can't get it to work.

Appreciate any help.

This also proves that MSTs are invariant under increasing functions (that is, if $f(x)$ is an increasing function that an MST w.r.t $w(E)$ would remain an MST w.r.t $f(w(E))$.

# Answer
> 1 votes
The property you speak of is indeed true.

Denote $E = \\{e\_1, e\_2, …, e\_{k-1}\\}$ and $F = \\{f\_1, f\_2, …, f\_k\\}$.

I will prove that there exists $f\in F\setminus E$ such that $(V, E\cup\\{f\\})$ is acyclic. That would mean that $w(e\_k) \leqslant w(f) \leqslant w(f\_k)$.

Suppose that $(V, E\cup\\{f\\})$ contains a cycle for each $f\in F$.

Denote $C\_1, …, C\_m$ the connected components of $(V, E)$. Since $(V, E\cup \\{f\\})$ contains a cycle for all $f\in F$, that means that each $f$ is an edge between two vertices of a certain $C\_i$. If we define $E\_i = \\{e\in E\mid e \text{ is an edge between two vertices of }C\_i\\}$ and $F\_i = \\{f\in F\mid f \text{ is an edge between two vertices of }C\_i\\}$, the pigeonhole principle says that there exists $i\in \\{1, …, m\\}$ such that $|F\_i| \> |E\_i|$. But since $(C\_i, E\_i)$ is a tree, that means that $|E\_i| = |C\_i| - 1$. That implies that $(C\_i, F\_i)$ contains a cycle, and that $T\_2$ contains a cycle.

We conclude by contradiction that $w(e\_k) \leqslant w(f\_k)$.

---
Tags: graphs, combinatorics, minimum-spanning-tree
---


# Question
Title: Context free language with valid Pumping Lemma use
Is this language context free?

$L = \\{a^kb^lb^ka^l \ | \ k,l \in \mathbb{N}\\}$

Using Pumping Lemma and $z = a^nb^nb^na^n$ I find it contradicting PL.

If $z = uvwxy$ and $|vwx| \leq n$, follows:

1. $vwx$ is in either $a^n$ or $b^n$, second $b^n$, or second $a^n$. After pumping form of the word changes and thus pumped word not anymore in the language. Done
2. $vwx$ lies between $a^nb^n$ or $b^nb^n$ or $b^na^n$. When we pump down, we get $a^pb^qb^na^n$ or $a^nb^pb^qa^n$ or $a^nb^nb^pa^q$ with $p,q \leq n$. Which shows that pumped word not in the language.

Where is the error? The language should be context free. Why PL shows that language is not context free?

# Answer
> 2 votes
The language is indeed context-free. Since it can be defined as $L = \\{a^kb^kb^la^l\mid k,l\geqslant 0\\}$, the following grammar can generate it:

> $S \rightarrow XY$
>
> $X\rightarrow AXB\mid \varepsilon$
>
> $Y\rightarrow BYA\mid \varepsilon$

In your tentative of proof, the second case is wrongly considered. You could have $vwx \in a^\*b^\*$ without any problem. For example, if $u=a^{n-1}$, $v =a$, $w=\varepsilon$, $x=b$ and $y = b^{2n-1}a^n$, then for any $k\geqslant 0$, $uv^kwx^ky = a^{n-1 +k}b^{2n-1+k}a^{n}\in L$.

---
Tags: context-free, pumping-lemma
---


# Question
Title: How do you specify Big-Theta of an algorithm when the Big-O and Big-Omega are different?
I understand that if `f(n) ∈ O(g(n))` and `f(n) ∈ Ω(g(n))`, we can conclude that `f(n) ∈ Θ(g(n))`.

But what if we have an algorithm where the Big-O and Big-Ω are different? For example `f(n) ∈ O(n^2)` and `f(n) ∈ Ω(n)`. Then what would be its Big-Theta notation?

To me, it seems that both `f(n) ∈ Θ(n^2)` and `f(n) ∈ Θ(n)` would be technically correct claims. I suspect I might have misunderstood something and I would appreciate if anyone could clarify this.

# Answer
There are two possibilities:

* either the Big-$\Theta$ lies somewhere between the Big-$O$ and Big-$\Omega$ but we can't tell from the given;
* or there is no Big-$\Theta$ expression at all (but we can't tell from the given).

E.g.

$T\_n=O(n^2), T\_n=\Omega(n)$ and $T\_n=\Theta(n^2)$ are all true,

where $T\_n$ denotes the $n^{\text{th}}$ triangular number, and

$n^2\cos^2(n)+n\sin^2(n)=O(n^2),n^2\cos^2(n)+n\sin^2(n)=\Omega(n)$, but there is no $\Theta$.
> 1 votes

---
Tags: algorithms, complexity-theory
---


# Question
Title: Why executables aren't written in a way that the OS understand instead of machine code?
We know that computer programs are either AOT compiled, JIT compiled or interpreted

And we also know that AOT compiled programs usually get compiled from its high level source code into machine code

Now the question is, if machine code is so hard to understand and write, why the idea of compilers wasn't to translate programs into a simpler language understood by the operating system instead of translating directly into machine code

And if such operating-system-dependent language existed, the OS should read the executables written in it and translate them into the corresponding machine code understood by the CPU

In other words, wouldn't the process of compiling into machine code have been easier if OSs had some kind of JIT compiler (VM?) that translated a specific kind of bytecode (which should exist) into machine code?

Are there any disadvantages of all this?

# Answer
OS-independent layers (more precisely CPU-independent) introduce some overhead to achieve the exact specifications, so in many contexts this is just unacceptable. And computer manufacturers have no interest in making their solution too standardized, as this impairs customer retention.

Anyway, you can consider that the Java Virtual Machine is an extension of the OS that just does what you want.
> 3 votes

# Answer
The OS doesn't execute programs. The CPU does. The OS helps manage access to resources. Since the CPU executes programs, programs need to be translated (compiled) into a form that the CPU can execute.

I see no obvious benefit or advantage to the scheme you describe (compile the program to an intermediate language, and then OS does JIT compilation). You could certainly do it, but the lack of a clear benefit probably explains why it is not common.

However, you might be interested in Android apps, which used to use a Dalvik interpreter and/or just-in-time compiler to run Android apps. Android apps are often written in Java, which was compiled to the Dalvik intermediate language, and then at runtime the system interpreted this or applied a JiT compiler.
> 1 votes

---
Tags: compilers
---


# Question
Title: Computer Algebra: Algorithms for solving equations symbolically
As a hobby, I have written a basic computer algebra system. My CAS handles expressions as trees. I have advanced it to the point where it can simplify expressions symbolically (i.e., sin(pi/2) returns 1), and all expressions can be reduced to a canonical form. The CAS can also differentiate expressions.

Using this paradigm, what kinds of algorithms are there for solving equations? An equation in my model would be represented as an (=) tree with two subtrees that are the left and right expressions. I know there is no "magic bullet" for solving all equations, but are there algorithms out there that are designed to symbolically solve an equation? If there aren't, what would be the general approach? What kind of classes can equations be split into (so that I might be able to implement an algorithm for each kind)? I don't want to use naive methods and then paint myself into a metaphorical corner.

# Answer
> 2 votes
I am no specialist, but IMO this problem is even harder than symbolic integration, and I have not heard of a general theorem that would parallel that of Liouville. (https://en.wikipedia.org/wiki/Liouville%27s\_theorem\_(differential\_algebra))

Of course, the case of univariate polynomials was settled by Galois, but only the degrees up to four are "easy" to handle.

Now many equations can be turned to polynomials by clever substitutions, but I have no idea of a general method to achieve that. (E.g. `9^x+3^x=5` can be reduced to quadratic. `9^x+4^x=5` can not.)

For transcendental equations that cannot be reduced to polynomial form, you are completely helpless. Needless to say, the case of systems of equations is even harder.

Now some CAS switch to numerical resolution when they cannot find a symbolic solution. But even this is challenging because though we have excellent root finders, little is said about root separation, i.e. methods that can guarantee that you have found all the roots.

# Answer
> 1 votes
The are some open source JAVA libraies with complete documentation for math/CAS like:

Jasymca, Java Algebra System and many more.

I think a good way is start with them and try to contribute more!

# Answer
> 0 votes
Very long time ago I attempted to do symbolic differentiations. While my code sufficed to help me solve a particular problem, I got thereby the conviction that implementing a good efficient computer algebra system must be at least as hard as writing a good compiler for a programming language. (Think e.g. of doing integrations.)

I have no knowledge to answer your listed concrete questions, like on the other hand to point out that "solving equations" seems to be a too broad issue for getting answers for your questions, there being all sorts of equations (linear, non-linear, differential, integral, etc. etc.) that are to be handled differently.

As to literature references, I suggest that you at least take a look of the following books before proceeding further with your project:

K. O. Geddes et al., Algorithms for Computer Algebra.

J. Gathen and J. Gerhard, Modern Computer Algebra.

# Answer
> 0 votes
I'm sure you'll find some references by taking a look at how Giac works. It is quite extensive so I couldn't do it myself now. Here you will many useful links. I think you might find something related to your question in the 1109 pages of documentation.

---
Tags: reference-request, computer-algebra
---


# Question
Title: What is "potential speedup" in parallel computing?
There is an example problem from p506 of *Computer Organization and Design, Fifth Edition: The Hardware/Software interface by David A. Patterson, John L. Hennessy*

I wonder how "potential speedup" is defined? The book doesn't give its definition.

In the example, since speedup with $10$ processors is $55\\%$ of the potential speedup, the potential speedup should be $ 5.5 / 55\\% = 10$. it is equal to the number of processors.

Since the execution time before improvement has a part $(10t)$ unaffectable by parallel computing on multiple processors, according to Amdahl's law (outlined in blue box), the potential speedup must be smaller than the number of processors.

So I am puzzled.

Google books has an earlier (4th) edition which has a similar example too.

# Answer
*Potential speedup* $\equiv$ *number of processors*. I agree that it is poorly chosen wording. A better term would be *efficiency* (the average amount of time that the processors are doing useful work.)
> 2 votes

# Answer
> Since the execution time before improvement has a part (10t)(10t) unaffectable by parallel computing on multiple processors, according to Amdahl's law (outlined in blue box), the potential speedup must be smaller than the number of processors.

The potential speedup in the article means a number of processors, already answered. It means a speedup limit for a given PC for the case when the algorithm could be cut in parallel pieces unlimited.

For example, an algorithm has N independent parts for N processors. It never occurs in real life, but a theoretically example is - find N random numbers. Here our speedup is N, but the article's algorithm hasn't this property.

The Amdahl's law doesn't interfere directly with the potential speed term. It, in other words, states that when the task split, the summary execution time can't be less than the largest fragment. So, Amdahl's law uses only sequential computation time for program fragments as the statement objects, not a "potential speedup."
> 1 votes

# Answer
Potential Speed up is how much we could have make it faster. with 10 processor and total task size 110t (10t sequential and 110t parallelizable) By Ahmdal's law

$$ Speedup\_{curr} = \frac{T\_{old}}{T\_{new}} $$

And when would be the speedup be maximum. When every part is parallelizable. Then,

$$ T\_{new} = \frac{T\_{old}}{n} $$

$$ Speedup\_{max} = \frac{T\_{old}}{T\_{new}} \\ = n $$

Thus potential speed up is

$$ Potential\\: Speedup = \frac{Speedup\_{curr}}{Speedup\_{max}} \\ = \frac{Speedup\_{curr}}{n} $$
> 0 votes

# Answer
With $p$ processors, you expect the solution to be obtained $p$ times faster, and this is of course the best you could hope.

This is indeed the *potential* speedup, and in practice it is never reached, due to overhead of parallelism and unavoidable parts of the algorithm that cannot be parallelized at all.

Things start going bad when the speedup stays below $1$. :-)
> 0 votes

---
Tags: terminology, algorithm-analysis, runtime-analysis, parallel-computing
---


# Question
Title: Can equations be simplified with the help of a given set of equations?
There are many posts here and elsewhere asking for algorithms to simplify simple arithmetic expressions. For example, this question asks how to simplify the expression $axc + byc + ayc + bxc$. Symbolics and xcas are two examples among many of Computer Algebra Systems (CAS) that can do this. But Symbolics and xcas perform differently: Symbolics can simplify the expression above and turn it into $cx(a + b) + cy(a + b)$, whereas xcas completely factorizes the expression into $(a + b)c(x + y)$.

I was wondering if there is any CAS that simplifies expressions based on some set of equations that you can input into the system? As an example, assume that we knew $a + b = 2$ and $x + y = -1$: is there any known (implemented) algorithm that given said equations, would factorize the expression above into simply $-2c$ ? Perhaps it's more pertinent to ask: could such an algorithm exist?

In the example above, we can set $y = -1 - x$ and $b = 2 - a$ (as pointed out in a comment), but in more complicated examples it might not be possible.

# Answer
If your knowledge is in the form of linear equations, as in your example, then you can make a simple substitution. In your example, set $b=2-a$ and $y=-1-x$, as Yves Daoust suggests. This will work for any system of linear equations.

If the expression is a polynomial and the "knowledge" is expressed as equations of polynomials, then it is possible that Groebner bases might be useful - I am not sure.
> 1 votes

---
Tags: reference-request, computer-algebra
---


# Question
Title: How can I convert the pseudo-code that solves maximum subarray problem to Python code?
I'm reading *Algorithm Design and Application*, by Michael T. Goodrich and Robert Tamassia, and sometimes the pseudo-code in this book doesn't make sense at all.

At chapter one they show us 3 solutions for the famous maximum subarray problem. I understood completely the first and second solutions, but the third one (the fastest) seems impossible to understand.

The pseudo-code for this solution is this:

```
Algorithm MaxsubFastest(A):
    Input: An n-element array A of numbers, indexed from 1 to n.
    Output: The maximum subarray sum of array A.

   M₀ ← 0    // the initial preﬁx maximum
   for t ← 1 to n do
      Mₜ ← max{0, Mₜ₋₁ + A[t]}

   m ← 0    // the maximum found so far
   for t ← 1 to n do
      m ← max{m, Mₜ }

   return m

```

What I don't get about this pseudo-code is this:

1. M₀ is a variable that receives zero at the beginning, right? But it is never called again... so what is happening here?
2. How the `Mₜ ← max{0, Mₜ₋₁ + A[t]}` part works at all? Is it creating a lot of Mₜ variables, one for every t value?
3. The "max" part is something like a function? If that is so, doesn't it interfere with our algorithm Big-Oh notation?
4. There are two loops that seems to "talk" to each other, otherwise they run separately.

I think that a good way to end my questioning is to see this code in a programming language I know (Javascript or Python, preferably). So, my question: how can I implement this pseudo-code in Python?

# Answer
> How the $M\_t ← \max\\{0, M\_{t-1} + A\[t\]\\}$ part works at all? Is it creating a lot of $M\_t$ variables, one for every t value?

Yes, it is creating variable $M\_t$ for every $t$. Together with $M\_0$, there are $n+1$ of them.

When $t=1$, the statement is $M\_1 ← \max\\{0, M\_0 + A\[1\]\\}$. Note that $M\_0$ is used.

> The "max" part is something like a function? If that is so, doesn't it interfere with our algorithm Big-Oh notation?

Yes, $\max$ is a function of two numbers that returns the bigger one between the two numbers or anyone of them if they are equal.

It is assumed that it takes up to to some constant time to call that function. A constant factor does not affect the big-$O$ notation.

> There are two loops that seems to "talk" to each other, otherwise they run separately.

Yes. The first loop creates/computes a list of $M\_t$. The second loop finds the maximum of them.

---

Here is corresponding code in Python. Note that the code uses $A\[t-1\]$ instead of $A\[t\]$ in the pseudocode since the index starts from $0$ in Python instead of $1$ in the pseudocode.

```
def MaxsubFastest(A):
    """Return the maximum sum of a subarray of A """
    n = len(A)
    M = [-1] * (n + 1)  # -1 stands for not set.
    M[0] = 0
    for t in range(1, n + 1):
        M[t] = max(0, M[t - 1] + A[t - 1])
    m = 0
    for t in range(1, n + 1):
        m = max(m, M[t])
    return m

```

---

As you might have suspected, we can reduce the usage of $n+1$ $M\_t$'s to only only variable $b$, which will be the bigger one between 0 and the maximum sum of a subarray that ends at current index of $A$. To enable that, we will merge two loops into one, keeping $m$ as the maximum sum of a subarray that have considered so far.

```
def MaxsubFastestWithLeastSpace(A):
    """Return the maximum sum of a subarray of A """
    c = 0
    m = 0
    for t in range(1, len(A) + 1):
        # c is the maximum sum of a subarray that ends at index t-1
        # if that sum is greater than 0; otherwise c is 0.
        c = max(0, c + A[t - 1])
        # the maximum sum of a subarray that ends before index t
        m = max(m, c)
    return m

```
> 0 votes

---
Tags: algorithms, python, pseudocode, maximum-subarray
---


# Question
Title: Infinite loops and the computability of mapping reductions
Consider the reduction $A\_{TM} \le\_m \overline{E}\_{TM}$, where

$$A\_{TM} = \\{\langle M, w \rangle \mid \text{TM $M$ accepts $w$}\\}\text{, and}$$

$$\overline{E}\_{TM} = \\{\langle M \rangle \mid \text{TM $M$ accepts some string}\\}$$

Then define the mapping reduction, $f(\langle M, w \rangle)$ as follows:

Construct a new TM $M^\prime$ that on input $x$

* **rejects** if $x \ne w$;
* otherwise, runs $M(w)$ and **accepts** if it accepts.

Finally, it outputs $\langle M^\prime \rangle$. This construction ensures that $\langle M, w \rangle \in A\_{TM} \Leftrightarrow \langle M^\prime \rangle \in \overline{E}\_{TM}$.

**Question.** The idea makes sense, except that I am having a hard time wrapping my head around infinite loops and the computability of mapping reductions. In particular, what ensures that we can indeed write $\langle M^\prime \rangle$ even if $M$ does not halt on $w$? It seems like the answer should be obvious — that there is some generic way to encode $\langle M^\prime \rangle$, but I don't know how.

Secondly, is it correct to say that $f$ is computable because it is fully determined by its inputs?

# Answer
> 2 votes
"fully determined by its inputs" does not imply "computable". The halting function is fully determined by its inputs, but not computable.

---
Tags: turing-machines, computability, undecidability
---


title: Are these functions computable?

text:
# Question
Title: Are these functions computable?
consider $g$ and $f$ and $h$ as

$ \begin{align\*} g(m) &= \begin{cases} 1 & if\\;program\\;m\\;halts\\;on\\;input\\;m \\ 0 & otherwise \\ \end{cases} \end{align\*} $

$ \begin{align\*} f(m,n) &= \begin{cases} undefined & if\\;m=n \\ 1 & if\\;program\\;m\\;halts\\;on\\;input\\;n \\ 0 & otherwise \\ \end{cases} \end{align\*} $

$ \begin{align\*} h(m,n) &= \begin{cases} 1 & if\\;program\\;m\\;halts\\;on\\;input\\;n \\ 0 & otherwise \\ \end{cases} \end{align\*} $

we have a counter example for computability of $g$ and $h$ but we don't have any counter example for $f$ and even more interesting function $f\_{all}$ $$f(m,n)=\dfrac{m-n}{m-n}h(m,n)$$ $$f\_{all}(m)=1-sgn(\lim\_{w \to \infty}\sum\_{\substack{n=0 \\ n\neq m}}^{w}(1-f(n,m)))$$

we know that if $p$ is a universal diophantine polynomial then we can represent a non-computable solution to the halting problem as follows $$ h(m,n) = sgn(\lim\_{w \to \infty}\sum\_{x\_1=1}^{w}...\sum\_{x\_u=1}^{w}\dfrac{1}{1 + wp^2(m,n,x\_1,...,x\_u)}) $$

now the question is: are $f$ and $f\_{all}$ computable?

# Answer
It's easy to see that $f$ is **not** computable, using the padding lemma: there is a total computable function $t$ such that for all $x$, $t(x)\>x$ but program number $x$ and program number $t(x)$ have the same behavior (= yield the same partial computable function).

This means that $f$ computes $g$, since we have $g(x)=f(x,t(x))$.
> 2 votes

---
Tags: computability, halting-problem
---


# Question
Title: find shortest path from single source to multiple destinations with obstacles which you can move
a formulation on an example:

let's have on a grid:

* a position of a bee queen **Q** (source node),
* a set of positions of free cells to lay an egg **E** (destination nodes),
* and a set of positions with worker bees **W** (moveable obstacles).

the queen and workers can move to 4 orthogonally neighboring cells (left, right, up, down)

```
 e  w
e ww
 w Q

```

**the task is to find an efficient sequence of moves for the queen and workers to lay the queen's egg.**
**(what is an efficient algorithm to find the shortest sequence of moves for queen and workers?)**

---

obviously, if the obstacles were immovable, i would use a simple BFS or A\*.

if the obstacles **W** or destinations **E** were moveable but not by me, i would use other pathfinders like D\*.

but i'm in control of moving the workers, so one of the solutions is:

* queen moves left

```
 e  w
e ww
 wQ.

```
* worker gives her way

```
 ew w
e .w
 wQ

```
* and then 3 moves for the queen:

```
 ew w
Q..w
 w.

```

there is no shorter path

# Answer
> 1 votes
This remains a reachability problem, but now with a larger statespace.

The state of the system is the location of the queen and of all the workers. You have a transition from state $s$ to state $t$ if $t$ can be reached from $s$ in a single step (i.e., the queen moves one step, or one worker moves one step). The goal is now to find the shortest path from the initial state to a goal state.

This is a statespace reachability problem, and it can be solved with any algorithm for statespace exploration. For instance, you can use BFS, or you can use A\* with an appropriate heuristic function.

I don't know what is the best heuristic to use with A\*. A simple heuristic is to use the Manhattan distance from from the queen to the nearest egg (or, equivalently, the length of the shortest path if there were no workers). A better heuristic might be to find the shortest path from the queen to any egg, where only the queen can move, and it costs 1 for the queen to move to an empty square and it costs 2 for the queen to move to a square that has a worker in it (now the queen is allowed to occupy the same square as a worker, solely for purposes of computing this heuristic). Perhaps you can find a better heuristic.

I don't know whether there is any algorithm that can be guaranteed to be efficient in all cases. In the worst case, there can be exponentially many possible states, so naive statespace exploration might be very inefficient, in the worst case.

---
Tags: shortest-path, graph-traversal
---


# Question
Title: Calculate odds that cards drawn from deck sum to at least some number ("Across the Obelisk" problem)
Here is a problem inspired by the game Across the Obelisk.

4 players have decks of cards. Each card has an integer value between 0-9 on it. The decks can be any size, and there's no other restriction on the card values - each possible card-value can be represented any number of times, including 0.

The game chooses an integer $X$, then each player shuffles their deck and draws one card. **What are the chances the sum of those cards is $\geq X$?**

Digging into the game's code, the developers solve this problem by generating *every possible combination of cards* and putting their sums into an array, then counting how many instances are $\geq X$. With deck size $D$, this is $O(D^4)$. This is only feasible because there's a low number of players and the deck sizes are small. Is there a solution that scales better?

# Answer
Here's a solution I came up with that's $O(PD + PV\log{P})$, where

* $D$ = The size of the largest deck
* $P$ = The number of players *(4 in the original problem)*
* $V$ = The max card-value *(9 in the original problem)*

---

The main ideas of this algorithm are:

* We can treat any deck, no matter how large, as a discrete probability distribution containing only the $V+1$ values $0$ thru $V$, each with its own probability of being chosen.
* Because each deck is independent, we can treat the two cards coming from any two decks as though it were a single card coming from a single larger probability distribution, whose value lies in the range $0$ thru $2V$
* Any card-value $\geq X$ *(the integer we want our sum to beat)* can be replaced by $X$ without changing the result

Combining these ideas, we get the following algorithm:

1. For each deck, create a probability table mapping each card-value to its probability of being drawn
2. Combine two tables $A,B$ into a new table $AB$, using the rule $AB(N) = A(0)B(N) + A(1)B(N-1) + ... + A(N-1)B(1) + A(N)B(0)$

In other words, the probability of their sum being exactly $N$ is the $Prob(Card\_1 = 0, Card\_2 = N) + Prob(Card\_1 = 1, Card\_2 = N-1) + ...$

2a. *(Optional)*: Combine all the entries $\geq X$ into a single entry by summing their values
3. Keep combining tables like this until there is only one left, always combining the two smallest tables. The sum of all values $\geq X$ then gives the answer.

---

Asymptotic analysis:

Step 1 takes time $PD$ to calculate, plus $PV$ to initialize the arrays, for an overall $O(PD + PV)$

Step 2 does one multiplication for each combination of cards, for a total of $|A||B|$.

Step 3 has step 2 repeating a total of P-1 times. The first P/2 times, the tables will each have size V. The next P/4 times, the tables will have size 2V. The next P/8 times, the tables will have size 4V, etc. So the total number of multiplications is $$(P/2)(V+V) + (P/4)(2V+2V) + (P/8)(4V+4V) + ...$$$$= PV + PV + PV + ...(\log\_2{P}\text{ times})$$

for an overall $O(PV\log{P})$
> 1 votes

---
Tags: algorithms, computer-games
---


# Question
Title: Boolean Logic when one component switches from 0 to 1
I recently was constructing boolean logic for all sorts of examples from Morris Mano's "Digital Logic and Circuit Design". I noticed that it is possible to construct a boolean logic wrt the inputs which depends on the current state. My question is that is it possible to construct a boolean logic which depend on the previous states too. For example, I wonder if we can construct a boolean logic such that the output will change only when one input changes from 0 to 1 in that time step. Suppose we have 2 inputs p and q, with an output z. When q transits from 0 to 1 ,if p = 0, z = 1 and if p = 1, z = 0. Otherwise, if q transits from 1 to 0, or remains the same as the previous state, no change in output occurs.

# Answer
> 1 votes
Designing pure functions (i.e. output depends only on input) is called *combinational logic*, and designing stateful logic (i.e. a finite state machine) is called *sequential logic*. If you're working your way through Mano's book, I promise you will get to it.

The traditional way to design a basic sequential circuit is to start with a state diagram, and assign each state to a binary number which is stored in flip-flops. You then design a *combinational* circuit whose inputs include the previous state and whose output includes the appropriate inputs to the flip-flops to transition it them to the desired state.

For this, you need the truth table for the flip-flops that you are using. As an example, this is the truth table for a JK flip-flop:

```
  Q  Q'  |  J  K
---------+--------
  0  0   |  0  X
  0  1   |  1  X
  1  0   |  X  1
  1  1   |  X  0

```

So, for example, to transition from state `0` to state `1`, the J line must be 1, and the K signal can be anything. You can either "reset" (J=1, K=0) or "toggle" (J=1, K=1); either will work. The previous state of the flip-flop is an input to the combinational circuit, and the J and K signals are outputs of the combinational circuit.

Pulse-triggered JK flip-flops are especially popular for basic sequential design because the pulse-triggered design avoid timing hazards, and the "don't care" inputs often make the combinational circuitry simpler.

There is an art in how to assign binary values to states. Sometimes, it is worth using more flip-flops to simplify the combinational circuitry, especially in high-speed circuits where edge-triggered flip-flops may be more appropriate than pulse-triggered ones to minimise propagation delay.

A final note on terminology: Older texts use the term "master-slave" to refer to pulse-triggered flip-flops. For obvious reasons, that phrase is falling out of favour. That older terminology describes how it has traditionally been built (with two RS flip flops), rather than what it actually does.

# Answer
> 0 votes
If we want to build a circuit that depends on previous states, the way we do that is to keep a copy of the previous state. That way, it is part of the current state. Indeed, the circuit can only depend on the input and current state; it can't depend on past information that hasn't been stored in the current state. This may involve introducing additional variables (or registers) to store that information about the past.

---
Tags: logic, boolean-algebra
---


# Question
Title: How to find average time complexity of backtracking algorithm?
Problem is to decide if it is possible to partition a given array **nums** into **k** partitions. I've written a brute force backtracking algorithm. How do we analyse this algorithm to calculate average runtime (average over all possible inputs -input may be such that it ends up "back-tracking" multiple times or possibly none). I want to perform a rigorous analysis. Defition of the backtracking procedure, which is called from `main()` with arguments `CanPartK(0,nums,visited,k,0,SUM)` and `visited[]=FALSE` , is as follows:

```
 bool CanPartK(int start, vector<int>& nums, vector<bool>& visited, int k, int curr_sum,  const int& SUM)
{
    // k*SUM = sum of elements of nums[]

    if(k==0) return true;
    if(curr_sum==SUM) return CanPartK(0, nums, visited, k-1, 0, SUM);

    for(int i=start; i<nums.size(); i++)
    {
        if(!visited[i] && curr_sum+nums[i]<=SUM)
            {
                visited[i]=true;
                if(!CanPartK(i+1, nums, visited, k, curr_sum+nums[i], SUM))
                        visited[i]=false;
                else
                             return true;
            }
    }

    return false;
}

```

# Answer
> 1 votes
First run your algorithm, count the iterations. Check how it varies with different inputs. Get some idea about the runtime.

Unless you have a good counter argument, backtracking tends to be exponential. However, backtracking will also tend to exclude huge numbers of cases if done right and the actual execution time can have huge variations 2^n or 20^n is a huge difference. That means exponential time algorithms can have huge improvements.

---
Tags: time-complexity, backtracking
---